Chapter 5 Link Layer Computer Networking: A Top Down Approach 6th edition Jim Kurose, Keith Ross Addison-Wesley March 2012 A note on the use of these.

Presentation on theme: "Chapter 5 Link Layer Computer Networking: A Top Down Approach 6th edition Jim Kurose, Keith Ross Addison-Wesley March 2012 A note on the use of these."— Presentation transcript:

1 Chapter 5 Link Layer Computer Networking: A Top Down Approach 6th edition Jim Kurose, Keith Ross Addison-Wesley March 2012 A note on the use of these ppt slides: We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you see the animations; and can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: If you use these slides (e.g., in a class) that you mention their source (after all, we’d like people to use our book!) If you post any slides on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material. Thanks and enjoy! JFK/KWR All material copyright J.F Kurose and K.W. Ross, All Rights Reserved Link Layer

2 Chapter 5: The Data Link Layer
Our goals: 理解数据链路层服务原理: 差错检测和纠正 共享广播信道: 多址接入 链路层编址 可靠传输、流量控制：done! 链路层实现 以太网 虚拟局域网 5: DataLink Layer

3 Link layer, LANs: outline
5.1 introduction, services 5.2 error detection, correction 5.3 multiple access protocols 5.4 LANs addressing, ARP Ethernet switches VLANS 5.5 link virtualization 5.6 data center networking 5.7 a day in the life of a web request Link Layer

4 网络层和链路层的关系 网络层: 链路层： 选路：路由器确定去往目的节点的下一跳 转发：在路由器内部将数据报从输入端口转移到输出端口
将数据报从一个节点传输到相邻的下一个节点，如： 源主机 -> 源路由器 路由器 -> 下一跳路由器 目的路由器-> 目的主机 5: DataLink Layer

5 一些术语 节点：主机和路由器统称为节点 链路：连接相邻节点的通信信道 帧：链路层分组称为帧 有线链路 无线链路 局域网
5: DataLink Layer

6 链路层服务 组帧（基本服务） 链路接入（广播链路需要） 差错检测（基本服务） 差错纠正（有些提供）: 从原始比特流中提取出完整的帧
在广播信道上协调各个节点的发送行为 差错检测（基本服务） 检测传输错误 差错纠正（有些提供）: 检测并纠正传输错误（不使用重传） 5: DataLink Layer

7 链路层服务（续） 可靠交付（部分协议提供） 流量控制: 半双工和全双工：
通过确认、重传等机制确保接收节点正确收到每一个帧（停-等、GBN、SR） 低误码率链路（如光纤、某些双绞线）上很少使用，高误码率链路（如无线链路）应当使用 流量控制: 调节发送速度，避免接收节点缓存溢出 提供可靠交付的链路层协议，不需要专门的流量控制 不提供可靠交付的链路层协议，需要有流量控制机制 半双工和全双工： 半双工通信时，提供收/发转换 5: DataLink Layer

8 链路层在哪儿实现？ 路由器：链路层在线卡中实现 主机：链路层主体部分在网络适配器（网卡）中实现
网络适配器连接物理媒体，所以还实现物理层的功能 链路层由硬件和软件实现： 网卡中的控制器芯片：组帧、链路接入、检错、可靠交付、流量控制等 主机上的链路层软件：与网络层接口，激活控制器硬件、响应控制器中断等 host schematic application transport network link physical cpu memory host bus (e.g., PCI) controller physical transmission network adapter card 5: DataLink Layer

9 网络适配器之间的通信 发送侧: 接收侧： 将数据报封装到帧中 提取帧，检测传输错误 生成校验比特 执行可靠传输和流量控制
datagram datagram controller controller sending host receiving host datagram frame 发送侧: 将数据报封装到帧中 生成校验比特 执行可靠传输和流量控制 接收侧： 提取帧，检测传输错误 执行可靠传输和流量控制 解封装数据报，交给上层协议 5: DataLink Layer

10 Link layer, LANs: outline
5.1 introduction, services 5.2 error detection, correction 5.3 multiple access protocols 5.4 LANs addressing, ARP Ethernet switches VLANS 5.5 link virtualization 5.6 data center networking 5.7 a day in the life of a web request Link Layer

11 检错和纠错 传输出错的类型 差错控制编码的类型 单个错：由随机的信道热噪声引起，一次只影响1位
突发错：由瞬间的脉冲噪声引起，一次影响许多位，使用突发长度表示突发错影响的最大数据位数 差错控制编码的类型 检错码：只能检测出传输错误的编码，不能确定出错位置，通常与反馈重传机制结合进行差错恢复 纠错码：能够确定错误位置并自行纠正的编码

12 如何检测与纠正错误？ 码字（codeword）：由 m 比特的数据加上 r 比特的冗余位（校验位）构成
检错：若收到的码字为无效码字，判定出现传输错误 海明距离（Hamming Distance）：两个码字的对应位取值不同的位数 纠错：将收到的无效码字纠正到距其最近的有效码字 检错码与纠错码的能力都是有限的！

