引入

本章节以局域网的视角，将物理层、数据链路层、网络层三层进行链接。前面课程虽没有涉及物理层内容，但其他课程（例如通信原理）已经打下了基础。

几种路由方式

寻找路由，有几种不同的方式：

集中式：有一个节点对网络所有节点和拓补状态都非常了解，中心路由找出的路径是最优的。但是集中控制代价极高，而且有同步周期问题（需要不断从整个网络收集信息，需要收集耗费的时间尽可能短）
分布式：交换由每个节点完成，路由更复杂，但是鲁棒性更高

对于面向连接和面向无连接，决定路由的时机也不一样。

面向连接需要在通信之前就确定路由，并固定线路。
而面向无连接只有到达特定的节点后，下一条路的路由才会出现。

现有的4种路由模式

Fixed：在该模式下，某一进来的包固定得被转发至一个固定的出口
Flooding
Random
Adaptive Routine：这是目前分组交换网络中大量采样的路由方式。这种路由属于需要各节点的信息，根据当前的信息进行自适应路由，但在集群规模的扩大时，收集信息会导致网络时延增加、部署成本提高，无法满足算力需求和部署要求。

物理层的视角切入局域网（基于以太网）

ALOHA

纯ALOHA

当传输点有数据需要传送的时候，它会立即向通讯频道传送，这也就是“想说就说”。
接收站通过检查帧校验序列字段来确定传入帧的正确性

如果正确，会给传输站点发送ACK。传输站点等待ACK的时间是2倍物理传输时长+一个小小的增量
如果接收的数据有错误，接收点会向传输点发NACK。
如果网络上的两个传输点同时向频道传输数据的时候，会发生碰撞（因此说ALOHA是一个竞争协议），这种情况下，两个站点会各自等待一段随机长度的时间后，再次尝试发送。

但是，如果站到站的传播时间比帧传输时间长，那么，在一个站发射一个帧之后，需要很长时间其他站才知道它。在此期间，其他站可能会开始传输帧，这会导致所有帧损毁。

纯ALOHA非常简单，但这样也带来了缺点：随着负载的增加，碰撞次数迅速增加，通道的最大利用率仅为18%左右。

slotted ALOHA（分段ALOHA）

为了ALOHA的利用率，将信道在时间上进行分为不同的子时段，每个传输点只能在一个子时段的开始处进行传送。每次传送的数据必须少于或者等于一个子间段。这样大大的减少了传输频道的冲突。

但是也提出了链路上时钟同步的要求。

slotted ALOHA将系统的最大利用率提高到约 37%

CSMA

就算是slotted ALOHA，利用率也还是太低了。无论是纯ALOHA还是slotted ALOHA，都缺少对信道当前状态的侦测，如果能不要“畅所欲言”，而是如果发现别人在说话，等别人说完了再发言，那么碰撞概率会进一步减小。

因此我们引入CSMA

CSMA：carrier sense multiple access，载波侦听多路访问（注意是multiple access，不是multiplex）

载波侦听（Carrier Sense）：指任何连接到介质的设备在欲发送帧前，必须对介质进行侦听，当确认其空闲时，才可以发送。

nonpersistent CSMA

在该模式下：

发信设备侦听信道是否空闲

如果空闲：则立即开始发信
如果不空闲：则随机或固定地等一段时间后再检查是否空闲

nonpersistent CSMA有一个缺陷：无法确定在信道传输的信息处于什么状态，可能处于比特流的头两个字，这时候延时可能等少了。如果处于比特流最后两个字，这时候可能等多了，造成时间的浪费

因此，引入 1-persistent protocol：

1-persistent CSMA

发信设备检查信道是否空闲

如果空闲：立即发信
如果忙：则持续侦听，一旦忙结束，立即发信

但是这样又产生了一个问题：如果信道资源很紧缺，一个忙当中，有多个发信站都在等待忙结束，在忙结束之后又立即发信，在空闲瞬间的“蜂拥而至”会导致帧碰撞。

因此，引入 is p-persistent：

p-persistent CSMA

如果信道空闲，则有概率p的可能发送，（1-p）的概率再等一个等待周期
如果信道忙，则持续侦听，等到空闲时执行 1 当中的概率发送

这个方法减少了“蜂拥而至”造成的碰撞的概率。

CSMA/CD

在前面的CSMA机制中，纵然比AHLOHA效率更高，但是对碰撞的处理并不完善：如果两帧发生碰撞，在碰撞发生后发送端仍然会发送完该帧才截止，这加剧了碰撞占用信道的时间。

而CSMA/CD中的CD就是“Collision Detection”，碰撞检测。在CSMA/CD模式下，网络适配器会“边发送边侦听”。在CSMA/CD机制下：

如果信道空闲，则直接发信
如果信道忙，则遵循CSMA的规则，侦听信道直到其不忙
如果在传输过程中任意站点检测到冲突，则发送一个人为的干扰信号（jamming signal），让所有站点都知道发生了冲突，然后停止传输。
（问题：碰撞时的jamming signal是怎么传过去的)（解答：bnh也不知道，那就是不考罢，哎……）
发送干扰信号后，等待一段随机时间（称为退避，backoff），然后尝试再次发送（回到第一步）。

