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! 链路层实现 以太网 点对点协议PPP 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: MPLS 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 链路层服务（续） 流量控制: 差错检测: 差错纠正（有些提供）: 半双工和全双工： 调节发送速度，避免接收节点缓存溢出
可以与可靠交付（如GBN、SR）集成，也可以是单独的机制 差错检测: 检测传输错误 差错纠正（有些提供）: 检测并纠正传输错误（不是通过重传） 半双工和全双工： 半双工通信时，提供收/发转换 5: DataLink Layer

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

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

11 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: MPLS 5.6 data center networking 5.7 a day in the life of a web request Link Layer

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

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

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

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

16 奇偶校验 单比特奇偶校验: 检测单比特错误 二维奇偶校验: 检测和纠正单比特错误 5: DataLink Layer

17 循环冗余校验（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码检错能力极强，可用硬件实现，是应用最广泛的检错码。

18 CRC生成多项式标准 四个多项式已成为国际标准 硬件实现CRC校验 CRC-12 = x12 + x11 + x3 + x2 + x + 1
CRC-CCITT = x16 + x12 + x5 + 1 CRC-32 硬件实现CRC校验 网卡NIC（Network Interface Card）

19 循环码性质 ⑴由任何多于一项的生成多项式g(x)产生的循环码能够检测所有单个错误；
⑵每个被(1+x)除尽的多项式都具有偶数项。若生成多项式g(x)具有偶数项，则由它产生的编码就能检测所有奇数个错误； ⑶若码长n不大于生成多项式g(x)的指数e(即n≤e)，则由g(x)产生的码能够检测所有单个和两个错码； g(x)的指数e：e是使g(x)能除尽xe+1的最小正整数；

20 循环码性质 ⑷若码长n不大于g1(x)的指数，则由生成多项式g(x)=(x+1)g1(x)产生的码能检测所有单个、两个及三个错误；
⑸由(n-m)次多项式产生的任一循环码，能检测所有长度不超过(n-m)的突发错误； ⑹ 长度为b>(n-m)的突发错误中： 若b=n-m+1，则不能检测部分占2 -(n-m-1) ； 若b>n-m+1，则不能检测部分占2 -(n-m) 。

21 循环码性质示例 CRC-16、CRC-CCITT可以检测所有单个错码(性质1)；奇数个错码(性质2)；2个错码(性质3)；长度不大于16的突发错码(性质5)；99.997%[=(1-2-15)]长为17的突发错码、99.998%[=(1-2-16)] 更长的突发错码(性质6) Note: 17=n-m+1=16+1 15=n-m-1=16-1 16=n-m=16

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

23 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: MPLS 5.6 data center networking 5.7 a day in the life of a web request Link Layer

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

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

26 理想的多址接入协议 在速率为R bps的广播信道上 1. 当只有一个节点发送时，它应能以速率R发送
2. 当有M个节点发送时，每个节点应能以 R/M的平均速率发送 3. 协议是完全分布式的: 不需要一个特殊的节点来协调发送 不需要时钟或时隙同步 4. 简单 5: DataLink Layer

27 MAC协议的分类 信道划分 随机接入 轮流使用信道 将信道划分为若干子信道，每个节点固定分配一个子信道，不会发生冲突。
不划分信道，节点可自行决定何时发送； 允许出现冲突，发生冲突后设法恢复。 轮流使用信道 不划分信道，有数据要发送的节点在信道上轮流发送，不会出现冲突。 5: DataLink Layer

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

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

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

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

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

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

34 时隙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

35 Pure ALOHA 基本思想： 发生冲突的情形： 任何节点有数据发送就可以立即发送 节点通过监听信道判断本次传输是否成功
若不成功，立即以概率P重传，以概率（1-P）推迟至下一个帧时 发生冲突的情形： 在时刻t0发送的帧与在 [t0-1,t0+1] 时段内发送的其它帧冲突 5: DataLink Layer

36 纯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

37 载波侦听多址接入（CSMA） 发送前监听信道： 冲突仍可能发生: 信道空闲: 发送整个帧 信道忙：推迟发送
由于存在传输延迟，节点可能没有监听到其它节点正在发送 一旦发生冲突，整个帧传输时间被浪费 5: DataLink Layer