13 编码集的检错与纠错能力 编码集的海明距离：编码集中任意两个有效码字的海明距离的最小值
检错能力：为检测出所有d比特错误，编码集的海明距离至少应为d+1 纠错能力：为纠正所有d比特错误，编码集的海明距离至少应为2d+1

14 差错检测的实施 发送端对要保护的数据D（包括帧头字段）生成校验 位EDC，添加在帧头中
接收端对收到的数据D’计算校验位EDC’，根据EDC’判 定是否有错 5: DataLink Layer

15 奇偶校验 二维奇偶校验: 单比特奇偶校验: 可检测2比特错和纠正单比特错 编码集海明距离为3 有利于检测突发错误 可检测单比特错误
检错率为50% 编码集海明距离为2 5: DataLink Layer

16 循环冗余校验（CRC） CRC是一种多项式编码，它将一个位串看成是某个一元多项式的系数，如1011看成是一元多项式X3 + X + 1的系数
信息多项式M(x)：由m个信息比特为系数构成的多项式 冗余多项式R(x)：由r个冗余比特为系数构成的多项式 码多项式T(x)：在m个信息比特后加上r个冗余比特构成的码字所对应的多项式，表达式为T(x) = xr·M(x) + R(x) 生成多项式G(x)：双方确定用来计算R(x)的一个多项式 编码方法：R(x) = xr·M(x) ÷ G(x) 的余式（减法运算定义为异或操作） 检验方法：若T(x) ÷G(x)的余式为0，判定传输正确 CRC码检错能力极强，可用硬件实现，是应用最广泛的检错码

17 CRC举例 例1：取G(X) = X3 + 1，对信息比特101110计算CRC码。 解答：
÷1001的余式为R=011 (CRC code) 码字： 例2：取G(X) = X3 + 1，接收端收到比特串 ，问是否有错？ ÷1001的余式为001（不为0），有传输错误。 5: DataLink Layer

18 Link layer, LANs: outline
5.1 introduction, services 5.2 error detection, correction 5.3 multiple access protocols 5.4 LANs addressing, ARP Ethernet switches VLANS 5.5 link virtualization 5.6 data center networking 5.7 a day in the life of a web request Link Layer

19 (shared air, acoustical)
链路的两种类型 点到点链路： 仅连接了一个发送方和一个接收方的链路 一条全双工链路可以看成是由两条单工链路组成 广播链路： 连接了许多节点的单一共享链路，任何一个节点发送的数据可被链路上的其它节点接收到 humans at a cocktail party (shared air, acoustical) 共享的电缆 （如早期以太网） 共享的无线射频 （如 WiFi） 共享的无线射频 （如卫星） 5: DataLink Layer

20 多址接入（Multiple Access）
冲突（collision） 在广播链路上，若两个或多个节点同时发送，发送的信号会发生干扰，导致接收失败 多址接入协议 规定节点共享信道（谁可以发送）的方法 多址接入协议也称媒体接入控制（Medium Access Control，MAC）协议 5: DataLink Layer

21 理想的多址接入协议 在速率为R bps的广播信道上 1. 当只有一个节点发送时，它应能以速率R发送（信道利用率高）
2. 当有M个节点发送时，每个节点应能以 R/M的平均速率发送（公平性好） 3. 协议是完全分布式的: 不需要一个特殊的节点来协调发送（健壮性好） 不需要时钟或时隙同步（不需要额外的机制） 4. 简单（实现和运行开销小） 5: DataLink Layer

22 MAC协议的分类 信道划分 随机接入（竞争） 轮流使用信道 将信道划分为若干子信道，每个节点固定分配一个子信道，不会发生冲突
关注公平性，轻负载时信道利用率不高 随机接入（竞争） 不划分信道，每个节点自行决定何时发送，出现冲突后设法解决 提高轻负载时的信道利用率，但重负载时冲突严重 轮流使用信道 不划分信道，有数据的节点轮流发送，不会出现冲突 信道利用率是以上两种方法的折衷 5: DataLink Layer

23 （1）信道划分的MAC协议 TDMA: 时分多址
将信道的使用时间划分成帧，每个节点在帧中被分配一个固定长度的时间片，每个时间片可以发送一个分组 节点只能在分配给自己的时间片内发送 若节点不发送，其时间片轮空 6-slot frame 1 3 4 1 3 4 5: DataLink Layer

24 信道划分的MAC协议 FDMA: 频分多址 将信道频谱划分为若干子频带 每个节点被分配一个固定的子频带 若节点不发送，其子频带空闲 time
frequency bands FDM cable 5: DataLink Layer

25 信道划分的MAC协议 CDMA: 码分多址 CDMA允许所有节点同时使用整个信道！ 将每个比特时间进一步划分为m个微时隙（称chip）
每个节点被分配一个惟一的m比特码序列（称chip code） 发送方编码：发送“1”=发送chip code；发送“0”=发送chip code的反码 信号叠加：多个节点发送的信号在信道中线性相加 接收方解码：用发送方的chip code与信道中收到的混合信号计算内积，恢复出原数据 前提条件：任意两个chip code必须是相互正交的 CDMA允许所有节点同时使用整个信道！ 5: DataLink Layer