CSMA/CD的一个例子：

补一下：看一下中文书的这一段

数据链路层的视角——拓补和交换

五星级中的五星级

基本拓补形式

Star拓补

Star拓补中这个中心节点有三种：Hub， switch，repeater。这三种设备工作在不同的层。工作的效果也不一样。

HUB（集线器）:物理层设备

HUB集线器属于纯硬件网络底层设备，基本上不具有类似于交换机的“智能记忆”能力和“学习”能力。它也不具备交换机所具有的MAC地址表，所以它发送数据时都是没有针对性的，而是采用广播方式发送。也就是说当它要向某节点发送数据时，不是直接把数据发送到目的节点，而是把数据包发送到与集线器相连的所有节点。因此，HUB下依旧需要使用CSMA/CD协议。

Bridge

Brige是一个

路由

拓补

（spanning Tree）

MAC帧的结构（要求掌握！五星级）

MAC地址用于唯一标明终端。理论上来说它不可改变，但是现在有技术可以在发送时使用虚拟的MAC地址。携带MAC地址的DPU如上图所示

Address Learning

在MAC地址下，当机器携带MAC地址开始发送信息时，交换设备就会知道：“这个MAC地址的机器在我的某个端口上”。就会将它加入自己的路由数据库。

但是这个有一个问题，假设B是新加入的。$\alpha$和$\beta$都没有对B的位置进行注册。此时，A朝B发送一个帧，首先$\alpha$和$\beta$都会收到并认为A在下方，假设$\alpha$先转发，$\alpha$转发的帧会被B同时被B和$\beta$收到，$\beta$就会认为A在B侧；同理，后续$\beta$转发的也会被A，此时$\alpha$会记录A在B侧。这样就出问题了，假设B要发生一个返回给A，那么此时无论是$\alpha$还是$\beta$都认为AB在同侧，都不进行转发。

在设计Spanning Tree 算法时，需要避免这样的逻辑环路。

点对点协议（PPP）

PPP：Point-to-point Protocol

连接数据链路层与网络层的协议——Address Resolution Protocol (ARP)

(ARP高速缓存是什么东西，要求理解)

（ARP的四个步骤要求掌握）

这是用来处理MAC地址和IP地址关系的协议。由于IP协议使用了ARP协议，因此常常将ARP协议划归网络层。有些地方也将其划归数据链路层，因为ARP消息直接封装MAC帧内，而非IP包。ARP本质是跨接地三层和第二层的协议。

在局域网中，交换机和其对应的MAC地址工作在数据链路层（第二层），而IP工作在网络层（第三层）。

在一个网络中：(这个流程要求记住)

在局域网内，Router存储有一个路由表，将各个设备的IP地址与MAC地址相映射。如果要转发的IP包的MAC地址已经在表中，则直接将其发送到对应端口上。
如果需要传输给一个已知IP地址，未知MAC地址的设备。那么路由将暂存这一帧数据，直接使用ARP在LAN上进行广播“我的IP是：xxx，硬件地址是：xxx，我想知道IP地址xxx的MAC地址”，寻找到对应IP地址的设备，让它回应自己的MAC。拿到MAC后再封包发送。
当局域网内的设备发现ARP请求的IP和自己的IP地址匹配时，则应答，应答消息包含自己的IP地址和MAC地址，单播发送给请求站点。
ARP 消息还可以简单地用于广播主机的 IP 地址和子网地址，以便让LAN上的其他设备可以获取。

现在介绍的ARP和IP，都是在同一个局域网上的。那如果你身在重庆，但是要和北京的一个设备通信，那这时候又如何解决呢？ARP协议仅能在一个广播域内进行查询，而这个广播域是通过IP地址划分的（同一网段IP）。

路由器在收到数据时会将目标IP与局域网IP检查一下，如果发现不为同一网段，则会请求网关IP地址的MAC
然后将这一帧数据朝网关发送，辅助网络完成下一跳。

课堂问题:

交换机每个端口需要配备自己的MAC地址吗？

不需要。因为交换机工作在第二层，只看你请求的MAC是否再它已知的端口上，如果是，则朝特定端口发送；如果不是，则朝口上广播或朝特定端口发送。

路由器的每个端口需要自己的MAC地址吗？

需要。因为路由器工作在第三层，每个端口连接不同的局域网。正如上面ARP所说，需要朝路由器的某个端口发送ARP请求，将包发给这个端口，再由这个端口根据路由协议转发至另外的路由端口。

如果大家折腾一下软路由OpenWRT系统就会发现，那里面有一张路由表。这就是由ARP协议请求出来的。表上记录了每个设备的MAC、IP、端口。此时会发现，这个路由器竟然只有两个端口！

其实这是由于家用路由器的路由端口只有2个导致的，平时路由器会看到一个WAN口加数个LAN口，这些LAN口之间都工作在第二层，公用一个MAC和IP；WAN口有一个MAC和IP。我们访问路由器的后台其实就是在访问路由器LAN口的IP地址。