38 CSMA/CD (Collision Detection)
通过测量收到的信号强度检测冲突（冲突信号的强度较大） 检测到冲突后立即停止传输损坏的帧（减少信道浪费） 5: DataLink Layer

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

40 以太网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

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

42 轮流MAC协议—轮询 主节点轮流“邀请”从节点发送 缺点: 引入轮询延迟 单点失效（主节点） 主节点 从节点 data poll data
5: DataLink Layer

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

44

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

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

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

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

49 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: MPLS 5.6 data center networking 5.7 a day in the life of a web request Link Layer

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

51 每个适配器有一个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

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

53 向同一个网络中的节点发送 在同一个物理网络上，数据报如何从一个节点到达另一个节点？ 问题：
发送节点的网络层将数据报和接收节点的物理地址交给数据链路层 数据链路层将数据报封装在一个链路层帧中，在物理网络上发送 接收主机的适配器收到帧，判断是发给本机的，取出数据报交给网络层 问题： 发送节点如何获得接收节点的物理地址？ 帧如何到达接收节点？

54 地址解析（Address Resolution）
发送节点的网络层知道接收节点的IP地址，如： 源主机知道源路由器的IP地址（缺省路由） 中间路由器知道下一跳的IP地址（查找转发表） 目的路由器知道目的主机的IP地址 问题： 发送节点已知接收节点的IP地址，想获得接收节点的MAC地址 地址解析： 获得与IP地址对应的MAC地址

55 地址解析的方法 静态映射IP地址-MAC地址的缺点： 地址解析协议用于动态获得IP地址-MAC地址映射：
主机每次使用的IP地址可能不同（DHCP） 主机可能更换网卡 地址解析协议用于动态获得IP地址-MAC地址映射： 若节点A希望获得节点B的MAC地址，节点A广播一个包含B的IP地址的地址解析请求 节点B用自己的MAC地址进行响应

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

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

58 改进ARP的措施－ARP缓存 每个节点在内存中维护一个地址映射（绑定）表，称ARP表。
每次发送数据报前先查询ARP缓存，找不到需要的地址映射再发送ARP请求进行查询，并在收到ARP响应后将地址绑定缓存到ARP表中。 ARP缓存中的信息动态更新，并在超时（一般为15～20分钟）后删除。

59 改进ARP的措施（续） 从ARP请求中获取地址绑定信息： 节点在启动时自动广播自己的地址绑定：
节点A在启动时主动广播一个ARP请求，在目标字段内填入自己的IP地址。 收到ARP请求的节点将A的地址绑定保存在自己的ARP表中。 若A收到ARP响应，报告IP地址重复错误。

60 数据报如何从源主机到达目的主机 数据报从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

61 R A创建IP数据报，src IP＝A, dest IP＝B A查找转发表，得到下一跳地址 111.111.111.110
A利用ARP获得下一跳 对应的MAC地址（R-1） A创建链路层帧，封装IP数据包，src MAC =A, dest MAC = R-1，发送 R接收帧，取出IP数据报，发现目的地址为B R查找转发表，得知B在其端口R-2的直连网络上 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

62 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: MPLS 5.6 data center networking 5.7 a day in the life of a web request Link Layer

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

64

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

66 交换式以太网 星型拓扑： 交换式以太网是无冲突的！ 今天的以太网采用基于交换机的星型拓扑 各节点仅与中心节点直接通信，各节点之间不直接通信。
主机通过双绞线或光纤连接到交换机 交换机在端口之间存储－转发帧 交换式以太网是无冲突的！ 星型拓扑： 各节点仅与中心节点直接通信，各节点之间不直接通信。 switch 5: DataLink Layer

67 如果没有源和目的地址间的冲突，其总带宽为n*10 Mb/s
交换机能够增加总带宽 该交换机通过处理帧的MAC地址，从一个输入端向一个或多个输出端转发分组，增加了网络总带宽 一个单个的以太网段只能提供100 Mpbs的带宽，若输入与输出主机两两不同的话，则以太网交换机可提供100×n/2 Mpbs的带宽（n为交换机上的输入和输出端口数目) 如果没有源和目的地址间的冲突，其总带宽为n*10 Mb/s 此时这些主机之间能够同时进行双工通信，而不会相互干扰 67