26 （2）随机接入的MAC协议 随机接入的基本思想： 随机接入MAC协议的例子： 当节点有数据要发送时，以信道速率R发送，发送前不需要协调
发送前不监听信道：ALOHA家族 发送前监听信道：CSMA家族 5: DataLink Layer

27 时分（Slotted） ALOHA 假设: 操作: 所有帧长度相同 节点从上层收到数据后，在下一个时隙发送
时间被划分为等长的时隙，每个时隙传一帧 节点只能在时隙开始时发送 节点是时钟同步的（知道时隙何时开始） 所有节点可在时隙结束前检测到是否有冲突发生 操作: 节点从上层收到数据后，在下一个时隙发送 若时隙结束前未检测到冲突，节点可在下一个时隙发送新的帧 若检测到冲突，节点在随后的每一个时隙中以概率P重传，直至发送成功 5: DataLink Layer

28 时分ALOHA 优点 缺点 单个活跃节点可以信道速率连续发送 发生冲突的时隙被浪费了 由于概率重传，有些时隙被闲置
分布式：节点自行决定什么时候发送 简单 缺点 发生冲突的时隙被浪费了 由于概率重传，有些时隙被闲置 需要时钟同步 5: DataLink Layer

29 时分Aloha的效率 最佳情况: 信道用于有效传输的时间仅为37%！ 效率：当网络中存在大量活跃节点时，长期运行过程中成功时隙所占的比例
最大效率: 找到令Np(1-p)N-1最大的概率p* 代入Np*(1-p*)N-1，并令N趋向于无穷，得到： 最大效率 = 1/e = 0.37 假设: 有N个活跃节点，每个节点在每个时隙开始时以概率P发送 给定节点在一个时隙中发送成功的概率 = p(1-p)N-1 给定时隙中有节点发送成功的概率 = Np(1-p)N-1 最佳情况: 信道用于有效传输的时间仅为37%！ 5: DataLink Layer

30 纯ALOHA 基本思想： 发生冲突的情形： 取消同步时钟，任何节点有数据发送就可以立即发送 节点通过监听信道判断本次传输是否成功
若不成功，立即以概率P重传，以概率（1-P）等待一个帧时后再决定。（帧时：发送一帧的时间，假设帧长度相同） 发生冲突的情形： 在时刻t0发送的帧与在 [t0-1,t0+1] 时段内发送的其它帧冲突 5: DataLink Layer

31 纯Aloha的效率 P(给定节点发送成功) = P(节点发送) . P(无其它节点在[t0-1,t0]内发送) .
= p . (1-p)N-1 . (1-p)N-1 = p . (1-p)2(N-1) 求出令节点发送成功概率Np . (1-p)2(N-1)最大的p*，并令N -> infty: 最大效率 = 1/(2e) = 0.18 5: DataLink Layer

32 载波侦听多址接入（CSMA） 发送前监听信道（carrier sensing）： 冲突仍可能发生: 信道空闲：发送整个帧 信道忙：推迟发送
由于存在传输延迟，节点可能没有监听到其它节点正在发送 即使忽略传输延迟，当两个（或多个）节点同时发现信道由忙变为空闲、并都决定立即发送时，仍会发生冲突 5: DataLink Layer

33 CSMA/CD (Collision Detection)
若在发送的过程中检测到冲突，怎么办？ 继续发送余下的部分（浪费带宽） 停止发送余下的部分 CSMA/CD的基本思想： 在发送的过程中检测冲突（发生冲突时信号较强） 检测到冲突后，立即停止发送剩余的部分 立即启动冲突解决的过程 5: DataLink Layer

34 以太网MAC协议 以太网采用CSMA/CD协议: NIC从网络层接收数据报，构造以太帧
5: DataLink Layer

35 以太网MA协议（续） 5. NIC进入指数回退阶段，选择一个等待时间: 6. 返回Step 2 指数回退的目的是根据网络负载调整重传时间：
第一次冲突后: 从{0,1}中选择K，延迟K· 512比特时间 第二次冲突后: 从{0,1,2,3}中选择K，…… 第三次冲突后: 从{0,1,2,3,4,5,6,7}中选择K，…… …… 第10次冲突后，从{0,1,2,3,4,…,1023}中选择K，…… 6. 返回Step 2 指数回退的目的是根据网络负载调整重传时间： 负载越重（冲突次数越多），重传时间的选择范围越大，再次发生冲突的可能性越小 5: DataLink Layer

36 CSMA/CD的效率 结论：应控制以太网的规模 Tprop = 以太网中任意两个节点之间传播延迟的 最大值
ttrans = 最长帧的传输时间 在以下情况下，以太网的效率趋近于1： tprop 趋近于 0，或 ttrans 趋向于无穷 结论：应控制以太网的规模 5: DataLink Layer

