a) 成帧 >> b) 数据接入 >> c) 可靠交付 >> d) 差错控制 >>
链路层的主体部分是在网络适配器中实现的,网络适配器有时也称为网络接口卡。位于网络适配器核心的是链路层控制器,该控制器通常是一个实现了许多链路层服务(成帧、链路接入、差错检测等)的专用芯片
网络交换机：交换机是工作在2层（链路层）的设备，能够理解链路层协议。当交换机从某个网线接口收到一份数据（链路层的“帧”），它可以识别出“链路帧”里面包含的目标地址（接收方的 MAC 地址），然后只把这份数据转发给“目标 MAC 地址相关的网线接口”，【链接同种网络设备】
网桥/桥接机：链接两个不同网络类型的电脑，比如虚拟机通过网桥链接本机？
嗅探抓包工具（Sniffer）
ARP 命令：“MAC 地址解析协议”
物理层传输的信息，通俗地说就是【比特流】（也就是一长串比特）。但是对于计算机来说，“比特流”太低级啦，处理起来极不方便。“链路层”要干的第一个事情，就是把“比特流”打包成更大的一坨，以方便更上层的协议进行处理。在 OSI 模型中，链路层的一坨，称之为“帧”（frame） 。
用帧的第一个字节说明帧的总长度
但若是一个帧出错，则后面都会出错，不常用
通过两个flag标志帧头和帧尾，通过esc转义
【需要记忆flag和esc的二进制到底是啥样吗】
这种方法和第二种比较类似，区别是他把flag具体化了，为6个1。这样当正文读取的时候一旦出现了5个连续的1，那么在后面填充一个0，避免出现6个1造成帧提前结束。
物理介质的传输，可能受到环境的影响。这种影响不仅仅体现为“噪声”，有时候会出现严重的干扰，导致物理层传输的“比特流”出错（某个比特“从0变1”或“从1变0”）。因此，链路层还需要负责检查物理层的传输是否出错。在 IT 行话中，检测是否出错，称之为“差错控制机制”（后面有一个小节会简单说一下这个话题）。
常见的“检错算法”对传输的数据计算出一个【校验值】，接收方收到数据会重新计算校验和，如果算出来不对，就把收到的数据丢弃，让对方重发。
奇偶校验码由N-1位信息元和1位校验元组成。N-1位的信息元就是我们发送信息里的有效数据，而1位校验元就是用于检错的冗余码。
奇偶校验码可以分为奇校验码和偶校验码：
奇校验：这串序列1的个数如果为偶数则在前面加个1，使1的个数变成奇数，否则加0。
偶校验：这串序列1的个数如果为奇数则在前面加个1，使1的个数变成偶数，否则加0。
CRC循环冗余检验码是一种通过多项式除法检测错误的方法，将每个比特串看作一个多项式，采用模2运算，具体细节看这篇文章
Cyclic Redundancy Check and Modulo 2 Division
Definition: 海明距离指两个帧同样位置上,取值不同的位置数目。 Example: 10001001 and 10110001海明距离是3
【可以计算长度不同的编码的海明距离-by GPT 不保真】如果两个编码长度不同，可以通过在较短编码的末尾添加空位（通常是0）或在较长编码的末尾截断来对齐它们的长度。这样，两个编码就可以按照相同的长度进行比较，从而计算它们之间的海明距离
Essence: every bit at position 2^k^,k>=0 is used as a parity bit for those positions to which it contributes
如何编码：
【为什么H3在7这里？不是8吗->就是8，它写错了】
如何纠错：
【本质是通过一系列海明编码，然后找和自己海明距离最近的有效编码，从而完成纠错】
奇怪的问题：如果给你一串二进制值，你怎么确定哪个是高位😭按照十进制的习惯是高位在左，但是按照汉明码的上述计算结构，高位在右 ->根据习惯约定，给你的二进制位串高位在左，需要你手动将之转换为适合计算的格式
如果数据不满，应该怎么做？比如1101 0011 0011 0101，5位校验位和11位数据位
假设两个端点通过同一个物理信道进行通讯，这两个端点处理信息的速度可能不同。如果发送方输出信息的速度超过接收方处理信息的速度，通讯就会出问题。于是就需要有某种机制来协调，确保发送方的发送速度不会超出接收方的处理速度。在技术行话中，这称之为“流量控制”，简称“流控”。
数据链路层的流量控制方法主要是停止等待协议和滑动窗口协议，滑动窗口协议还包括后退N帧协议GBN和选择重协议SR。
【TODO: 这部分可能还要看一下协议原型和书上的代码，以及各种差错情况分析】
这部分不太明白，到时候找一篇文章再看看吧
停止等待协议就是每发送完一个帧就停止发送，等待对方的确认帧，在收到确认帧后再发送下一个帧
当发送方向接收方发送数据帧，发送方发送0帧到接收方，接收方收到0帧后，会向发送方回复0帧的确认帧ACK 0，发送方收到回复的确认帧ACK 0后，然后再向接收方发送1帧，发送双方不断的进行发送和确认的操作而传输数据。
【问题来了，为啥只有0～1】
（1）超时计时器设置的重传时间应当比帧传输的平均RTT更长一些。
（2）发送方发完一个帧后，必须保留该帧的副本，如果没有收到回复帧，则立刻重传该帧。
即发送方在等待确认帧时超时重传
也是超时重传
（1）上层的调用
上层要发送数据时，发送方先检查发送窗口是否已满，如果未满，则产生一个帧并将其发送，如果窗口已满，发送方只需将数据返回给上层，提示上层窗口已满，上层等一会再发送。（实际情况是发送方先缓存这些数据，窗口空闲时再发送）
（2）收到了一个ACK帧
GBN协议中，对n帧的确认采用累积确认的方式，标明接收方已经收到n帧和它之前的全部帧。同时，这里的确认是捎带确认。
（3）超时
与停止-等待协议一样，如果出现超时，发送方重传所有已发送但未被确认的帧。
如果正确收到n号帧，并且按序，那么接收方为n帧发送一个ACK确认帧，并将帧中的数据部分交付给上层。其余情况都丢弃帧，并为最近按序接收的帧重新发送ACK，接收方无需缓存任何失序帧，只需要维护一个信息，就是下一个按序接收的帧序号。意思是不是按序收到的帧都会被丢弃，并且不会回复确认帧。
（1）累积确认：就是当接收方向发送方发出第n帧的确认信息，那么接收方就认为第n帧之前的所有帧接收方都已正确接收。
（2）接收方只按顺序接收帧，不按顺序会被丢弃。接收方有一个计录需要接收帧的序号，如果不是它都不会接收直接丢弃。
（3）发送方窗口最大为 2^n^ - 1，接收窗口大小为1。
为什么最大窗口尺寸是2^n^ ** - 1?**
为了看清楚为什么必须有这个限制,请考虑下面 MAX_SEQ=7 的场景:
(1) 发送方发送0~7号共8个帧。
(2) 7号帧的捎带确认返回到发送方。
(3)发送方发送另外8个帧,其序列号仍然是0~7。
(4) 现在7号帧的另一个捎带确认也返回了。
问题出现了:属于第二批的8个帧全部成功到达了呢,还是这8个帧全部丢失了(把出错之后丢弃的帧也算作丢失)?在这两种情况下,接收方都会发送针对7号帧的确认,但发送方却无从分辨。由于这个原因,未确认帧的最大数目必须限制为不能超过 MAX_SEQ。
【要考】如果没有反向流量以捎带确认怎么办? 当一个按正常次序发送的数据帧到达之后,接收方通过start-ack-timer启动一个辅助的定时器。若在定期器到期之前没有反向流量,则发送一个单独的确认帧。
因连续发送数据帧而提高了信道利用率（与停止-等待协议比较），但是在重传时把原来已经正确传送的数据帧重传，又降低了效率。
为解决后退N帧协议GBN数据帧丢失需要重传确认的问题，选择重传协议SR解决问题的办法是设置单个确认，同时加大接收窗口，设置接收缓存（缓存乱序帧）
（1）上层的调用
上层要发送数据时，SR发送方先检查发送窗口可用于该帧的序号，如果序号位地发送窗口内，则发送数据帧；否则就像GBN一样，要么将数据缓存，要么返回上层之后再传输。
（2）收到了一个ACK帧
如果收到ACK，加入该帧序号在窗口内，则SR发送方将被确认的帧标记为已接收，如果该帧序号是窗口的下界（最左边第一个窗口对应的序号），则窗口向前移动到具有最小序号的未确认帧，如果窗口移动到有序号并未发送的帧，则发送帧。
（3）超时
每个帧都有自己的定时器，当某帧确认超时，则只重传某帧。
来者不拒（窗口内的帧）
SR接收方将确认一个正确接收的帧而不管其是否按序，失序的帧将被缓存，并反回给发送方一个该帧的确认帧，当序号最小的帧被接收，这时可以将一批按序帧交付给上层，则向前移动滑动窗口。图例：
【等等，这个协议连自顶向下方法的教科书上都未曾出现过😭】
细节的解析可以参考这篇文章，这里只是快速的过一下ppt里的内容
【成帧】采用零比特插入法，易于硬件实现，且支持任意的位流传输，实现信息的透明传输（bits填充）
【差错控制】采用CRC帧校验序列，可防止漏帧，提高信息传输的可靠性
【流量控制】全双工通信，吞吐率高，在未收到应答帧的情况下，可连续发送信息帧，提高数据链路传输的效率（是GBN还是SR呢？->两种都可以🤔通过control字段控制）
control字段里还有：sequence numbers, acks, nacks
【ppp基于HDLC协议】PPP encapsulation is based on the High-level Data Link Control (HDLC) derived from the mainframe environment.
【成帧】多协议成帧？->protocol字段
【差错控制】Frame Check Sequence。在常见的以太网协议中，FCS使用循环冗余检验（Cyclic Redundancy Check，CRC）算法进行计算
假设您想要与您的提供商建立真正的互联网连接。 ◼ 通过调制解调器建立物理连接。 • Pc通过Modem呼叫提供商先收到答复，建立物理连接 ◼ 您的 PC 开始发送大量链路控制数据包 (LCP)，以协商您想要的 PPP 连接类型。 请注意，这些数据包嵌入在 PPP 帧中： • 数据帧中的最大有效负载大小 • 进行身份验证（例如要求密码） • 监控链路质量（例如有多少帧未通过）。 • 压缩标头（对于快速计算机之间的慢速链接很有用） ◼ 然后，我们协商网络层内容，例如获取提供商的路由器可用于将数据包转发给您的 IP 地址。 // NCP，网络控制协议，破坏了层间关系。
【先协商链接类型，再协商上层内容】
【todo：这部分啥意思...】
•如果IP地址是动态分配的，谁来分配？ 提供者。 •如果IP地址是动态分配的，其他人是否可以向您发送数据( 他们不知道您的地址，是吗？我们需要先联系他们（我们的地址包含在请求中）。
在上一个章节已经讲到：用于远距离通讯的“物理介质”，总是有成本。因此需要对物理信道进行“多路复用”，就会导致多个端点共用同一个物理信道。如果同时存在多个发送者和多个接收者。接收者如何知道某个信息是发给自己而不是别人？ 另外，某些物理介质可能不支持并发（无法同时发送信息）。某些物理介质可能是【半双工】，所有这些物理层的限制，都使得“多路复用”变得复杂。为了解决这些问题，链路层需要提供了某种相应的机制（协议），术语叫做“介质访问控制”（洋文是“Media Access Control”，简称 MAC）。
我们可以把这种信道控制划分为三个策略：
完全不控制：简单地让站点尝试使用信道，并在发生冲突时执行某些操作。应用于竞争系统。
采用循环技术：允许每个站轮流使用该信道。应用于基于令牌的系统——拥有令牌的站可以使用该信道。
让电台预留频道。用于时隙系统。问题是如何进行预留。
事实上，我们已经实现了部分信道复用，比如之前的x分多路复用就是一种静态信道复用，但是它的效率还不够高。
策略选择：我们真正想要的是轻载时的争用策略，以及高峰时段的无碰撞策略 现实生活中：CSMA/CD适用于有线网络，CSMA/CA适用于无线网络
Principle： 如果想发就发好了。如果发生碰撞，等待一段随机事件后重试
效率分析
在t0时刻发送帧，会与在[t0-1，t0+1]期间其他结点发送的帧冲突
P(给定结点成功发送帧) = P(该结点发送) * P(无其他结点在[t0-1，t0]期间发送帧) * P(无其他结点在[t0，t0+1]期间发送帧)
= p * (1-p)^N-1^ * (1-p)^N-1^
= p * (1-p)^2(N-1)^
= 1/(2e) = 0.18（选取最优的p，并令n）
【通过某些神秘的数学计算，我们得知分槽aloha性能会好很多】
原理
所有帧大小相同，时间被划分为等长的时隙(每个时隙可以传输1个帧)，结点只能在时隙开始时刻发送帧，结点间时钟同步，如果2个或2个以上结点在 同一时隙发送帧，结点即检测到冲突。
当结点有新的帧时，在下一个时隙(slot)发送，如果无冲突，该结点可以在下一个时隙继续发送新的帧，如果冲突，该结点在下一个时隙以概率p重传该帧，直至成功。
效率
一个给定的结点成功传送的概率是p(1-p)^{n-1}^， 因为有N个结点，任意一个结点成功传送的概率是Np(1-p)^{n-1}^。当活跃结点数量趋向无穷大时，最大效率1/e，即37%。
【挺重要的，我猜测要考】
这个比ALOHA好，因为它在发送之前就检测冲突
1-persistent: listen whether the channel is free before transmitting. 当信道忙的时候，持续监听直到空闲便开始发送。
Nopersistent： Less greedy - 当信道忙的时候，等待随机时间再来尝试.If you wait to long, the channel utilization drops.
P-Persistent：用于分（时）槽系统.若发现当前时槽信道空闲，以概率p使用之。
P=1 is not really good, P=0 makes you really polite.
Question: Should the conclusion be that p- persistent protocos are really qood with p=0？ p=0不是大家太谦虚，然后没人用信道了吗
但是在现实生活中，检测有没有节点使用这个信道是一个工程难题，因为我们有传播时延等等一众延迟
改进 • 在传输过程中，保持监听以检测冲突。如果发生冲突，传输立即停止。 • 如果发生冲突，则等待一段随机时间，然后再次继续第一步。
知道无冲突的最短时间是$2T-\delta$，这被称为竞争期/征用期
这是一类免于冲突的协议
如有 N 个站点共享信道，编号为 0~N-1
竞争周期将分为 N 个时隙，每个站点占有一个时隙，如某站准备发送，则可在属于它的时隙内填入 1
一个竞争周期后，则将按顺序发送，不会产生冲突
简而言之，就是在竞争期轮流修改位图，表示自己在下一个传输期有无意愿传输数据
为了避免冲突,必须使用一条仲裁规则:一个站只要看到自己的地址位中的0值位置被改写成了 1,则它必须放弃竞争
即通过异或运算和判断01，决定要不要发送
【怎么选择协议】 • 当没有发生太多事情时，争用系统是好的 - 站点可以立即传输帧。 当出现问题时我们会进行一些修复。 • 当通常存在大量流量时，无冲突系统是很好的——站点首先必须在帧传输之前明确地获取信道。 我们做了很多工作来避免碰撞。 我们真正想要的是轻载时的争用策略，以及高峰时段的无碰撞策略
所以我们综合上述两种策略 解决方案：在竞争期间动态调节竞争站的数量。 如果在第 k 个时段发生冲突，则将竞争者分为两组。 • 第一组可以在下一个时隙（k+1）再次尝试。 如果没有发生冲突，则第二组在之后的时隙（k+2）内进行尝试。 否则，第一组将再次分裂。 注意：如果流量不大，则立即允许第一个站发送帧。 对于大量流量，该策略简化为位图协议。
某个竞争时槽，发生冲突，则缩小下一个时槽参与竞争的站点数目； 不发生冲突，那么下一个时槽应该让另一半节点来竞争； 当负载较重，显然不应该从树根节点开始尝试•负载越重，越应该从树的下面节点开始搜索
【为啥突然出现了一个光相关的东西，而且还和物理层有关🤔直接截图当展位符吧，懒得看了】
物理层 • 以太网布线 • 曼彻斯特编码 数据链路层 • 以太网 MAC 子层协议 - CSMA/CD • 二进制指数退避算法 • IEEE 802.2：逻辑链路控制子层 以太网性能 其他以太网 • 交换式以太网 • 快速以太网 • 千兆以太网
以太网代表 IEEE 802.3 协议的近似实现。 它基于 CSMA/CD（感知通道，等待空闲，并在检测到冲突时退避）
这部分也是看看就好...
接收方在没有外部时钟参考的情况下,可以毫无歧义地确定每一位的起始、结束或者中间位置
【注意，差分曼彻斯特编码中，第一个位置没有实际意义】
802.3 帧的组成：
前导码：7 个 10101010
帧起始符：10101011
目的地址（物理地址）
源地址（物理地址）
长度：不考虑前导码和帧起始符的长度。最短为 64 字节，最长为 1518 字节。
数据：LLC 数据，至少要 46 个字节，如果不够就要填充。
校验和：CRC 循环冗余校验，校验范围为除前导码和帧起始符外的字段
Ethernet 帧的组成：
前导码：8 个 10101010
目的地址（物理地址）
源地址（物理地址）
类型：上层网络层使用的协议
数据：LLC 数据，至少要 46 个字节，如果不够就要填充。
校验和：32 位 CRC 循环冗余校验，校验范围为除前导码和帧起始符以外的字段
为什么有一个字段既要表示类型，也要表示长度？ 是历史遗留问题，因为在IEEE标准出来之前，有很多MAC层协议，这一部分一般由之前的ppp协议里的llc负责，所以我们向既有事实妥协 “幸运的是,所有在 1997年之前使用的类型字段其值都大于 1500,因此规定了最大数据长度。现在的规则是,任何值小于或等于 Ox600(1536)可解释为长度字段,任何大于 Ox600可解释为类型字段。 现在IEEE 可以认为每个人都使用了它的标准, 并且其他人可以继续做他们正在做的事情(不能打扰 LLC),它因而无须感到内疚。“（自顶向下方法原文）
【考试内容】为什么以太网一帧的大小被限制为1500？为什么padding最多是46？/帧最多是64
【区分帧和垃圾数据】当一个收发器检测到冲突时，它会截断当前的帧，这意味着冲突帧中已经送出的位将会出现在电缆上。为了更加容易地区分==有效帧和垃圾数据==， 以太网要求有效帧必须至少64字节长，从目标地址算起直到校验和，包括这两个字段本身在内。如果帧的数据部分少于46个字节，则使用填充（Pad）字段来填充该帧，使其达到最小长度要求。
【防止冲突】这是一种机制，如果发生冲突则会产生48位长（？）的冲突噪声，所有帧必须至少需要2t时间才能完成发送,这样当突发噪声回到发送方时传送过程仍在进行。 “对于一个最大长度为2500米、具有4个中继器的10 Mbps LAN(符合802.3规范),在最差情况下,往返一次的时间大约是50微秒(其中包括了通过4个中继器所需要的时间)。因此,允许的最小帧长必须至少需要这样长的时间来传输。以10 Mbps 的速率,发送一位需要100纳秒,所以500位是保证可以工作的最小帧长。考虑到加上安全余量,该值被增加到512位,或者64字节。“
运行在以太网上，想上层网络层提供接口
•LLC 3种服务类型:不可靠数据包服务,有确认的数据包服务,面向连接的可靠服务
RTT（Round-Trip Time，来回传输时间）
看一下就好
placeholder，我猜肯定不考
在这部分： 两个局域网不同，网桥还要对不同的帧格式 进行重新封装 如果两个局域网数据传输速率不同，则网桥还要进行 Buffering
理想的网桥是透明网桥（transparent bridges ），它可以将多个 LAN 连接起来，LAN 内的硬件和软件不需要做任何的变化。
但是如果内部出现环，怎么防治无限转发->每个网桥维护扩展树
• 路由器：放置在“经典”网络中，并将数据包转发到其他路由器。 • 传输网关：在传输层连接两个网络：从 TCP 连接到 ATM 传输连接。 • 应用网关：连接两种不同的应用协议，例如将SMS 消息发送到Web 服务器，或将X.400 邮件系统连接到基于Internet 的邮件系统。
虚拟局域网（VLAN）可以将物理上不在同一 LAN 上的设备，在逻辑上归为同一组 LAN。一个 VLAN 对应一个广播域。有了 VLAN，可使用二层交换机实现广播域的分割。
事实上，更多的局域网桥接在一起才更好，更安全
如果 VLAN 是跨交换机的，可以用 IEEE 802.1Q 协议，方法如下：在跨交换机之前，交换机会给帧打上一个 VLAN ID 标记，当到达另一个交换机后，交换机拆除 VLAN ID，并转发给对应端口。
【todo】CRC冗余校验的局限性
每个未确认的帧都需要一个定时器，我们怎么获得多个定时器？ 一个硬件时钟和一个软件链表; 图里的剩余滴答数是时间差而不是时间
链路层的协议主要有如下： （介质访问控制） （逻辑链路控制） （解析 MAC 地址） （以太网） 的一部分（Wi-Fi） （2层VPN） （拨号上网） （拨号上网）
它通常用在两 "节点 (电信网络)")间建立直接的连接，并可以提供连接、传输以及。
PPP被用在许多类型的物理网络中，包括线、、、、特殊无线电链路以及光纤链路（如）。
PPP还用在接入上。早年，（ISP）使用PPP为用户提供到的，这是因为IP报文无法在没有数据链路协议的情况下通过线路自行传输。PPP的两个派生物和被ISP广泛用来与用户建立（DSL）、互联网服务连接。
【流量控制】和这两个子协议