68 碰撞域 vs. 广播域 碰撞域描述了一组共享网络访问媒体的网络设备覆盖的区域 广播域是指广播分组直接到达的区域
红色箭头表示冲突域，当然也是广播域 广播域是指广播分组直接到达的区域 若LAN交换机未划VLAN，它是一个广播域 (a)传统的共享式10 Mb/s以太网 (b)交换式局域网，每个端口具有10 Mb/s 10 Mb/s 68 陈鸣：网络工程设计 解放军理工大学计算机系

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

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

71 检测冲突需要的最大时间

72 为什么有最小帧长的要求？ 为确保发送节点在发送结束前检测到冲突，帧的发送时间必须足够长。
若信号在以太网上相距最远的两个适配器之间的往返延迟为2τ，那么帧的发送时间不应小于2τ，即帧的最小长度≧链路速率×2τ。 以太网标准规定最小帧长为64字节（不包括前导码），这个长度足以保证在10Mbps的最大直径以太网中，发送节点可在完成发送前检测到可能的冲突。

73 802.3以太网标准: 链路层 & 物理层 存在许多不同的以太网技术：
链路层：MAC协议，帧格式，帧处理 物理层： 传输介质: 光纤，同轴电缆，双绞线 速度: 如10Mbps, 100 Mbps, 1Gbps, … 编码方式 所有这些以太网技术由IEEE 802.3工作组标准化，形成IEEE 802.3标准族 5: DataLink Layer

74 DIX以太帧与802.3帧 最早提出的以太帧称为DIX（DEC-Intel-Xerox）以太帧： 802.3帧结构：
类型：指出处理数据域的协议实体 802.3帧结构： 长度：替代DIX帧中的类型域，指出数据域的长度。 这两种格式都可使用，当类型/长度域的值大于1500时解释为类型域，否则解释为长度域

75 共享式以太网的问题 在有N个节点的系统中，每个节点平均只能获得总带宽的1/N 当网络中有较多活跃节点时，频繁冲突导致网络性能很低
冲突域：竞争广播信道的一组节点构成一个冲突域 共享式以太网中所有节点位于同一个冲突域中

76 交换式以太网的优点 交换式以太网将信道“共享”变为“独享”： 网络的集合带宽为各个交换机端口的带宽之和
每个节点通过专用链路连到交换机的一个端口 交换机为每个端口提供专用的带宽 交换机的每个端口为一个冲突域（不同端口的发送互不影响） 网络的集合带宽为各个交换机端口的带宽之和 随着端口的增多，网络吞吐量增加，即使网络负载很重也不会导致网络性能下降 交换式以太网从根本上解决了网络规模与网络性能的矛盾

77 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: MPLS 5.6 data center networking 5.7 a day in the life of a web request Link Layer

78 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

79 自主学习 交换机自主学习“哪个主机通过哪个端口可达”：
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

80 转发和扩散 目的地址A’未知: 扩散 目的地址A已知: 按照转发表转发 A A A’ C’ B 1 2 6 3 A A’ A A’ A A’
Source: A Dest: A’ A A A’ C’ B 目的地址A’未知: 扩散 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

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

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

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

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

85 Institutional network
mail server to external network web server router IP subnet Link Layer

86 交换机 vs. 路由器 均为存储-转发设备： 内部都有转发表： 交换机是即插即用设备 路由器需要手工配置
交换机工作于链路层，根据MAC地址存储转发帧 路由器工作于网络层，根据IP地址存储转发数据报 内部都有转发表： 交换机：使用“逆向学习法”学习转发表 路由器：运行选路协议计算转发表 交换机是即插即用设备 路由器需要手工配置 5: DataLink Layer