37 （3）轮流MAC协议 轮询 主节点轮流“邀请”从节点发送，邀请到的从节点允许发送 缺点: 引入轮询延迟 单点失效（主节点） 主节点 从节点
data poll 主节点 data 从节点 5: DataLink Layer

38 轮流MAC协议 令牌传递 缺点： 网络中有一个令牌，按预定顺序在节点间传递 获得令牌的节点可以发送 发送完数据后释放令牌 令牌传递延迟
单点失效（令牌） T (nothing to send) T data 5: DataLink Layer

39 MAC协议小结 按照时间、频率、编码划分信道： 随机接入： 轮流访问： 时分多址，频分多址，码分多址
纯ALOHA, S-ALOHA（ALOHA网络） CSMA/CD（早期以太网） CSMA/CA（802.11）（第6章） 轮流访问： 中心节点轮询（蓝牙） 令牌传递（FDDI，IBM令牌环，令牌总线） 5: DataLink Layer

40 MAC协议比较 信道划分MAC协议: 随机接入MAC协议： 轮流协议（试图权衡以上两者）： 重负载下高效：没有冲突，节点公平使用信道
轻负载下低效：即使只有一个活跃节点也只能使用1/N的带宽 随机接入MAC协议： 轻负载时高效：单个活跃节点可以使用整个信道 重负载时低效：频繁发生冲突，信道使用效率低 轮流协议（试图权衡以上两者）： 按需使用信道（避免轻负载下固定分配信道的低效） 消除竞争（避免重负载下的发送冲突） 5: DataLink Layer

41 Next: LAN technologies
Data link layer so far: 服务 差错检测 多址接入 Next: LAN technologies 链路层编址 以太网 交换机 VLAN 5: DataLink Layer

42 局域网、城域网和广域网 局域网LAN（Local Area Network）
将小范围内的计算机及外设连接起来的网络，范围在几公里以内，通常为个人或机构所有 城域网MAN（Metropolitan Area Network ） 通常覆盖一个城市的范围（几十公里），要能支持数据、音频和视频在内的综合业务，服务质量好，支持用户数量多 广域网WAN（Wide Area Network） 通常覆盖一个国家或一个洲（一百公里以上），规模和容量可任意扩大 5: DataLink Layer

43 Link layer, LANs: outline
5.1 introduction, services 5.2 error detection, correction 5.3 multiple access protocols 5.4 LANs addressing, ARP Ethernet switches VLANS 5.5 link virtualization 5.6 data center networking 5.7 a day in the life of a web request Link Layer

44 链路层编址 每一块网络适配器（网卡）固定分配一个地址，称为物理地址、硬件地址、链路层地址、MAC地址等
MAC地址由IEEE负责分配，每块适配器的地址是全球唯一的： 网卡生产商向IEEE购买一块MAC地址空间（前3字节） 生产商确保生产的每一块网卡有不同的MAC地址 MAC地址固化在网卡的ROM中 现在用软件改变网卡的MAC地址也是可能的

