# USTC_CN ## Chapter 1 **互联网只是众多网络的一种，是一堆网络通过网络互联设备构成的巨型网络，网络的网络，Internet 网际** 物理层就是在媒体之上传输接收电磁波信号、光信号，把链路层来的0101的数字信号变成电磁波发走、接到、转换 链路层，*相邻两个节点之间*传输以*帧*为单位的数据 网络层，在链路层的基础上实现了*源主机到目标主机*的*端到端*的传输（尽力而为，不可靠） 传输层，在网络层的基础上，把主机之间的传输变为*进程之间*的传输，把不可靠变为可靠 按照应用层协议交换应用报文，实现各种各样的网络应用 主机节点 数据交换节点：既不是源也不是目标 中继器 交换机 路由器 负载均衡设备 链路把节点连接在一起 计算机网络：有节点和边 接入链路 access 主机和数据交换节点 骨干链路 backbone 数据交换节点之间 端系统 end system host 交换机是工作在链路层的网络交换设备 路由器是工作在网络层的网络交换设备 负载均衡器是工作在更高层的网络交换设备 **协议：对等层的实体在通信过程当中应该遵守的规则的集合** 格式（语法、语义）、次序、动作 pdu：协议数据单元Protocol Data Unit 应用层上叫message 传输层上叫segment **互联网是分布式的应用进程以及为分布式应用进程提供通信服务的基础设施** 基础设施包括了应用层以下的所有运行当中的协议实体，从应用往下看都是 分布式应用是网络存在的理由 socket api 面向连接的服务tcp 无连接的服务udp 方的：主机 圆的：交换节点 edge网络的边缘：边缘上跑了网络应用 core网络的核心：众多路由器交换机小节点构成分布式的系统，大的数据交换 access网络的接入网：把边缘的主机接入网络核心 C/S 客户端服务器模式 服务器先运行起来，客户端后运行 可扩展性差，负载达到一定程度，性能会断崖式下降 服务器农场server farm TCP流量控制 TCP拥塞控制 网络核心：电路交换/线路交换 circuit switch 信令 端到端的资源被分配给从源端到目标端的呼叫 call 独享：性能保障，但是如果没有数据传输则造成资源浪费 电话网络都是线路交换网络 网络资源（如带宽）被分成片pieces 将带宽分成片 Division Multiplexing 频分FDM 时分TDM 波分WDM 码分接入 CDMA 传播延迟 在局域网中可以忽略不计 在广域网中不能忽略 电路交换/线路交换不适合计算机之间的通信：连接建立时间太长，建立起的线路是独享的，能够保证性能，但是计算机之间的通信具有突发性，独享线路在没有数据发送时，会造成相当的浪费 网络核心：分组交换 packet switch 主机和主机的通信，越过每一个通信链路的每一跳用链路带宽的所有 主机和主机之间通信的数据被分成一个个单位，称为分组 packet 到每个节点，先完全存储再转发 延长变大但是换取了共享性 ![-w250]() 发送就是接收，发的同时就在接收，只不过要加上传播延迟，如果A和B靠的足够近，那么A在发的时候B就在接收 **代价**：分组交换：排队延迟和丢失 如果到达速率>链路的输出速率 分组将会排队，等待输出 如果路由器缓存用完了，分组将会被抛弃 好处就是共享性 按需使用 网络核心的关键功能 路由 转发 分组交换：统计多路复用/统计时分复用 STDM 分组没有固定模式 分组交换允许更多用户使用网络 流量强度趋近于1时，排队时延会趋近于无穷，分组需要无限等待才能被处理 如何让分组交换网络在有的时候表现得具有线路交换的特性 数据报网络：像寄信 1. 源主机发给目标主机的分组，携带了目标主机的完整地址 2. 交换节点收到分组，根据每个分组所携带的目标主机的完整地址进行存储转发 3. 两个主机通信之前不需要握手/连接 4. 每个分组都独立路由（路径可能不一样，可能会失序） 5. 每个交换节点当中（路由器）不需要维护主机之间的通信状态 虚电路：打电话 virtual circuit 1. 源主机与目标主机通信之前需要握手/连接 2. 交换节点之间需要维护通信状态，建立一条虚拟线路 3. 每个分组携带一个虚电路号（而不是目标主机的完整地址） 4. 每个分组以虚电路号作为标识，到达交换节点之后存储转发 5. 虚电路靠信令建立 TCP向应用进程提供服务是面向连接的，而不是有连接的 面向连接 这个连接仅仅体现在端系统的TCP实体上，目标主机和源主机的TCP实体上，中间的路由器不维护他们之间的通信状态 接入网路和物理媒体 有线接入 电话线-程控交换机 猫 modem 调制解调器 用电话线上网 调制和解调 ASDL SDL 不同带宽负责不同任务 光纤 同轴电缆 光纤到户 AP 无线接入 无线LANs 无线广域接入 物理媒体是第零层 导引型媒体：看得到的 双绞线 同轴电缆 光缆：带宽极宽，误码率极低，安全 全反射要获得传输的东西需要把光纤割开 bypass 旁路之后才能截获 采用电磁波，或多或少会辐射出去一些，被截获 光信号在光纤当中，入射角满足一定条件，实现全反射 单模光纤：垂直，传的非常远 多模光纤 光纤 高鲲 非导引型媒体：看不到的 **Internet结构和ISP** 互联网是网络的网络 ISPs：Internet Service Providers 互联网服务提供者 接入ISP需要互联 全部两两连接的话，需要连接的数量太巨大，可扩展性scalability比较差 ![-w350]() IXP：互联网交换点 ISP：提供网的 ICP：提供业务的 Internet Content Provider Google 全球范围之内部署很多数据中心机房并用专线连在一起，位置离一些ISP很近 成本原因：ISP收费太高 用户体验原因 ![-w350]() 互联网是一堆ISP通过网络互联设备构成的 具有一个松散的层次结构 ISP之间网络的互联是任意的 服务质量不好可以换，多头接入 **分组延时、丢失和吞吐量** 四种分组延时 处理延时preceeding 排队延时 传输（发送）时延：把比特打到链路上 传播时延：比特在链路上传播的时间（距离比较近可以忽略不计） 流量强度：$I = \frac{La}{R}$ I处在0, 1之间 R是链路的带宽 L是每个分组的长度 a是单位时间内希望通过这条链路转发的分组的数量 流量强度趋近于1时，排队延时趋近于无穷，分组需要无限等待才能被处理，分组会丢失 设计系统时流量强度不能大于1 tracert address traceroute address ICMP 协议：互联网控制报文协议 分组到路由器TTL-1 RTT：Round Trip Time Traceroute 的基本原理是向目标主机发送一系列 TTL（生存时间）从 1 开始递增的 IP 数据报。每个数据报在路由器中 TTL 减 1，当 TTL 减到 0 时，该路由器丢弃数据报并向源主机返回一个 ICMP “Time Exceeded” 报文。这样，源主机可以知道数据报在第几跳被丢弃，从而确定该跳的路由器地址。当 TTL 值足够大，数据报成功到达目标主机时，由于目标端口号无人监听，目标主机会返回一个 ICMP “Port Unreachable” 报文，源主机据此判断目标已达，结束探测。每次发包和收包之间的时间差即为该跳的往返时间（RTT）。 丢失的分组 1. 由上一个路由器重传 2. 由源主机重传 3. 根本不重传（UDP） 链路可靠，链路层向上提供的服务是不可靠的（以太网） 链路不可靠，链路层向上提供的服务是可靠的 吞吐量：单位时间内从源主机向目标主机发送的有效的比特数 瞬间吞吐量 平均吞吐量 短板效应，取决于小的 瓶颈链路：端到端路径上，限制端到端吞吐的链路，就是那个比较小的 路由器之间的链路可能同时有n组源目主机在使用通信，那么这些主机可使用的实际带宽/吞吐量是链路带宽的1/n 路由器之间的链路可能同时有n组源目主机在使用通信，那么这些主机可使用的实际带宽/吞吐量是链路带宽的1/n，最小值是瓶颈带宽 协议层次 使用分层的方法实现复杂网络的设计与实现 把计算机网络复杂的功能分成一个个功能明确的层次 每一层通过层间接口向上层提供服务，这一层的功能需要借助下层的服务来与对方交换PDU 协议的目的是为了向上层提供更好的服务 协议通过层间接口访问下层所提供的服务才能实现 协议是水平的，服务是垂直的 ![-w350]() 服务访问点SAP：下层服务提供者用SAP区分不同上层用户的信息 Socket API 套接字 服务用户和服务提供者在层间界面上的服务访问点，使用原语 原语就是提供服务的形式 Socket API函数调用，应用层使用传输层服务TCP/IP 服务用户通过SAP告诉服务提供者要使用它的什么服务 服务提供者通过原语告诉服务用户向它提供什么服务 两个用户在使用下层提供的服务之前需要握手建立连接，那这种服务就是面向连接的服务 无连接的服务 本层协议的实现需要使用下层提供的服务 实现本层协议的目的是为了向上层提供更好的服务 ![-w350]() 上层的SDU经过层间接口抵达下层，与一些头部结合被封装成本层的PDU，随后继续作为相对上层的SDU向下传输 SDU可以被分割成若干小块，与头部结合变为一些小的PDU 上层一些小的SDU，可以结合成一个大的，与下层头部结合变为本层PDU 一对一，一对多，多对一 SDU就像是货物 每一层的PDU就像是卡车头（头部）装载货物（上层SDU） 应用层的PDU：应用报文 message 传输层的PDU：报文段 segment 网络层的PDU：分组 IP数据报 链路层的PDU：帧 frame 分而治之，分治算法 Internet协议栈 应用层：在传输层提供的服务基础上，完成应用报文与报文之间的交互，实现各种各样的网络应用 传输层：在网络层主机到主机的传输的基础上，完成进程到进程的区分，将网络层提供的不可靠传输变为可靠传输，不出错，不重复，不丢失，不失序 网络层：在链路层提供的相邻两点之间传输的基础上传输以分组为单位的端到端的数据传输 链路层：在物理层提供的基础之上，在相邻两点之间传输以帧为单位的数据 物理层：把数字信号转为物理信号，承载在媒体之上，从一点传到相邻的另外一点 ISO/OSI参考模型 ISO国家标准化组织 OSI开放系统互联 应用层 表示层 会话层 传输层 网络层 链路层 物理层 表示层会话层的功能在TCP/IP协议栈中由应用层实现 1.7 1小时之后的内容 到路由器要做一个三层的解封装，再封装 到交换机要做一个两层的解封装，再封装 各层次的协议数据单元 应用层的PDU：(应用)报文 message 传输层的PDU：报文段 segment 网络层的PDU：分组 Packet （在网络层不建立连接，又可以叫做datagram数据报） 链路层的PDU：帧 frame 物理层的PDU：位 bit NCP协议：相当于TCP和IP的综合体 IP over everything Everything over IP 域名解析 ftp 尼尔逊提出超文本 hml ## Chapter 2 应用层 TCP/IP协议下 传输层向应用层提供服务的方式就是Socket API套接字编程，原语就是Socket API 网络应用的体系结构 C/S模式 服务器是中心，资源在服务器，客户端请求服务，服务器响应请求 可扩展性差 可靠性较差 P2P模式 既是服务器又是客户端 混合体 Napster 即时通讯 进程通信 客户端进程 服务器进程 Session 会话 标识一个进程需要三样东西 主机IP TCP还是UDP TCP或UDP的端口号 web应用跑在80号端口 ftp跑在21号端口 一个进程：用IP + Port表示端节点 任何一对应用进程之间的通信都可以用两个端节点来表示 end point 传输层提供的服务需要穿过层间的信息 1. “货物”SDU 2. 谁传的：自己的应用进程标示：IP+TCP(UDP)端口 3. 传给谁：对方的应用进程标示：对方的IP+TCP(UDP)端口 65536个端口号，16位 TCP Socket是个整数代表四元组，一个本地标识 我的IP，我的端口号，对方IP，对方端口号 便于管理，使层间通过的信息量最少 TCP socket 代表两个进程之间的会话关系 操作socket值就是操作会话关系 2.1 50min开始 UDP Socket是个整数代表二元组 目标IP，目标UDP端口 要传三样东西 1. 货物本身 SDU 2. UDP Socket 3. 对方IP，端口号 应用协议：运行在不同端系统上的应用进程如何相互交换报文 实体：指的是仅仅和网络交互有关的，遵守协议的这部分内容 公开协议 专用（私有）协议 衡量传输层给应用层提供服务的指标 数据丢失率 延迟 吞吐 安全性 TCP服务： * 可靠的传输服务 * 流浪控制 * 拥塞控制 * 不能提供：时间保证，最小吞吐保证，安全保证 * 面向连接 TCP用时间换可靠 UDP服务 * 不可靠 * UDP通过增加端口号，可以区分应用进程 * 无连接 * 不做可靠性的工作 * 应用能够按照设定的速度发送数据 实时多媒体应用 ![]() 增加TCP，UDP的安全性 SSL 安全套接字层 APP SSL TCP UDP SSL在应用层，因为应用采用SSL库，SSL库使用TCP通信，但也可以说在传输层，因为它为应用层提供服务 HTTP HTTPs s就是SSL over TCP，保证安全性 Web与HTTP Web页由一些对象组成 URL：通用资源定位符 ![]() HTTP超文本传输协议 Web的应用层协议 C/S模式 HTTP使用TCP S1 等待Socket S2/3... 连接Socket HTTP是无状态的 无状态服务器：不维护客户端状态 维护状态协议很复杂 非持久HTTP--> HTTP 1.0 通信结束连接断开 文件传输时间2RTT+传输时间 第一个RTT用来发起TCP连接 第二个RTT用来HTTP请求并等待HTTP响应 持久HTTP-->HTTP1.1 持续连接，不用每次都建立TCP连接 流水线 pipeline 前面的没回来，就进行下面的请求 非流水线 non-pipeline 在前面一个回来之后，再进行下一次请求 HTTP请求报文 请求行方法类型 GET：客户端向服务器请求 POST：客户端向服务器提交 HEAD：取头部，维护/建立索引 1.1才有的 PUT DELETE HTTP响应报文 状态行 TCP不维护报文与报文之间的界限 需要应用进程自己区分messages之间 状态码 200: OK 301: Moved Permanently 400: Bad Request 404: Not Found 505: HTTP Version Not Supported HTTP是无状态协议 没有记忆 cookie 在请求报文中有一个Cookie的首部行 通过Cookie将HTTP变为有状态的，有记忆 Web缓存（代理服务器） 客户端：快，降低客户端的请求响应时间 服务端：减小Web服务器载荷 把很多用户的访问请求在本地命中，从而减小服务器负担，减小用户的响应时间 二八定律 $tqueue = \frac{I}{1-I}\frac{L}{R}$ 安装本地缓存，满足不了的再通过proxy访问Original Server 减少成本，减少用户访问时间，提高性能 Conditional GET条件获取方法 头部字段 if modified since 如果改了就再发一份新的，没改就不用 保证缓存的对象和服务器中对象的一致性 ![-w350]() **FTP 文件传输协议** 上传到服务器 从服务器下载 守候在21号端口 FTP用户 FTP服务器 用户名和口令都是明文传输 抓包可以抓到很多 服务器与客户端的20号端口主动建立数据连接 控制命令和数据传输在两个TCP连接上进行 FTP是有状态协议 **Email** 三个主要组成部分 * 用户代理 * 邮件服务器 * 简单邮件传输协议：SMTP Web应用的用户代理：浏览器 FTP应用的用户代理：客户端软件 用户代理发给邮件服务器，邮件服务器放到队列里，然后挨个打到相应的邮件服务器，邮件服务器收邮件到相应的用户邮件箱 用户到相应邮件服务器的邮箱当中使用以下三个协议把邮件拉出来 POP3 IMAP HTTP 前两跳推，后一跳拉 使用TCP C/S模式 端口号25 从送方服务器到收方服务器 传输的3个阶段 * 握手 * 传输报文 * 关闭 邮件内容必须处在规范的ASCII码范围之内 报文必须为7位ASCII码 SMTP使用持久连接 SMTP要求报文为7位ASCII码 HTTP 拉 SMTP 推 二者都使用ASCII形式的命令/响应交互、状态码 HTTP：每个对象封装在各自的响应报文中 SMTP： 多个对象包含在一个报文中 carbon copy（CC）抄送 暗自抄送，暗抄 MIME：多媒体邮件扩展 Base64 IMAP提供的特性比POP3更复杂 远程目录维护 HTTP不仅用于Web访问，还可以用于文件上传下载，还可以用于收发邮件 下载并删除模式 下载并保留模式：从其他客户端/主机还能看到邮件 POP3无状态 IMAP提供远程目录文件夹维护，服务器端得维护客户端状态，所以是有状态的 **DNS** Domain Name System 域名解析系统 *名字空间找到网络空间对应节点IP地址* 主机名解析为IP地址转换 一个由分层的DNS服务器实现的**分布式数据库** 一个使得主机能够查询分布式数据库的应用层协议 DNS运行在UDP之上，53号端口 它是给其他的应用用的应用，最终由其他应用服务人 独立于物理的网络空间： * 一个域名所包含的IP节点可以在不同的子网 * 一个子网内也可能包含不同域名的节点 互联网是以子网为单位进行物理组织的，子网之间通过路由器相联 子网的聚集和可达性通告，大概齐的聚集，对应可达性通告 树形组织的DNS名字空间 根->顶级域->二级域->...... DNS名字空间：倒着生长的树 ![]() DNS空间是**逻辑的** 区域：名字空间中人为划分的不重叠范围 * 任何一个区域都有对应的权威名字服务器 * 维护该区域名字和IP的对应关系 * 分布式域名解析 **DNS根的IP地址是确定的** ![-w350]() ![-w350]() ![-w350]() CDN内容分发系统 域名--> IP地址的转换 分层的命名 分布式的解析 维护问题 互联网的核心功能很多都在网络边缘的主机应用进程上实现 别名--规范名字-- IP地址 刀片服务器 负载均衡 根DNS服务器 顶级域DNS服务器 权威DNS服务器 本地DNS服务器 顶级域 Top Lever Domains com, org, net, edu, gov/uk, fr, ca, jp 二级域 三级域 互联网的名字空间是一颗倒着生长的树 命名从树叶往树根走 共有13个根名字服务器 墙的原理是DNS污染 ![-w350]() 域的划分是逻辑的，而不是物理的 域与物理网络无关 名字服务器Name Server 一个名字服务器会造成很多问题 可靠性问题、扩展性问题、维护问题 区域 Zone 将DNS名字空间划分为互不相交的区域，每个区域都是谁的一部分 每个区域都有一台名字服务器，维护者它所管辖区的权威信息，是这个区域的权威名字服务器 权威DNS服务器 上层区域得知道下层区域怎么走 TLD服务器，顶级域服务器 上层域得有一个指针指向下层域的名字服务器 区域名字服务器维护资源记录 Domain name TTL Class Value Type ![-w350]() TTL可以是长期（权威记录）或短期（缓冲记录） 缓存，提高查询效率，减少权威服务器负载，为了性能 删除，为了一致性 上层得知道下层 key: 子域 value：子域的IP服务器 key：子域服务器 value：该子域服务器的地址 2.5 53min DNS大致工作过程 应用调用解析器 解析器作为客户向Name Server发出查询报文 Name Server返回响应报文 IP 地址 子网掩码 默认网关 default gateway DNS Local Name Server本地名字服务器 在一个子网内部的名字服务器 名字解析过程： 目标名字在Local Name Server中 1. 查询的名字在该区域内部 2. 缓存caching 本地名字服务器中找不到时， 1. 进行递归查询，顺着树根往上走，询问权威名字服务器 2. 进行迭代查询，根服务器告诉你下面的权威服务器自己查 递归查询：根服务器帮你查 深度查询dfs 迭代查询：根服务器告诉你在哪，自己查 广度查询bfs ![]() 实践中，大多是从请求主机到本地DNS服务器的查询是递归的，其余的查询是迭代的 DNS协议报文 查询报文和响应报文格式相同，通过标识位flag判断 ID号很重要，可以实现流水线方式，通过查询ID号和响应ID号匹配，可以在上一个回来之前就发下一个 通过缓存提高性能 在DNS数据库中插入数据 P91 流量是分布式的，不需要走根 查询也不一定要从根 所以中国一个根服务器也没有会造成安全隐患，但问题不大 **P2P** C/S模式 上载带宽是ui 下载带宽是di 采用C/S方法将一个F大小分发给N个客户端时 $D_{c-s} = max\{\frac{F}{d_{min}},\frac{NF}{u_s}\}$ 对于客户端数量很少的时候，服务器性能没问题，那么瓶颈就在于客户端自身的下载带宽 对于客户端数量很多的时候，服务器自身上载带宽就是瓶颈 $D_{P2P} = max\{\frac{F}{d_{min}},\frac{NF}{u_s+\sum\limits_Nu_i},\frac{F}{u_s}\}$ ![-w350]() P2P 性能高、可扩展性好 系统管理能力差 非结构化P2P 节点之间构建任意的Overlay * 集中化目录（Napster）：一个服务器管理节点具有的资源，P2P分发，可能会产生单点故障、性能瓶颈、版权问题 * 完全分布式（Gnutella）：每个节点已经和其他节点构成了Overlay；泛洪flooding，一个节点向所有邻居发送查询报文，命中的反向转发。配置死档列表，所有收到ping的节点发送pang * 混合体（kaZaA）：每个节点都属于某个组，组长，组员，组内是集中是的，组长之间是分布式的，将Hash值作为文件的唯一ID DHT（结构化）P2P Overlay覆盖网，应用层的逻辑网 BitTorrent 节点加入到洪流，互通有无 每一个节点维护一个bitmap 映射是否有这个资源 通过bitmap的泛洪，就可以知道在洪流的所有其他节点拥有资源的信息 一开始什么都没有的块，是吸血鬼，先随机下载四块，之后遵循稀缺优先 Tit-for-Tat 上传越积极（上传速率高、对更多人上传），你越容易从别人那里获得更高优先级的下载。 上传越多，别人更倾向于回传给你，因此你获得的下载速度可能更快。 有限疏通 BitTorrent 客户端会每隔一个周期（通常是 10 秒），根据过去两个周期中各个 peer 给它上传的速度来评估“谁对它贡献大”。然后本周期就优先向这些 peer unchoke（给予上传服务）。此外，每隔一个较长的周期（比如 30 秒），会随机从其余的 peer 中选一个“优化的 peer”（optimistic unchoke），给予上传机会，以探测是否存在更好的互惠对象。 BitTorrent（BT）是一种去中心化的点对点（P2P）文件共享协议，基本工作流程如下： 1. 获取 .torrent 文件 用户通过网站或搜索引擎下载 .torrent 文件，文件中包含了： * 被分享文件的元数据（如文件名、大小、分片信息等）； * 一个或多个 Tracker 服务器地址。 2. 联系 Tracker 客户端读取 .torrent 文件后，会向指定的 Tracker 服务器发送请求，汇报自己正在下载该文件。 3. 获取 Peer 列表 Tracker 返回当前也在下载或上传该文件的 peer 列表（IP 和端口），这些 peer 就是其他用户的客户端。 4. 连接并交换数据 客户端与这些 peer 建立连接，互相交换文件分片（piece），谁有我缺的片，我就向谁请求；我有别人缺的片，我就上传给他们。 5. 块交换策略 BT 使用 “tit-for-tat”（你传我，我传你） 策略选择上传对象，同时定期进行 “Optimistic Unchoke” 试探其他 peer。 6. 完成下载 & 做种（Seeding） 当下载完成后，客户端可以继续保持连接，为其他 peer 上传数据，称为“做种”。 DHT(Distributed Hash Table )结构化P2P 1. DHT 网络结构是“逻辑环” • 所有节点通过某种方式（如 IP 地址 + 端口）计算哈希值（通常是 SHA-1），得到一个 m 位长的整数。 • 这些哈希值在一个大小为 2^m 的编号空间内按顺时针方向排列，构成一个环状结构。 2. 节点在环上有序排列 • 每个节点根据其哈希值（node ID）占据环上的一个位置。 • 节点通过一定规则连接到环上的其他节点，以便于路由（如 Kademlia 中有路由表）。 3. 数据存储也用哈希定位 • 共享内容（文件、键值对等）也通过哈希算法生成一个 key。 • 按照 一致性哈希（Consistent Hashing） 规则： 这个 key 被存储在第一个哈希值大于等于 key 的节点上（即该 key 的“后继节点”）。 4. 查找过程是结构化的 • 路由算法使查找时间复杂度从 O(N) 降为 O(log N)。 • 比如：Kademlia 协议使用 XOR 距离 + k-bucket 路由表，只需 log 级跳数。 redis分布式存储 mongodb中的分片集群 ES集群 **视频流化服务和CDN** 视频是一系列图像构成的 图像又是一系列像素点的序列构成的 AVS，Audio Vedio Standard MPEG 流化服务 streaming 变下载变观看，下与看并行，下好放入缓冲区 多媒体流化服务 DASH：Dynamic Adaptive Streaming over HTTP 传输的一块块内容是在HTTP上的 HTTP就是传输协议 manifest file DASH（动态自适应流媒体传输）是一种基于 HTTP 的流媒体传输协议，它将一个视频文件划分为多个小块（segments），并为每个块提供多个版本（不同码率、分辨率、编码等）。 所有版本的块信息统一存储在一个 manifest 文件中（称为 MPD，Media Presentation Description），该文件描述了每个块的： * 可选分辨率（Resolution） * 编码格式（Codec） * 比特率（Bitrate） * 块的 URL 路径（HTTP 下载地址） 客户端播放时，先下载 manifest 文件，实时分析当前的 网络状况、设备性能、缓冲状态等，然后根据实际情况动态选择适合的版本（比如高码率、高分辨率，或者低码率、低分辨率）进行下载和播放。 ![-w350]() CDN（Content Distribution Network）通过在全球范围内部署分布式缓存服务器（称为 边缘节点 / 缓存节点），将常用的内容（如网页、图片、视频）提前存储到离用户更近的位置。 ICP预先部署内容在CDN缓存节点上 当用户请求某个内容时，DNS 域名解析会将请求引导到最近的边缘节点，从而实现： • 更短的延迟（latency）； • 更快的加载速度； • 降低主服务器负载； • 提高服务可用性和抗压能力。 两种典型的 CDN 部署策略： 1. Enter Deep（深度进入） • 特点：CDN 服务商将缓存服务器部署到大量本地 ISP 的网络内部，甚至是边缘城市的接入层交换机旁边。 • 优点：服务器离用户非常近，跳数少、延迟低、带宽保障好，特别适合视频、直播等对时延敏感的场景。 • 缺点：需要与大量 ISP 合作，硬件部署和维护成本高，管理复杂。 📌 举例：YouTube 的 CDN（Google 的 GGC - Google Global Cache）就采用了此策略，把缓存服务器放进了世界各地的小 ISP 网络中。 2. Bring Home（带回家） • 特点：CDN 服务商仅在少量的关键网络枢纽位置部署缓存节点，例如大城市的互联网交换中心（IXP）。 • 优点：部署数量少、管理集中、成本较低，适合对“准实时”要求不高的内容（如网页、静态文件）。 • 缺点：用户请求还需经过较多跳数，服务延迟比 Enter Deep 稍高。 📌 举例：Akamaized 网络早期部署、或国家级门户网站可采用该方式。 CDN的作用就是提供内容加速服务 中国蓝汛 China Cashe “让内容靠近用户” 用户如何知道这些内容去哪访问： * manifest file * 域名解析重定向 CDN是在应用层实现的，在网络边缘 很多网络核心服务都是在边缘实现的 ![-w350]() ## Chapter 3 传输层 发送方：将应用层的报文分成报文段，传递给网络层 接收方：将报文段重组成报文，然后传递给应用层 网络层向上层提供的服务并不可靠，可能丢失，乱序，重排，出错 传输层将网络层提供的不可靠的服务加强成可靠服务 延迟无法降低，带宽无法变大 **复用和解复用** 源端目标端复用解复用 ![-w350]() 引入port 使用Socket使得通过层间的信息最少最方便 Socket：源IP｜源port｜目标IP｜目标port｜PID 多个应用进程共享一个TCP/UDP协议 根据端口号将数据交给对应应用进程 PID进程标识符 ![-w350]() **UDP** 不可靠，可能乱序、丢失 无连接 适用于：流媒体应用、事务性应用（一次往返搞定） DNS SNMP 跑在UDP之上，又想要可靠性，需要应用进程自己在内部实现可靠性 校验和用来判断UDP包括头部和载荷部分在传输过程中有无出错 错就表现为丢失 8字节头部 cost/head payload 从上面来多块就往外发多块 校验和edc 用于差错检测 接收方计算校验和 不相等，那肯定有错 相等，也可能有错，残存错误 D｜EDC D：IP尾头部 + UDP头部 + UDP数据部分 Check Sum D+D' EDC+EDC' 进位回滚求和 做反码 **RDT可靠数据传输的原理** 双向数据通信分解成两个单向数据通信 使用 FSM有限状态机来描述发送方和接收方 $\frac{事件}{动作}$ RDT 1.0 封装，解封装 假设下层信道不出错不丢失不失序不重复，完全可靠 RDT 2.0 下层信道可能出错，Packet 有可能出错 发送方两个状态： 等待上层调用它的发送 等待ACK，NAK 谢谢或者不谢谢 接收方： 等待下层的调用 收到NAK 检错重传 ACK或NAK错了怎么办？ RDT 2.1 在分组中增加序号 在ACK/NAK可能出错的前提下，把刚刚发送的Packet在发送一遍，即使产生重复，也可以通过序号检测出来 停止等待协议 Stop-and-Wait 没有确认的确认 RDT 2.2 无NAK的协议 NAK free 对ACK做编号 对当前分组的反向确认用前面分组的正向确认去代替 RDT 3.0 具有比特差错和分组丢失的信道 packet丢了 发送方等待确认 接收方等待packet 产生死锁 死锁的四个条件 * 互斥 * 请求并保持 * 不可剥夺 * 循环等待 **超时重传机制** 超时：比正常往返时间长一点 ACK丢了，再发packet就好，重复问题已经在前面解决 适应式的超时时间 动态计算 链路层的超时时间计算和传输层的超时时间计算不太一样 链路容量很大的情况下 一次发一个，停止等待的利用率极低 比如北京到合肥的高速公路上，车辆经过收费站，只有当一辆车到达目的地，并返回，下一辆才能走，这样整条链路上大部分时间都是空闲的，此时的链路利用率就很低 流水线协议 一次发送多个未经确认的分组 * 回退N步协议(GBN：GO Back N) * 选择重传协议(SR：Selective Repeat) 铺垫：滑动窗口协议(Slide window) | 发送窗口SW | 接收窗口RW | 协议 | |------------|------------|----------------| | SW = 1 | RW = 1 | 停止等待协议SAWP | | SW > 1 | RW = 1 | 回退N步协议GBN | | SW > 1 | RW > 1 | 选择重传协议SR | 发送/接收缓冲区 如果发送缓冲区很大，那么就可以发送很多未经确认的分组，但是，由于线路的利用率最大就是100%，所以发送缓冲区大小是有上限的 发送窗口是发送缓冲区的一个范围，发送窗口是发送缓冲区的一个子集，存放已发送但是未确认的分组 发送窗口的最大值 ≤ 发送缓冲区的大小 窗口的相对滑动：分组不动，窗口向前滑动 实际是窗口不动，分组向后滑动 滑动窗口的后沿不能超过前沿 接收窗口 RW = 1，GBN 0｜1｜2｜3｜4｜.... $\ \ \ \ \ \ \ \ \ \uparrow$ 此时，0和1已经接收，接收窗口照在2上，意味着现在只能等待2被接收，此时如果3、4、....过来，不接收，并丢弃。并发送ACK = 1，意味着1以及之前的分组已经接收，期待接收1的下一个也就是2被接收，**发送连续收到的最大分组的确认，累计确认**，不是每一个分组都有超时计时器，只有位于发送窗口下沿的分组具有超时计时器，当发生超时重传时，会发送所有在发送窗口内已发送但是未收到确认的分组 RW > 1，SR 在滑动窗口内的分组可以乱序接收，接收一个分组，发一个ACKi，但是只有顺序接收完成时，才能向前移动窗口。每个分组都有一个超时计时器，当发送方接收到某一个分组的确认时，就会关闭它的计时器，发生超时重传，只会发送个别超时的分组，而不会全发 ![-w350]() ![-w350]() 分组使用n位编号，序号空间是$2^n$ | 协议 | 发送窗口的最大值 | |------|------------------| | GBN | $2^n-1$ | | SR | $2^{n-1}$ | 序号空间可以被看作为一个长度为$2^n$的环，其中序号为$2^n-1$紧接着序号0 **TCP** ![-w350]() 应用进程将报文数据交给 TCP，TCP 根据最大报文段长度（MSS）对数据进行分段，并在每个分段前加上 TCP 头部，封装成 TCP 报文段（segment），然后交给 IP 层进一步处理。 发送方缓存：需要进行检错重传和超时重传 接收方缓存：解决应用进程读取的速率与发送方传播的速率的不一致性 全双工：同时、双向 MTU：最大传输单元 Maximum Transmission Unit ![-w350]() TCP头部中的序号：指的是每一段MSS的第一个字节在整个TCP字节流中的偏移量 ｜MSS｜MSS｜MSS｜MSS｜.....｜MSS｜ x x+MSS x+n*MSS 偏移量是指某个数据（比如一个字节）距离某个起始点的位置，用来标识它在整个数据流中的“相对位置。 一般来说，TCP头部固定20字节 累计确认 有点类似GBN ![-w350]() ACK = n: n之前的都已经收到了，下一个期望收到的是n 在《计算机网络自顶向下第七版》中是这样的描述的： 收到一个ACK。在GBN 协议中，对序号为n的分组的确认采取累积确认（cumulative acknowledgment）的方式，表明接收方已正确接收到序号为n的以前且包括n在内的所有分组。 在TCP协议中主机A填充进报文段的确认号是主机A期望从主机B收到的下一字节的序号。看一些例子有助于理解实际发生的事情。假设主机A已收到了来自主机B的编号为0 ~535的所有字节，同时假设它打算发送一个报文段给主机B。主机A等待主机B的数据流中字节536及之后的所有 字节。所以主机A就会在它发往主机B的报文段的确认号字段中填上536。 ACK的值和TCP首部中的序号 The sequence number is the byte number of the first byte of data in a TCP segment, while the acknowledgement number is the sequence number of the next byte the receiver expects to receive 超时时间如何设置 测量RTT 卡尔曼滤波 $TimeoutInterval = EstimatedRTT + 4\cdot DevRTT$ 平均值 + 4倍的偏差 **TCP可靠数据传输** GBN和SR的结合体 ![-w350]() 收到3个冗余确认，触发的重传称为快速重传（超时计时器还未耗尽） 之前讲RDT的时候讲的分组实际上是一个代词，当前第n层要实现可靠数据传输，把第n层的pdu叫做分组，而在TCP协议中需要被具体化，也就是报文段 为了减少 ACK 报文段的数量，提高传输效率，TCP 可采用**延迟确认机制**。其原理如下： 当接收方收到一个报文段后，并不会立即发送 ACK，而是启动一个最多持续 500 毫秒的辅助定时器（Delayed ACK Timer），以等待是否还有后续报文段到达： * 如果在定时器超时前，又接收到新的报文段，则不立即发送 ACK，而是重启定时器，继续等待后续报文段； * 如果在某次定时器超时时，没有再接收到新的报文段，则立即发送 ACK，用于确认所有已接收的报文段。 ![-w350]() **TCP流量控制** 接收方控制发送方，不让发送方发送的太多、太快以至于让接收方的缓冲区溢出 通过捎带技术 Piggybacking，一方把自己空闲缓冲区的尺寸告诉 对方 **TCP连接管理** 连接的本质 1. 双方都知道要和对方通信 2. 为这次通信要准备好缓冲区 3. 控制变量要做一些置位（双方的初始序号到要告知对方，且确认） 三次握手 ![-w350]() 1. 我告诉你我的初始序号是x 2. 你要对“我的初始序号是x”这件事进行确认 3. 你告诉我你的初始序号是y 4. 我要对“你的初始序号是y”这件事进行确认 2，3合并成一步就是捎带 SYN = 1 每次初始序号的选择是随机的，以此来区分老数据和新数据 **TCP关闭连接** 大概齐的拆除 两个半连接 两军问题 客户端，服务器分别关闭它自己这一侧的连接 * 发送FIN bit = 1的TCP段 一旦接收到FIN，用ACK回应 * 接到FIN段，ACK可以和它自己发出的FIN段一起发送 * 可以处理同时的FIN交换 ![-w350]() 两侧连接关闭后，启动一个定时器，在定时器归零前如果没有再收到数据，连接就被真正的关掉了 **拥塞控制原理** 太多的数据需要网络传输，超过了网络的处理能力 拥塞的表现： * 分组丢失 * 分组经历较长延迟 * 为了让网络达到理想的泵出，输入分组的速率要比迸出的速率大很多，造成更大的成本 * 由于拥塞，分组可能会经历比正常情况下更长的延迟，从而导致超时重发，而这种重发是多余的没有必要的，从而会进一步加剧网络的拥塞 > 如果不加控制，网络拥塞会加速变坏 * 当分组丢失时，任何“关于这个分组的上游传输能力”（在网络时分拥塞下的）都被浪费了 拥塞控制方法 * 端到端的拥塞控制（靠自身判断） * 网络辅助信息的拥塞控制 网络辅助信息的拥塞控制 ATM ABR拥塞控制 ABR：available bit rate RM（资源管理）信元 ![-w350]() ER字段 Explicit rate ![-w350]() **TCP拥塞控制** 端到端的拥塞控制原理 拥塞感知： * 某个段超时（丢失） 1. 网络拥塞，路由器缓存没有空间了，段被丢弃 2. 由于各级错误，导致段被丢失，实际上网络可能只是轻微拥塞，一定程度上是误判，但是此情况概率小 * 收到有关某个段的3次重复ACK 轻微拥塞 拥塞窗口：CongWin/cwnd 发送端限制已发送但是未经确认的数据量上限，从而粗略控制发送方往网络注入的速率 $rate = \frac{CongWin}{RTT}$ 超时或收到3个重复ACK时：CongWin减小 * 超时时：CongWin降为1MSS，进入SS阶段然后再倍增到CongWin/2（每个RTT），从而进入CA阶段 * 3个重复ACK：CongWin降为CongWin/2，进入CA阶段 否则，CongWin增大，跃跃欲试 SS（慢启动）阶段：每个RTT*2（加倍增加） > 实际上，慢启动并不慢，只是起点低，实际增加速度按照指数级增涨 CA（拥塞避免阶段）：每个RTT+1MSS）（线性增加） 试探酒量的方式 TCP拥塞控制和流量控制的联合动作 SendWin = min{CongWin, RecvWin} swnd = min{cwnd, rwnd} ![-w350]() 乘性减，加性增 ![-w350]()![-w350]() 3.7 30min TCP的公平性 n = 2 $RTT_{AA'} = RTT_{BB'}$ ![-w350]() ## Chapter 4 网络层：数据平面 转发在数据平面 路由在控制平面 传统方式和SDN（软件定义网络：Software Defined Network）方式 转发：从哪个端口入，从哪个端口出，局部功能 路由：路由决定从源主机到目标主机的路径，全局功能 路由表是算出来的 路由表是控制平面和数据平面的粘合剂 流表是网络操作系统根据南向接口算出来的 流表：根据流表网络对分组做动作：转发，阻止，泛洪，改变字段 传统路由器，在一个设备上分布式的实现数据平面和控制平面 数据平面和控制平面紧耦合 控制平面：路由算法决定端到端路径 数据平面：IP协议根据转发表决定了IP数据报在此路由器上的局部转发 SDN方式：逻辑集中的控制平面 控制平面是集中式的 网络是可编程的 分组交换机：Packet Switch 网络服务模型 传输层的连接仅仅体现在两个端系统之间 网络层主机与主机之间的连接被称为有连接 IP网路向上层提供的服务可以用best effort这个服务模型来表述 ![-w350]() **路由器组成** 路由：运行路由选择算法/协议（RIP，OSPF，BGP）生成路由表 转发：从输入到输出链路交换数据报，根据路由表进行分组的转发 最长前缀匹配 输入端口队列 当交换机构的速率小于输入端口的汇聚速率时，输入端口可能要排队 需要匹配瞬间的速度不一致 Head-of-the-Line(HOL) blocking: 排在队头的数据报阻止了队列 中其他数据报向前移动 交换机构 fabric * 将分组从输入缓冲区传输到合适的输出端口 * 交换速率：分组可以按照该速率从输入传输到输出 * N个输入端口：交换机构的交换速度事输入线路速度的N倍才比较理想，不会称为瓶颈 memory bus crossbar 通过内存交换 memory 通过总线交换 bus 通过互联网络的交换 crossbar 输出端口 调度问题 输出端口排队 排队带来延迟，由于输出端口缓存溢出则丢弃数据报 调度机制 FIFO先来先服务 丢弃策略： * tail drop：丢弃刚到的分组 * priority：根据优先权丢失/移除 * random：随机地丢失/移除 优先权调度：发送最高优先权的分组 Round-Robin Scheduling 时间片轮转 Weighted Fair Queuing 加权公平队列 **IP Internet Protocol** ![-w350]() 以太网IP数据报数据部分MTU = 1500B 分片 根据offset偏移量进行定序 ![-w350]() **IP地址** 用来标识网络设备接口 主机有几个网卡就有几个IP地址，若主机有虚拟网卡，则会有更多IP地址 路由器至少有两个IP地址 子网 Subnets IP地址 高位bits：子网部分 低位bits：主机部分 一个子网内的节点（主机或者路由器）它们的IP地址的高位部分相同，这些节点构成的网络的一部分叫做子网 无需路由器介入：一跳可达，子网内各主机可以在物理上相互直接到达 纯子网 要判断一个子网, 将每一个接口从主机或者路由器上分开,构成了一个个网络的孤岛 ![]() A类一个字节代表网络号 B类两个字节代表网络号 C类三个字节代表网络号 .... A类地址有$2^7-2 = 126$个网络，有$2^{24}-2$个主机 .... 一个子网聚集成一个表象 以网络为单位，做路由信息的通告、传播和计算 子网部分：全0---本网络 主机部分：全0---本主机 主机部分：全1---广播地址 ![-w350]() 127.x.x.x 回路地址 127.0.0.1 测试地址 ping ... = ping 自己 内网（专用）IP地址 ![-w350]() **CIDR无类域间路由** 子网部分可以在任意的位置 a.b.c.d/x > x是地址中子网号的长度 子网掩码：为1的位置代表是子网号，为0的位置代表是主机号 查路由表的时候，将IP地址与子网掩码作与运算，将子网号提取出来 路由信息在通告当中可以聚集 默认的端口 = 出口路由器所对应的IP = 默认网关 DHCP：Dynamic Host Configuration Protocol 从服务器中动态获得一个IP地址 Plug and Play 接上就用了 DHCP（Dynamic Host Configuration Protocol，动态主机配置协议）是一个网络协议，用于自动为设备分配 IP 地址和其他网络配置信息，让设备能够快速加入网络、进行通信，而不需要手动设置。 四个信息 IP地址 子网掩码 Mask 默认网关 Default Gateway Local Name Server DNS服务器 ![-w350]()![-w350]() DHCP server：提供IP地址的服务器，通常是路由器或专用服务器 DHCP client：请求IP的设备，如电脑、手机、打印机等 DHCP lease：IP地址是租来的，不是永久的，有时间限制 静态地址保留（Static DHCP）：某些设备每次都保留固定IP（打印机...） 租用期到了要renew一下 DHCP在UDP之上 两次交互 如何获得一个网络的子网部分 从ISP获得的地址块中分配一个小的地址块 比如 20位子网号｜12位主机号 --> 20位网络号｜3位子网｜9位主机号 这样23位子网号构成的网络就是20位子网号构成网络的子网 ICANN：Internet Corporation for Assigned Names and Numbers 层次编制：路由聚集 路由器发布子网通告信息，如果关于某个子网前缀的都发给特定的路由器/IP，那么就称这个路由器/IP是关于这个子网前缀的下一跳 路由信息聚集的时候可以允许一定的空洞 比如拿到了八个连续地址块中的七个 路由聚集使得路由表项大大减少 **NAT：Network Address Translation** 所有内网地址在进入互联网的时候使用一个有效IP地址 回来的时候，把目标IP地址把外网地址换为内网地址 ![-w350]() ![-w350]() 主动出去没问题 外网设备进来交互会产生问题 NAT穿越问题 内网穿透 方案： 1. 静态配置NAT 2. Universal Plug and Play(UPnP)协议 Internet Gateway Device(IGD)协议 动态查询、增加、删除NAT路由器映射表的表项 3. 中继 外部设备借助中继relay的关系把要和内网对象通信的信息告知对方 **IPv6** IPv4被分完了 地址由32位-->128位 固定头部40字节 ![]() TLV类型数据 type length value type: 后面数据的类型 Checksum被移除 Options允许但是在头部之外 ICMPv6 * 增加了"Packet is too big"报文 * 多播组管理功能 隧道：在IPv4路由器之间传输的IPv4数据报中携带IPv6数据报 IPv6与IPv6之间借助IPv4的隧道 IPv6是小岛 IPv4是海洋 平滑过度 最后小岛越来越多，海洋越来越少，最后都变成大陆，平滑过渡成IPv6 ![-w350]()![-w350]() IPv6部署还要很长时间 **通用转发和SDN** 每个路由器既实现了控制平面的功能又实现了数据平面的功能 网络设备太多了 垂直集成 一家独占所有产品 SDN：逻辑上集中的控制平面 通过南向接口下发流表，分组交换机就可以根据流表行动 SDN水平集成，集中化 流量工程：传统路由比较困难 ![-w350]() 数据平面交换机 * 流表被控制器计算和安装 * 基于南向接口（e.g. Openflow），SDN控制器访问基于流的交换机 * 也定义了和控制器的协议（Openflow） SDN控制器（网络OS） * 维护网络状态信息 * 通过上面的北向接口使得SDN控制器与网络应用交互 * 通过下面的南向接口使得SDN控制器与分组交换机交互 逻辑上集中，物理上分布式 网络控制应用 控制的大脑，采用下层提供的服务，实现网络功能 控制平面 每个路由器包含一个流表（被逻辑上集中的控制器计算和分发） 匹配 + 操作 match + action ![-w350]() **可以精确控制路径** ![-w350]() **网络层控制平面** 路由表怎么算 传统路由选择算法 SDN控制器 ICMP 传统方式和SDN方式 内部网关协议 RIP/OSPF 外部网关协议 BGP 传统方式：垂直集成，分布式实现，买一个厂商设备容易被这个厂商绑架，网络的工作方式僵化，无法修改 SDN方式：控制平面，数据平面分离 **路由选择算法** * link state * distance vector 路由：找到一个路由器到其他所有路由器最好的路径 路径 Path 一般选择较好路径，最小代价，最快，最不拥塞 路由器-路由器的之间的最优路径 = 主机-主机之间的最优luj Dijkstra's algorithm 输入： 网络拓扑 边的代价 源 输出： 源到所有目标的最优路径 汇集树（sink tree） 树是最小联通图又是最大无环图 图可能有环，到一个节点可能有多钟路径，那就没有最优一说了 全局路由选择算法：有上帝视角，能看到网络拓扑，代价 link state 分布式路由选择算法 distance vector 链路状态算法 link state * 获得网络拓扑和链路代价信息 * 使用最短路由算法得到路由表 * 使用此路由表 ![-w350]() 链路状态：周边节点与其他节点的相连情况已经其代价 链路状态分组泛洪 泛洪广播风暴 解决：TTL + 版本号 可靠泛洪，需要对方确认 使用LS协议的 OSPF IS-IS Dijkstra算法 v(D(v),P(v)) c(i,j)：从节点i到j链路代价 D(v)：从源节点到节点v的当前路径代价 P(v)：从源到节点v的前序节点 N'：当前已经知道最优路径的节点集合（永久节点结合） I-N'：临时节点集合（没搞定的节点集合） 与源节点相邻的节点 ![-w350]()![-w350]() 贪心算法 每次都找最小的 ![-w350]() 生成汇集树 ![-w350]() 复杂度：$O(n^2)$ 可能会造成路径震荡 Distance vector距离矢量路由选择算法 DV算法基本思想 * 各路由器维护一张路由表， * 各路由器与相邻路由器交换路由表 * 根据获得的路由信息，更新路由表 DV与Floyd不一样 Floyd算法 ![-w350]() 角标是中间点，Path矩阵存放前序节点 ![-w350]()![-w350]() ![-w350]() Bellman-Ford 算法 ![-w350]() Bellman-Ford方程（动态规划） $d_x(y)$：从x到y的最小路径代价 $d_x(y) = min\{c(x,v)+d_v(y)\}$ 分不的迭代式算法 我把距离矢量给邻居让他们去算，邻居把距离矢量给我，让我去算 ![-w350]() DV的特点： * 好消息传得快，坏消息传得慢 形成环路 无穷计算问题 水平分裂（Split Horizon）算法 ![-w350]() Count to Infinity：一个路由失效后，节点间反复“互相告诉彼此还可达”，导致路由表中跳数无限增长（直到最大跳数）。 通过 Split Horizon，错误信息就不会“兜回来”，加快了路由收敛。 毒性逆转 Poison Reverse 如果你是我通往某个目的地的下一跳，我就明确告诉你：“通过你去这个目的地的距离是 ∞（不可达） ![]() **内部网关协议** * RIP * OSPF **RIP**：Routing Information Protocol 跳数最大为15，16即为不可达 DV每隔30s和邻居交换DV，通告 每个通过包括：最多25个目标子网 自治区域内，小网，使用距离矢量算法 ![-w350]() RIP通告报文通过UDP报文传送，周期性重复 网络层的协议使用了传输层的服务，以应用层实体的方式实现 **OSPF**: Open Shortest Path First 使用LS算法 IS-IS路由协议几乎和OSPF一样 ![-w350]() ![-w350]() 在本区域内泛洪链路状态分组 area border routers：既在backbone区域内又在一个具体的区域内 “ RIP 距离矢量慢、只靠邻居问；OSPF 链路状态快，靠自己看全图。” “小网络用 RIP，大网络靠 OSPF。” ⸻ **ISP之间的路由选择协议** 一个平面路由，使用LS或DV算法非常困难 层次路由：将互联网分成一个个AS（autonomous system） 整个互联网就分为自治区域内和自治区域间 每个自治区可以选择自己的路由选择协议（LS/DV） 子网数量、路由器数量都有限，LS/DV都hold的住 ![-w350]() 互联网AS间路由：**BGP** Border Gateway Protocol 边际网关协议 * eBGP: 从相连的ASes哪里获得子网可达信息 * iBGP：将获得的子网可达信息传遍到AS内部的所有路由器 使用改进的距离矢量算法（路径矢量） 不仅仅是距离矢量，还包括到达各个目标网络的详细路径（AS 序号的列表）能够避免简单DV算法的路由环路问题 ![-w350]() BGP会话：2个BGP路由器在一个半永久的TCP连接上交换BGP报文 路径属性 不仅通告代价还要通告序列，让对方可以检测出其中是否有环路，避免无穷计算问题 AS-PATH：前缀的通告所经过的AS列表 NEXT-HOP：访问某个前缀所应走的下一跳地址 自治区之间路由要强调策略 网关路由器可能获取有关一个子网X的多条路径 选择代价最小的，跳数少不一定代价小 使用TCP协议交换BGP报文 ![-w350]() 热土豆路由 ![-w350]() 内部网关协议关注于性能 外部网关协议更关注于策略 SDN ICMP：Internet Control Message Protocol ![-w350]() ![-w350]() ## Chapter 6 链路层和局域网 广域网链路层比较简单 点到点的链路一般用于广域网：距离比较远 * 海底电缆 多点连接的链路一般用于局域网 * 共享型介质 * 网络交换机 MAC：Media Access Control 介质访问控制 ![-w350]() nodes：节点，主机，路由器，网桥，交换机 links frames：帧，链路层的PDU 一个节点把帧通过链路传递给另一个相邻的节点 同样的IP分组，在每一跳中封装格式都可能不同 数据报（分组）在不同的链路上以不同的链路协议传送 不同的链路协议提供不同的服务 ![-w350]() 以太网在链路层提供不可靠服务 如果链路比较可靠，出错率低，就放弃可靠传输的功能 如果链路不可靠，出错率高，在协议上就需要可靠传输的功能 WLAN在链路层实现可靠协议，出错要重发 ![-w350]()![-w350]() 前向纠错，如果错的没那么多，可以根据网络编码，从出错的帧上恢复过来 每个网卡（网络适配器/NIC：Network Interface Card）实现了链路层和相应物理层的功能 发送数据 1. 网络层（IP 层）传下数据包 • 比如你想发一个网页请求，IP 层会生成 IP 数据包，交给链路层处理。 2. 数据链路层（网卡）封装为帧（Frame） • 网卡根据 MAC 地址把这个 IP 包封装成以太网帧（Ethernet Frame），添加： • 源 MAC 地址、目标 MAC 地址 • 帧类型字段 • FCS（帧校验序列）等 3. 物理层将帧转换为比特流 • 网卡借助物理层技术（如曼彻斯特编码、NRZ 等），把整个帧编码为 0 和 1 的比特流。 • 比特流以电信号、电磁波或光信号的形式发往网线、Wi-Fi 天线或光纤中。 接收数据 1. 物理层接收信号 • 信号经过网线等介质到达网卡。 • 物理层把电信号等转换为二进制比特流。 2. 数据链路层将比特流组装成帧 • 网卡重组成一个完整的帧，检验 FCS 校验是否正确（用于差错检测）。 • 如果帧的目标 MAC 地址匹配本机网卡，就上交给上层协议处理。 **检错和纠错** EDC = 差错检测和纠正位（冗余位） D 奇偶校验 单bit奇偶校验：检测单个bit级错误 2维奇偶校验：检测和纠正单个bit错误 无法防范对偶错误 **CRC**：循环冗余校验码 * 模2运算 加法不进位，减法不借位 加和减是一样的 异或 = 不进位加法 * 位串的两种表示 $1\cdot x^3 +0\cdot x^2 + 1\cdot x + 1 \iff 1011$ * 生成多项式 r次方 1001 $G = x^3 + 1$ r+1位 你想留出几位校验码，就左移几位；你想留几位校验码，就用 r 次生成多项式（r+1位二进制） * 使得数据位+r位冗余位正好能 够被生成多项式整除 | D | EDC | |--------|-----| | 数据位，要被保护 | r位冗余位 | 接收方：用数据位+r位冗余位除以生成多项式，如果整除，则代表数据无误 $D\cdot 2^r \iff D左移r位 $ $D\cdot2^r\oplus R = nG$ $D\cdot2^r\oplus R\oplus R = nG\oplus R ，由于x\oplus x = 0$ $D\cdot2^r = nG\oplus R$ $R = [\frac{D\cdot 2^r}{G}]$ ![-w350]() ![-w350]() **多点访问链路和协议** MAP：Multiple Access Protocol 完全分布式的 MAC（Medoa Access Control）协议： * 信道划分 * 随机访问 * 依次轮流 信道划分MAC协议： TDMA时分复用 FDMA频分复用 CDMA码分复用 ![-w350]() 用得比较少了 ![-w350]() 随机MAC协议 * 时隙ALOHA 时槽：空闲的，成功发送的，碰撞的 要求各个节点在时间上保持同步 要冲突就全冲突 * 纯ALOHA 简单、无须节点间在时间上同步 但是帧的冲突概率变大 效率没那么高 CSMA 载波监听多路访问 使用之前先检测一下是否有人在用信道 但是冲突仍可能发生：由传播延迟，导致两个节点可能检测不到正在进行的传播 两个节点距离越远，传播时间越长，冲突概率越大 CSMA/CD 载波监听多路访问/冲突检测 说前先听，边说边听 检测到冲突，则传输终止 节点检测到冲突，要发送一个强化的jam信号 ![-w350]() 二进制指数退避算法 exponential backoff 连续碰撞次数k 在$\{0,2^k-1\}$中选择一个数i。等待i * 512位时 碰撞次数越多，退避时间范围指数增长，从而降低再次冲突的概率 自适应算法 无限局域网中的MAC：CSMA/CA 载波监听多路访问/冲突避免 LAN：Local Area Network WLAN：Wireless Local Area Network 检测到信道忙则等待 检测到信道空闲也不是直接发送，要选取一个随机值，在信道空闲的时候开始-1，也就是退避倒计时，直到倒计时归0，信道仍然空闲则发送 传输过程中不做冲突检测 如果发送，则一股脑全部发送 CD也没用，不冲突也不等于成功 ![-w350]() 确认帧的发送优先级比数据帧的发送优先级高 LAN中，不冲突 = 成功 WLAN中，不冲突 ！= 成功 有线不需要确认 无限需要确认 ![-w350]() ![-w350]() ![-w350]() **线缆接入网络** CMTS：Cable Modem Termination System 竞争式时隙 预约式时隙 DOCSIS: data over cable service interface spec 上行竞争性时隙预约，下行发布预约结果，各个节点根据预约情况使用相应的时隙，如果预约不成功，二进制指数退避再次预约，直到预约成功 利用率问题： 信道划分协议：高负载利用率高 随机协议：低负载利用率高 轮流（Taking Turns）MAC协议 高负载和低负载情况下表现都很好，但是太复杂 论询：主节点一个一个问从节点 但是容易造成单点故障 在令牌传递协议中，网络中仅有一个特殊的控制帧——令牌帧（Token）在节点之间按顺序轮流传递。节点只有在持有令牌时才能发送数据。发送节点将令牌帧替换为数据帧，数据帧按环路传播，接收节点在识别出自己地址后拷贝数据，然后由发送方移除数据帧并重新生成令牌，继续轮转。 高低负载下表现都很好，但是不如信道划分和random的最好表现 ![-w350]() **MAC地址和ARP** MAC地址48位写死了 到达节点，将帧拆封，用IP查找路由表，找到下一跳IP，利用ARP协议解析MAC地址后再封装为帧，然后传输 MAC地址的作用是在一个网络的内部从标识一个节点与另一个节点 理论上全球任何两个网卡的MAC地址是不一样的 IP地址是分层的 MAC地址是平面的 48位全1是广播地址 MAC地址是不变的 IP地址会变 **ARP：Address Resolution Protocol** 跨层的协议 ARP缓存：储存IP地址和MAC地址的映射关系，具有TTL 存：为了用得快 删：为了适应变化 plug and play 以太网 一个碰撞域只允许一个节点发 hub --> switch 总线型-->星型 交换机通过提供点对点的全双工通信，避免冲突的产生，从而解决了传统以太网（基于CSMA/CD）在高负载下性能下降的问题。 以太网：无连接、不可靠的服务 以太网的MAC协议：采用二进制退避的CSMA/CD介质访问控制形式 ![-w350]()![-w350]() ![-w350]() 曼彻斯特编码 1：有向下跳变 0：有向上跳变 跳变有无：目的是把时钟信号抽出来 5个bit代替4个bit 有限的若干bit确保有一个跳变，接收方可以通过这个跳变同步它的接收时钟，按照这个接收时钟来接收数 5B/4B 编码是把每 4 位数据编码成 5 位代码，以确保传输过程中不会出现太多连续的“0”或“1”，从而便于接收端保持时钟同步。 通过HUB连接的所有设备在一个碰撞域之内 级联 交换机 帧的存储转发设备 对主机来说交换机可以是透明的 交换机有MAC地址 即插即用，自学习 ![-w350]() 不知道，就泛洪 如果输出端口和输入端口一样，则过滤掉 如果不一样，则转发 交换机级联不能形成环 使用生成树算法 同一时刻起作用的只有一棵树 交换机和路由器都是存储转发设备但是层次不一样 交换机是链路层存储转发设备 路由器是网络层存储转发设备 二者都有转发表