87 交换机 vs. 路由器 交换机转发速度快，成本低（二层设备） 路由器转发速度慢，成本高（三层设备）
交换机不能连接异构链路（即MAC协议不同的网络） 路由器可以连接异构链路（重新封装链路层帧） 交换机不能阻断广播帧的传播：交换机会扩散所有的广播帧，从而通过交换机连接的所有主机在同一个广播域中 路由器可以阻数广播帧的传播：每个路由器端口是一个独立的广播域

88 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: MPLS 5.6 data center networking 5.7 a day in the life of a web request Link Layer

89 虚拟局域网: motivation 流量隔离的需要： 若用路由器隔离流量： 广播流量（如ARP）跨越整个局域网 安全/隐私问题
增加路由器成本 降低交换机使用效率 网络重配置困难 Computer Science Computer Engineering Electrical Engineering Link Layer

90 虚拟局域网（VLAN）的基本概念 在一个物理局域网上，利用软件定义出若干个虚拟局域网 每个VLAN在逻辑上是一个独立的IP子网：
每个VLAN是一个单独的广播域，一个VLAN中的所有帧流量被限制在该VLAN中 不同VLAN之间的通信要依赖于网络层路由

91 VLANs port-based VLAN: switch ports grouped so that single physical switch …… 1 7 9 15 2 8 10 16 流量隔离: frames to/from ports 1-8 can only reach ports 1-8 … … Electrical Engineering (VLAN ports 1-8) Computer Science (VLAN ports 9-15) Electrical Engineering (VLAN ports 1-8) … 1 8 2 7 9 16 10 15 Computer Science (VLAN ports 9-16) … operates as multiple virtual switches Link Layer

92 Electrical Engineering
Port-based VLAN router VLANS之间的转发: done via routing (just as with separate switches) 动态成员管理: ports can be dynamically assigned among VLANs 1 7 9 15 2 8 10 16 … … Electrical Engineering (VLAN ports 1-8) Computer Science (VLAN ports 9-15) Link Layer

93 Electrical Engineering
VLAN可以跨越多个交换机 1 7 9 15 16 1 3 5 7 2 8 10 2 4 6 8 … … Electrical Engineering (VLAN ports 1-8) Computer Science (VLAN ports 9-15) Ports 2,3,5 belong to EE VLAN Ports 4,6,7,8 belong to CS VLAN trunk port: carries frames between VLANS defined over multiple physical switches Link Layer

94 VLAN的划分方法 基于交换机端口划分VLAN： 基于MAC地址划分VLAN： 基于IP地址划分VLAN：

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

96 交换机如何在VLAN间转发帧？ 当一个帧到达时， 交换机判断该帧属于哪个VLAN 查找转发表得到该VLAN对应的端口
5: DataLink Layer

97 如何知道一个帧属于哪个VLAN？ 根据帧的到达端口、源MAC地址或源IP地址（由VLAN的划分方法确定），查找VLAN的配置表获悉

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

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

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

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

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

103 点到点协议：PPP协议 PPP是因特网中广泛使用的点到点数据链路协议，用于PC机到因特网的拨号连接，以及路由器到路由器之间的专线连接。

104 PPP协议的组成 PPP由以下三部分组成： 一种在串行通信线路上的组帧方式，用于区分帧的边界，并支持差错检测。
一个用于建立、配置、测试和拆除数据链路的链路控制协议LCP。 一组网络控制协议（NCP），用以支持不同的网络层协议。

105 PPP帧格式 PPP帧格式： Flag: 帧边界 Address: 总是0xFF（点-点线路） Control: 总是0x03
Protocol: 指出载荷字段中携带的是哪类分组 Info：载荷字段 Check：CRC校 验 5: DataLink Layer

106 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

107 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

108 The Internet: virtualizing networks
Internetwork layer (IP): 编址: 互联网络看起来像一个统一的网络，尽管下层的物理网络很不相同 network of networks 网关: 将IP包封装在本地网络分组中 在网际层上选路到下一个网关 gateway ARPAnet satellite net 5: DataLink Layer

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

110 Chapter 5: Summary 数据链路层服务原理： 链路层技术实例： 差错检测与纠正 共享广播信道：多址技术 链路层编址 以太网
交换式以太网，VLAN PPP 5: DataLink Layer