45 每个适配器有一个MAC地址 Broadcast address = FF-FF-FF-FF-FF-FF LAN (wired or
1A-2F-BB AD Broadcast address = FF-FF-FF-FF-FF-FF LAN (wired or wireless) = adapter 71-65-F7-2B-08-53 58-23-D7-FA-20-B0 0C-C4-11-6F-E3-98 5: DataLink Layer

46 MAC地址类型 目的MAC地址有三种类型： 网络适配器仅将发送给本节点的帧交给主机： 若将适配器设置成混收模式，适配器将收到的所有帧交给主机
多播地址：标识一个多播组的逻辑地址，地址最高比特为1 广播地址：ff:ff:ff:ff:ff:ff 网络适配器仅将发送给本节点的帧交给主机： 目的地址为适配器MAC地址的单播帧 所有 广播帧 指定接收的多播帧 若将适配器设置成混收模式，适配器将收到的所有帧交给主机

47 如何实现直接交付？ 当发送节点A、接收节点B位于同一个物理网络上时，数据报可从A直接交付给B： 问题： 发送节点如何获得接收节点的物理地址？

48 地址解析（Address Resolution）
问题：已知IP地址，如何得到对应的MAC地址？ 静态映射IP地址-MAC地址的缺点： 主机每次使用的IP地址可能不同（DHCP） 主机可能更换网卡 地址解析协议（ARP）用于动态获得IP地址-MAC地址映射，其基本思想是： 若节点A希望获得节点B的MAC地址，节点A广播B的IP地址（地址解析请求） 节点B用自己的MAC地址进行响应

49 ARP报文格式 硬件类型：硬件接口类型。对于以太网，该值为“1”。 协议类型：高层协议地址类型。对于IP地址，该值为080016。
操作：ARP请求为1，ARP响应为2 在以太网上，ARP报文封装在以太帧中传输

50 地址解析的过程 A想知道B的MAC地址： A构造一个ARP请求，在发送方字段填入自己的MAC地址和IP地址，在目标字段填入B的IP地址。
每个收到ARP请求的节点用目标IP地址与自己的IP地址比较，地址相符的节点进行响应（B响应）。 B构造一个ARP响应，交换发送方与目标字段内容，在发送方硬件地址字段填入自己的MAC地址，修改操作字段为2 B将ARP响应封装在单播帧（目的地址为A的MAC地址）中发送。

51 IP地址为130.23.43.20、物理地址为oxB23455102210的主机，要获得IP地址为130.23.43.25的主机的MAC地址

52 改进ARP的措施：ARP缓存 每个节点在内存中维护一个地址映射（绑定）表，称ARP缓存

53 改进ARP的措施：主动学习 从ARP请求中获取地址绑定信息： 节点在启动时自动广播自己的地址映射：
节点A在启动时主动广播一个ARP请求，在目标字段内填入自己的IP地址 收到ARP请求的节点将A的地址映射缓存起来 若A收到ARP响应，报告IP地址重复错误

54 数据报如何从源主机到达目的主机 数据报从A经过R到达B： A知道下一跳地址为111.111.111.110（R-1）
R知道B从其端口R-2直接可达 R 1A-23-F9-CD-06-9B E6-E BB-4B CC-49-DE-D0-AB-7D A C-E8-FF-55 88-B2-2F-54-1A-0F B 49-BD-D2-C7-56-2A 5: DataLink Layer

55 A创建IP数据报，src IP＝A, dest IP＝B A利用ARP获得下一跳111.111.111.110对应的MAC地址（R-1）
A创建链路层帧，封装IP数据包，src MAC =A, dest MAC = R-1，发送 R接收帧，取出IP数据报，发现目的地址为B R利用ARP获得B的MAC地址 R创建链路层帧，封装IP数据报，src MAC=R-2, dest MAC = B, 发送 B的网卡接收帧，取出IP数据报，交给网络层 R 1A-23-F9-CD-06-9B E6-E BB-4B CC-49-DE-D0-AB-7D A C-E8-FF-55 88-B2-2F-54-1A-0F B 49-BD-D2-C7-56-2A 5: DataLink Layer

56 Link layer, LANs: outline
5.1 introduction, services 5.2 error detection, correction 5.3 multiple access protocols 5.4 LANs addressing, ARP Ethernet switches VLANS 5.5 link virtualization 5.6 data center networking 5.7 a day in the life of a web request Link Layer

57 以太网 第一个广泛应用的局域网技术，也是目前占主导地位的有线局域网技术 与其它的局域网技术相比，技术简单、成本低
为提高速率，以太网技术不断演化和发展 速率持续提高：10 Mbps -> 100Mbps -> 1Gbps -> 10 Gbps -> 40Gbps -> 100Gbps -> … 5: DataLink Layer

58 总线拓扑：共享式以太网 集线器（1990s后期）： 总线（1970s中期）：
以同轴电缆作为共享传输媒体（总线） 所有节点通过特殊接口连接到这条总线上 集线器（1990s后期）： 一个物理层中继器，从一个端口进入的物理信号（光，电），放大后立即从其它端口输出 集线器相当于共享电缆 双绞线 hub 总线: 同轴电缆

59 星型拓扑：交换式以太网 交换机（21世纪早期）： 星型拓扑： 交换式以太网不会产生冲突，不需使用CSMA/CD协议！
主机通过双绞线或光纤连接到交换机 交换机在端口之间存储转发帧（链路层设备） 主机与交换机之间为全双工链路 交换式以太网不会产生冲突，不需使用CSMA/CD协议！ 星型拓扑： 各节点仅与中心节点直接通信，各节点之间不直接通信 不同于基于hub的星型连接 switch 5: DataLink Layer

60 以太帧结构 Preamble（前导码）: Dest.Address/Src Address：目的/源MAC地址
7个 字节，后跟一个 字节，用于在发送方和接收方之间建立时钟同步 Dest.Address/Src Address：目的/源MAC地址 Type（2字节）: 指出Data所属的高层协议（如IP、ARP等），每个协议有一个编号 Data：46～1500字节，不足46字节填充至46字节 CRC（4字节）: 对dest addr.、src addr.、type和data四个字段计算得到的CRC码 5: DataLink Layer

61 无连接、不可靠的数据传输 无连接: 发送方NIC与接收方NIC之间没有握手 不可靠: 接收方NIC不发送确认 CRC检查出错的帧被丢弃
依靠上层协议（TCP或应用）恢复 5: DataLink Layer

62 为什么有最小帧长的要求？ 为确保节点在发送结束前检测到冲突，帧的发送时间必须足够长： 为什么最小帧长为64字节（不包括前导码）：
节点检测冲突需要时间 假设信号在相距最远的两个适配器之间的往返延迟为2τ，则帧的发送时间不应小于2τ，即帧的最小长度≧链路速率×2τ 为什么最小帧长为64字节（不包括前导码）： 根据早期以太网的最大直径（2500米）和数据速率（10Mbps）计算得到

63 检测冲突需要时间

64 802.3以太网标准: 链路层 & 物理层 历史上出现过许多不同的以太网技术：
链路层相同：MAC协议，帧格式，帧处理 物理层不同： 传输媒体: 光纤，同轴电缆，双绞线 数据速率: 如10Mbps, 100 Mbps, 1Gbps, … 物理层编码方式 所有这些以太网技术由IEEE 802.3工作组标准化，形成IEEE 802.3标准族 5: DataLink Layer

65 10Mbps以太网（早期以太网） 10Base-5： 10Base-2： 10Base-T 10Base-F
基带同轴电缆（粗），每段电缆最大长度500米 10Base-2： 基带同轴电缆（细），每段电缆最大长度约200米 10Base-T 3类双绞线和集线器，双绞线最大长度100米 10Base-F 多模光纤和集线器，光纤最大长度2000米 5: DataLink Layer

66 100Mbps以太网（快速以太网） 仅能使用光纤/双绞线，以及集线器/交换机 100Base-TX（可使用集线器或交换机）：
5类双绞线（2对），不超过100米 100Base-T4 （可使用集线器或交换机） ： 3类双绞线（4对），不超过100米 100Base-FX（只能使用交换机）： 多模光纤（2条），不超过2000米 5: DataLink Layer

67 千兆、万兆以太网 使用交换机，并增加了对流量控制的支持 1000Base-SX： 1000Base-LX：
多模光纤，不超过550米 1000Base-LX： 单模或多模光纤，不超过5000米 1000Base-CX（很少用）： 2对屏蔽双绞线，不超过25米 1000Base-T： 4对5类双绞线，不超过100米 10GBase-T： 只使用光纤，长距离用单模光纤，短距离用多模光纤 5: DataLink Layer

68 DIX以太帧与802.3帧 最早提出的以太帧称为DIX（DEC-Intel-Xerox）以太帧：
type：指出处理data域的协议实体 符合IEEE 802.3标准的帧（802.3帧）： length：替代DIX帧中的type域，指出data的长度 这两种格式都可使用，当type/length的值大于1500时解释为type，否则解释为length

69 讨论：共享式以太网和交换式以太网 共享式以太网： 交换式以太网： 集线器的所有端口位于同一个冲突域 任一时刻最多只允许一个主机发送
网络规模（节点数量）与网络性能的矛盾无法解决 交换式以太网： 交换机的每个端口为一个冲突域 多对端口可以同时通信 网络的集合带宽=各个端口的带宽之和 从根本上解决了网络规模与网络性能的矛盾 双绞线 hub

70 交换式以太网的最小帧长及规模 交换式以太网不再使用CSMA/CD协议，理论上不再需要限制帧的最小长度。但为了向后兼容，帧格式及最小帧长度的限制仍然保持不变。 由于交换式以太网不再使用CSMA/CD协议，网络直径不再受到信号最大往返时间的限制。

71 Link layer, LANs: outline
5.1 introduction, services 5.2 error detection, correction 5.3 multiple access protocols 5.4 LANs addressing, ARP Ethernet switches VLANS 5.5 link virtualization 5.6 data center networking 5.7 a day in the life of a web request Link Layer

72 switch with six interfaces
交换机如何转发？ A Q: 交换机如何知道A’通过端口4可达，而B’通过端口5可达？ A: 每个交换机内部有一张端口转发表，每个表项记录以下信息: MAC地址，到达该MAC地址的端口 Q: 转发表是如何建立和维护的？ C’ B 1 2 6 3 4 5 C B’ A’ switch with six interfaces (1,2,3,4,5,6) 5: DataLink Layer

73 自主学习 交换机自主学习“哪个主机通过哪个端口可达”：
Source: A Dest: A’ A A A’ 交换机自主学习“哪个主机通过哪个端口可达”： 当一个帧到达时，交换机从源MAC地址了解到发送节点，从帧到来的端口了解到发送节点的位置（从该端口可达） 在转发表中记录发送节点和可达端口 C’ B 1 2 6 3 4 5 C B’ A’ MAC addr interface TTL A 1 60 转发表 （初始为空） 5: DataLink Layer

74 帧的过滤和转发 当帧到来时: 1. 记录帧的到来端口 2. 用帧的目的MAC地址查找端口转发表
3. if 找到目的MAC地址 //已知节点 then { if 目的地址所在端口=帧的到来端口 then 丢弃帧 //过滤不需要转发的帧 else 转发帧到表项指定的端口 //按转发表转发帧 } else 扩散帧 //未知节点，采用扩散法转发 向输入端口以外的所有端口转发 5: DataLink Layer

75 交换机收到帧的处理过程 用帧的目的地址查找转发表（转发决策）： 用帧的源地址查找转发表（更新转发表）：
若目的地址所在端口 = 帧的进入端口，丢弃帧 若目的地址所在端口 ≠ 帧的进入端口，转发帧 若目的地址不在转发表中，扩散帧 用帧的源地址查找转发表（更新转发表）： 若找到地址，将对应表项的生存期设为最大值 若没有找到该地址，添加源地址和进入端口到转发表，设置表项的生存期为最大值

76 举例 目的地址未知: 扩散 目的地址A已知: 按照转发表转发 A A A’ C’ B 1 2 6 3 A A’ A A’ A A’ A A’
Source: A Dest: A’ A A A’ C’ B 目的地址未知: 扩散 1 2 6 3 A A’ A A’ A A’ A A’ A A’ 4 5 目的地址A已知: C 按照转发表转发 A’ A B’ A’ MAC addr interface TTL A 1 60 转发表 （初始为空） A’ 4 60 5: DataLink Layer

77 级联交换机 多个交换机也可以级联在一起，形成更大范围的局域网
D E F S2 S4 S3 H I G S1 A B C Q: 数据包要从A发往F，交换机S1如何知道应转发给S4，而S4如何知道应转发给S2？ A: 通过自主学习！（与单交换机情形相同） 5: DataLink Layer

78 举例 假设C发送一个帧给I，I响应C： Q: 给出 S1, S2, S3, S4 中的交换机表和包转发决策 S4 1 3 2 S1 1 S3
A 4 4 F D I B C G H E Q: 给出 S1, S2, S3, S4 中的交换机表和包转发决策 5: DataLink Layer

79 有环网络和生成树算法 为提高可靠性，网络中通常存在环（冗余链路），这会导致扩散的帧在网络中循环转发 使用生成树构造无环拓扑：
所有交换机运行一个生成树算法，构造一棵覆盖网络中所有主机的生成树 平时只有生成树上的交换机可在属于生成树的边上转发帧 当生成树上的交换机或链路发生故障时，启用冗余链路，重新计算生成树 5: DataLink Layer

80 交换机 vs. 路由器 交换机工作于链路层，根据MAC地址存储转发帧 路由器工作于网络层，根据IP地址存储转发数据报 交换机是即插即用设备
路由器需要手工配置 交换机转发速度快，成本低（二层设备） 路由器转发速度慢，成本高（三层设备） 5: DataLink Layer

81 交换机 vs. 路由器 交换机不能连接异构链路（即MAC协议不同的网络），因为交换机只是按原样转发帧
路由器可以连接异构链路，因为路由器需重新封装链路层帧 交换机需运行生成树算法消除冗余链路，生成树算法假设网络是扁平的，对网络中的节点总数有限制 路由器无此限制

82 交换机 vs. 路由器 冲突域： 广播域： 交换机不能阻断广播帧的传播： 路由器可以阻断广播帧的传播： 共享同一条广播链路的主机集合
交换机只能学习到单播MAC地址，所有广播帧都会扩散发送 通过交换机连接的所有主机在同一个广播域中 路由器可以阻断广播帧的传播： 路由器根据IP地址转发包（看不到MAC地址） 每个路由器端口是一个独立的广播域 冲突域： 共享同一条广播链路的主机集合 任何一个主机发送的帧（各种帧），可被冲突域中的其它主机接收到 广播域： 广播帧能够到达的主机集合 5: DataLink Layer

83 Link layer, LANs: outline
5.1 introduction, services 5.2 error detection, correction 5.3 multiple access protocols 5.4 LANs addressing, ARP Ethernet switches VLANS 5.5 link virtualization 5.6 data center networking 5.7 a day in the life of a web request Link Layer

84 虚拟局域网（VLAN） 在大型机构网络中，管理员通常按部门将用户组织到不同的网络中 管理员配置网络遇到的困难：
同一部门的人员在物理位置上可能很分散（他们的主机连接到在不同的交换机上），但是逻辑上，不同的网络可能需要隔离 用大量的路由器来分割网段，成本很高 网络设备供应商提供用软件配置网络的方法，导致虚拟局域网概念的提出

85 VLAN的基本概念 虚拟局域网VLAN： 每个VLAN在逻辑上是一个独立的网络： 划分VLAN通过软件配置完成
位于物理局域网上的一个逻辑IP子网，包含了配置为该VLAN成员的所有节点 每个VLAN在逻辑上是一个独立的网络： 每个VLAN是一个单独的广播域：一个VLAN中的所有帧流量被限制在该VLAN中 不同VLAN之间的通信要依赖于网络层路由 划分VLAN通过软件配置完成

86 使用VLAN配置网络 VLAN的实现基础是支持VLAN功能的交换机 管理员配置VLAN：

87 如何划分VLAN？ 基于交换机端口划分： 基于MAC地址划分： 基于IP地址划分： 将某些交换机端口直接、强制性地分配给某个VLAN
根据用户节点的MAC地址划分VLAN 基于IP地址划分： 根据IP子网地址划分VLAN

88 交换机如何在VLAN间转发帧？ 当一个帧到达时， 交换机判断该帧属于哪个VLAN 查找配置表得到该VLAN对应的端口
标记为G的节点属于一个VLAN，标记为W的节点属于另一个VLAN 5: DataLink Layer

89 如何知道一个帧属于哪个VLAN？ 帧所属的VLAN = 发送节点所属的VLAN
交换机根据帧的到达端口、源MAC地址或源IP地址（取决于VLAN的划分方法），查找VLAN配置表 为避免重复查找 VLAN配置表，交换机将VLAN标识放入帧头中 后续交换机通过检查帧头的VLAN标识，得知这个帧所属的VLAN

90 IEEE 802.1Q 802.1Q规定了新的以太帧格式，帧头中包含一个VLAN标签（tag），用于指明帧属于哪个VLAN

91 802.1Q 如何与已有网卡兼容？ Q：我们需要抛弃已有的以太网卡吗？ A：不用，因为只有交换机会使用VLAN字段
Q：谁来产生VLAN字段？ A：由第一个接收帧、且支持VLAN的交换机添加 VLAN字段，由路径上最后一个这样的交换机 去掉VLAN字段 Q：帧长度不够怎么办? A：802.1Q将帧的最大长度提高到1522字节

92 VLAN以太网与已有以太网共存 Transition from legacy Ethernet to VLAN-aware Ethernet. The shaded symbols are VLAN aware. The empty ones are not.

93 三层交换机和路由器 不同子网或VLAN之间通过路由器转发，太慢！ 三层交换机： 机构网络中三层交换机和路由器的使用：
具有部分路由功能、又有二层转发速度的交换机 专为加快大型局域网内部的数据交换而设计 但在安全、协议支持等方面不如专业路由器 机构网络中三层交换机和路由器的使用： 三层交换机：通常用在机构网络的核心层，连接不同的子网或VLAN 专业路由器：连接机构网络与外网

94 三层交换机为什么快？ 路由器转发IP包的过程： 三层交换机转发IP包的过程： 三层交换机转发速度快的原因：
利用ARP获得下一跳MAC地址 用下一跳MAC地址构造链路层帧，发送 三层交换机转发IP包的过程： 将以上第1、第2步的结果缓存到本地三层转发表中 用目的IP地址查找三层转发表： 1）若命中，直接用下一跳MAC地址构造链路层帧，发送 2）若未命中，执行以上第1、2、3步 三层交换机转发速度快的原因： 一次选路，多次转发

95 中国科学技术大学校园网络示意图 网络信息中心 东校区 西校区 南校区 南区汇聚节点 东区核心节点 网络中心核心节点 计算中心汇聚节点
10G CERNET 2.5G出口 网络信息中心 东校区 西校区 南校区 服务器群 超级计算平台 CNCNET 100M出口 中国科学技术大学校园网络示意图 1G 100M 2G CERNET2 CHINANET 1G出口 力三楼 力二楼 力一楼 南区教学楼 MBA中心 软件学院 南区图书馆 南区实验楼 南区学生宿舍 防火墙 西区学生宿舍 力四楼 南区汇聚节点 东区学生宿舍 行政办公楼 理化中心大楼 理化一号楼 大礼堂 微尺度 物理楼 数学楼 教一楼 教二楼 化学楼 艺术楼 出版社 东区活动中心 继续教育学院 加速器 火灾科学实验室 西区活动中心 信息学院 生命科学学院 教三楼 图书馆 电四楼 电三楼 科研楼 东区核心节点 网络中心核心节点 计算中心汇聚节点 西区核心节点 路由器 内部：核心层，汇聚层，接入层 对外：租用电信线路连接到ISP

96 Link layer, LANs: outline
5.1 introduction, services 5.2 error detection, correction 5.3 multiple access protocols 5.4 LANs addressing, ARP Ethernet switches VLANS 5.5 link virtualization 5.6 data center networking 5.7 a day in the life of a web request Link Layer

97 The Internet: virtualizing networks
1974: 多个不连通的网络 ARPAnet data-over-cable networks packet satellite network (Aloha) packet radio network 它们在以下方面不同: 编址方法 包格式 差错恢复 选路 ARPAnet satellite net "A Protocol for Packet Network Intercommunication", V. Cerf, R. Kahn, IEEE Transactions on Communications, May, 1974, pp 5: DataLink Layer

98 The Internet: virtualizing networks
在物理网络上增加一个逻辑层次（IP层） 在逻辑层上统一编址、统一包格式 互联在一起的网络看起来像一个网络 用网关连接不同的物理网络: 在逻辑层上选路到下一个网关 将IP包封装在本地网络帧中，发送到下一个网关 network of networks gateway ARPAnet satellite net 5: DataLink Layer

99 Cerf & Kahn’s Internetwork Architecture
两级编址: IP网络，物理网络 IP层提供统一的网络视图：地址，包格式 底层可以是任意的物理网络： cable satellite 56K telephone modem today: ATM, MPLS … 物理网络对于IP层是不可见的，对于IP来说物理网络只是一条虚拟链路而已！ 5: DataLink Layer

100 Chapter 5: Summary 数据链路层服务原理： 链路层技术实例： 差错检测与纠正 共享广播信道：多址技术 链路层编址 以太网
虚拟局域网 5: DataLink Layer

101 作业 实验： 提交时间： 习题： 5，8，11，13，23，24，25，26 Ethernet-ARP 11月20日
5: DataLink Layer