计算机网络-链路层和局域网

链路层和物理层
链路层的MAC协议有
信道划分协议、随即加入协议、轮询协议
LAN局域网
链路层地址,又称 LAN地址(LAN address) , 物理地址(phyiscal address) , MAC地址(MAC address)
地址解析协议ARP
交换机：链路层设备（检查链路层头部）,根据MAC地址进行转发
路由器：网络层设备（检查网络层的头部）, 根据IP地址进行转发

链路层和局域网

导论

问题

为什么在链路层和传输层都实现了可靠性 ？
因为一个点到点 一个端到端 ?

前言

• 传输层功能：解决进程到进程的区分，加强网络服务从不可靠变成可靠

• 网络层功能：解决端到端传输 ; 也即解决一个网络如何到达另一个网络的路由问题

• 链路层功能：解决点到点传输 ; 也即解决在一个网络内部如何由一个节点（主机或者路由器）到达另外一个相邻节点

• 目标

  • 理解数据链路层服务的原理:
    • 检错和纠错
    • 共享广播信道：多点接入（多路访问）
    • 链路层寻址
    • LAN:以太网、WLAN、VLANs
    • 可靠数据传输，流控制: 解决!
  • 实例和各种链路层技术的实现

• WAN : World Area NetWork

  • 广域网、外网、公网
  • 网络形式采用点到点链路
    • 带宽大、距离远（延迟大） >带宽延迟积大
    • 如果采用多点连接方式
      • 竞争方式：一旦冲突代价大
      • 令牌等协调方式：在其中协调节点的发送代价大
  • 点到点链路的链路层服务实现非常简单，封装和解封装

• LAN : Local Area NetWork

  • 局域网
  • 一般采用多点连接方式
    • 连接节点非常方便
    • 接到共享型介质上（或网络交换机），就可以连接所有其他节点
  • 多点连接方式网络的链路层功能实现相当复杂
    • 多点接入：协调各节点对共享性介质的访问和使用
    • 竞争方式：冲突之后的协调
    • 令牌方式：令牌产生，占有和释放等

• 术语

  • 节点 node : 任何运行链路层协议的设备称为节点，包括主机、路由器、交换机、wifi接入点
  • 链路 link : 沿着通信路径,连接个相邻节点通信信道的是链路
    • 有线链路
    • 无线链路
    • 局域网，共享性链路
  • 帧 frame : 第二层协议数据单元帧frame，封装数据报

• 数据链路层负责从一个节点通过链路将（帧中的）数据报发送到相邻的物理节点（一个子网内部的2节点）

链路层功能：解决点到点。在相邻两点之间，传输以帧为单位的数据

链路层服务

• 成帧(frame)

  • 链路层协议将网络层数据报用链路层帧封装起来，然后放入链路传送

• 链路接入

  • 媒体访问控制(Medium Access Control , MAC)协议规定了frame在链路上传输的规则
  • 对于点到点链路(链路的一端仅有一个发送方,另一端仅有一个接收方)
    • MAC协议比较简单
    • 即无论何时链路空闲，发送方都能够发送帧
  • 对于多个节点共享单个广播链路(即多路访问问题)
    • MAC协议负责协调多个节点的帧传输

• 可靠交付

  • 当链路层协议提供可靠交付服务时,它保证无差错地经链路层移动每个网络层数据报
    • 在（一个网络内）相邻两个节点完成可靠数据传递
  • 与TCP提供可靠交付服务类似，链路层也是通过确认和重传实现可靠交付
  • 链路层可靠交付服务通常用于易于产生高差错率的链胳,如无线链路
    • 其目的是本地(也就是在差错发生的链路上)纠正一个差错，而不是通过运输层或应用层协议迫使迸行端到端的数据重传
  • 然而，对于低比特差错的链路，括光纤、同轴电缆和许多双绞铜钱链路，链路层可靠交付可能会被认为是一种不必要的开销 由于这个原因，许多有线的链路层协议不提供可靠交付服务.

• 差错检测和纠正

  • 差错检测 : 逼运输层、网络层的因特网校验和更复杂一些.
  • 差错纠正 : 接收端检查和纠正bit错误，不通过重传来纠正错误

以太网 链路层 不保证可靠传输协议（因为以太网本身比较可靠，所以不需要通过协议实现可靠）
waln(无线局域网) 链路层 保证可靠传输协议(发出去之后需要确认)（因为无线网络本身出错率就比较高，存在电磁波衰减、干扰问题；所以需要人为地通过协议保证可靠）

实现

链路层在哪里实现 ?

• 首先，网络适配器(network adapter)，又称网络接口卡(Network Interface Card, NIC)，就是所谓的网卡

• 链路层功能主体在网卡上实现,也有功能在软件实现,软硬件结合
  

  • 每个主机/路由器/交换机上插若干网卡,每个网卡上实现了链路层和相应物理层功能、
  • 网卡写死了自己的MAC地址

• 网卡/适配器通信
  

  • 发送方:
    • 在帧中封装数据报
    • 加上差错控制编码，实现RDT和流量控制功能等
  • 接收方
    • 检查有无出错，执行rdt和流量控制功能等
    • 解封装数据报，将至交给上层
  • 适配器是半自治的,实现了链路和物理层功能
  • 一个适配器可以同时发/接

差错检测和纠正

• 链路层会提供 比特级差错检测和纠正(bit-level error detection and correction) 服务
• 理论基础 :
  • 发送方 : 为保护比特受损，使用差错检测和纠正位(Error-Detection and Correction , EDC)来增强数据D
    • 数据D不仅包括网络层数据报，还包括链路层首部
  • 接收方 : 收到D’和EDC’,确定D’和原D是否相同
  • 检测并非100%有效，可能出现未检出比特差错(undetected bit error)
    • 导致接收方向上提交一个受损的数据报
    • 因此，我们要选择一个差错检测方案，使得这种事件发生的概率很小
      • 奇偶校验
        • 用来描述差错检测和纠正背后隐含的基本思想
      • 检验和方法
        • 更多地应用于运输层
      • 循环冗余检测
        • 更多地应用在适配器中的链路层
          

奇偶检验

• 单bit奇偶校验 : 检测单(奇数)个bit级错误
  • 采用一个奇偶检验位.
  • 
• 2维奇偶校验 : 检测和纠正单个bit错误,检测两个bit差错的任意组合
  • i+j+1个奇偶检验位
  • 

校验和方法

略

循环冗余检测 CRC

略

• CRC : Cyclic Redundancy Check

多路访问链路和协议

• 两种类型的链路（一个子网内部链路连接形式）：

  • 点对点链路(point-to-point link)
    • 由链路一段的单个发送方和链路另一端的单个接收方组成
      • 如以太网交换机和主机之间的点对点链路
    • 为点对点链路设计的链路层协议 , 如点对点协议 PPP ; HDLC
  • 广播链路(broadcast link) (共享线路或媒体)
    • 多个发送和接收节点都连接在同一个，单一的，共享的，广播信道上
    • “广播”是因为当任何一个节点传输一个帧时，信道广播该帧，每个其他节点都收到一个副木。
    • 以太网和无线局域网是广播链路层技术的例子。

• 多路访问问题 ( mu1tiple access problem )

  • 如何协调多个发送和接收节点对一个共享广播信道的访问 ?
  • 在本节，我们暂缓讨论特定的链路层协议，而先研究这个对链路层很重要的问题.
  • 广播信道通常用于局域网中，局域网是一个地理上集中在一座建筑物中(或者在一个公司，或者在大学校园)的网络。因此我们还将在本节后面考察一下多路访问信道是如何在局域网中使用的

以太网：(Ethernet)，以太网可以看成是一种实现局域网通信的技术标准，是目前最广泛的局域网技术。以太网的运行速率有10Mbps,100Mbps,1Gbps,10Gbps的，它的传输介质有的是双绞线，有的是光纤。 简单的说，以太网就是在局域网内，把附近的设备连接起来，可以进行通讯。

多路访问协议 / 媒体访问控制协议(MAC)

• 碰撞 (collision)
  • 多个节点在同一个时刻发送，接收方则会收到2个或多个信号叠加
  • 通常，当碰撞发生时，没有一个接收节点能够有效地获得任何传输的帧;在某种意义下，碰撞帧的信号纠缠在一起 因此，涉及此次碰撞的所有帧都丢失了，在碰撞时间间隔中的广播信道被浪费了

• 多路访问协议 (multiple access protocol)

  • 即节点通过这些协议来规范它们在共享的广播信道上的传输行为
  • 在实践中，数以百计或者甚至数以千计个节点能够通过一个广播信道直接通信
  • 即 介质/媒体访问控制协议：MAC
    • 分布式算法-决定节点如何使用共享信道，即：决定节点什么时候可以发送？
    • 关于共享控制的通信必须用借助信道本身传输,没有带外信道.

• 理想多路访问协议

  • 给定：Rbps的广播信道
  • 必要条件：
    • 1. 当一个节点要发送时，可以R速率发送.
    • 2. 当M个节点要发送，每个可以以R/M的平均速率发送
    • 3. 完全分布的:不会因某主节点故障而使得整个系统崩溃
      • 没有特殊节点协调发送
      • 没有时钟和时隙的同步
    • 4. 简单

MAC协议分类

P294

• MAC协议可分为如下三大来
  • 信道划分协议(channel partitioning protocol)
    • 把信道划分成小片（时间、频率、编码）
    • 分配片给每个节点专用
  • 随机访问协议(random access protocol)
    • 信道不划分，允许冲突
    • 冲突后恢复
  • 依次轮流协议(taking-turns protocol)
    • 节点依次轮流
    • 但是有很多数据传输的节点可以获得较长的信道使用权

信道划分协议

TDMA

• TDMA:time division multiple access
  • 信道的时间分时间帧(time frame),每个时间帧划分为n个时隙(slot)
  • 节点轮流使用信道,每个节点使用每周期中固定的时隙(长度=帧传输时间)传输帧
  • 如果站点无帧传输，时隙空闲-》浪费
  • 如：6站LAN，1、3、4有数据报，时隙2、5、6空闲

    

FDMA

• FDMA: frequency division multiple access
  • 信道的有效频率范围被分成一个个小的频段
  • 每个站点被分配一个固定的频段
  • 分配给站点的频段如果没有被使用，则空闲
  • 例如：6站LAN，1、3、4有数据报，频段2、5、 6空闲

    

CDMA

• 码分多路访问 CDMA (code division multiple access) :
  • 所有站点在整个频段上同时进行传输, 采用编码原理加以区分
  • 完全无冲突
  • 假定:信号同步很好,线性叠加
  • 比方
    • TDM:不同的人在不同的时刻讲话
    • FDM:不同的组在不同的小房间里通信
    • CDMA:不同的人使用不同的语言讲话

随机接入协议

• 当节点有帧要发送时

  • 以信道带宽的全部 R bps发送
  • 没有节点间的预先协调
  • 两个或更多节点同时传输，会发生➜冲突“collision”

• 随机接入协议规定:

  • 如何检测冲突
  • 如何从冲突中恢复（如：通过稍后的重传）

• 有如下随机接入MAC协议:

  • 时隙ALOHA
  • ALOHA
  • CSMA, CSMA/CD, CSMA/CA

时隙ALOHA

略

纯ALOHA(非时隙)

略

CSMA(载波侦听多路访问)

略

CSMA/CD(冲突检测)

略

以太网的MAC协议 : CSMA/CD

CSMA/CA

略

无线局域网中的MAC协议：CSMA/CA

略

轮流协议 Taking Turns

• 信道划分MAC协议:
  • 共享信道在高负载时是有效和公平的
  • 在低负载时效率低下
    • 只能等到自己的时隙开始发送或者利用1/N的信道频率发送
    • 当只有一个节点有帧传时，也只能够得到1/N个带宽分配
• 随机访问MAC协议
  • 在低负载时效率高：单个节点可以完全利用信道全部带宽
  • 高负载时：冲突开销较大，效率极低，时间很多浪费在冲突中
• 轮流协议 : 有2者的优点

轮询协议 polling protocol

• 主节点邀请从节点依次传送

• 缺点:
  • 轮询开销：轮询本身消耗信道带宽
  • 等待时间：每个节点需等到主节点轮询后开始传输，即使只有一个节点，也需要等到轮询一周后才能够发送
  • 单点故障：主节点失效时造成整个系统无法工作
    

令牌传递协议 token-passing protocol

• 令牌控制
  • 控制令牌( token)循环从一个节点到下一个节点传递
  • 令牌报文：特殊的帧
  • 缺点:
    • 令牌开销：本身消耗带宽
    • 延迟：只有等到抓住令牌，才可传输
    • 单点故障 (token)：令牌丢失系统级故障，整个系统无法传输
      

MAC协议总结

• 多点接入问题：对于一个共享型介质，各个节点如何协调对它的访问和使用?
  • MAC协议负责协调，MAC协议可划分为
    • 信道划分协议：按时间、频率或者编码
      • TDMA、FDMA、CDMA
    • 随机访问协议 (动态)
      • ALOHA, S-ALOHA, CSMA, CSMA/CD
      • 载波侦听: 在有些介质上很容易 (wire：有线介质), 但在有些介质上比较困难 (wireless：无线)
      • CSMA/CD ：802.3 Ethernet网中使用
      • CSMA/CA ：802.11 WLAN中使用
    • 依次轮流协议
      • 集中：由一个中心节点轮询；分布：通过令牌控制

LAN 局域网

Local Area NetWork

链路层寻址和ARP

链路层地址 (MAC地址)

• 32bitIP地址: 网络层地址

  • 前n-1跳：用于使数据报到达目的IP子网
  • 最后一跳：到达子网中的目标节点

• 主机和路由器不但具有网络层地址，而且具有链路层地址（实际上是网卡具有）

• 链路层地址,又称 LAN地址(LAN address) , 物理地址(phyiscal address) , MAC地址(MAC address)

  • 用于使帧从一个网卡传递到与其物理连接的另一个网卡(在同一个物理网络中)
  • 6bytes , 48bit
  • MAC地址被设计为永久的
  • 理论上全球任何2个网卡的MAC地址都不相同 e.g.: 1A-2F-BB-76-09-AD

• 网络层地址和MAC地址分离

  • IP地址和MAC地址的作用不同
    • IP地址是分层的
      • 一个子网所有站点网络号一致，为了路由聚集，减少路由表消耗内存
      • IP地址完成网络到网络的交付
    • mac地址是一个平面的
      • 网卡在生产时不知道被用于哪个网络，因此给网卡一个唯一的标示，用于区分一个网络内部不同的网卡即可
      • 可以完成一个物理网络内部的节点到节点的数据交付
  • 局域网是为网络层协议设计的，而不仅仅是ip协议.如果适配器吧指派IP地址而非独立的MAC地址，则适配器不能方便的支持其他网络层协议
  • 如果适配器使用网络层地址而不使用MAC地址
    • 则网络层地址存入适配器，那么每次适配器移动都需要重新配置
    • 则网络层地址不存入适配器，而是适配器将收到的每个帧（向cpu发起中断，内核跳转到相应中断处理程序）沿协议栈向上传递到网络层.由网络层判断收到的帧的网络层地址是否匹配。这就造成，主机会被局域网上收到的每个帧中断.

地址解析协议ARP

• ARP : Address Resolution Protocol

  • 负责网络层地址(IP地址)和链路层地址(MAC地址)的转换
    

• 在LAN上的每个IP节点都有一个ARP表

• ARP表：包括一些LAN节点IP/MAC地址的映射

  • < IP address; MAC address; TTL>
  • TTL时间是指MAC地址映射失效的时间 ,典型是20min
    

• A要发送帧给B(B的IP地址已知),A需要根据ipB解析出macB.

  • 如果arp table中有该ipB的entry，那么易得mac地址
  • 如果arp table中没有该ipB的entry(如222.222.222.222)，那么如何 ?
    • A广播包含B的IP地址的ARP查询包
      • ARP查询分组
      • 目的地址使用MAC广播地址，子网LAN上的所有节点都会收到该查询包
        • Dest MAC address = FF-FF-FF-FF-FF-FF
      • 子网中的其他适配器接收到该用于arp查询的帧，将该帧中的ARP分组向上传递给arp模块，arp模块检验该arp分组要查询的ip地址是否是本机的ip地址. 无论是否匹配 , 都缓存下收到的该查询分组< sender_ip - sender_mac_addr > 若匹配,
    • B给A发送回一个响应ARP分组，告知其B的MAC地址
      • 该分组的目的地址为A的MAC地址

• ARP是即插即用的

  • 节点自己创建ARP的表项
  • 无需网络管理员干预

• ARP报文结构
  

• ARP协议是网络层协议还是链路层协议 ?
  • ARP分组既包含链路层地址，又包含网络层地址.
  • 将ARP看成是跨越链路层和网络层边界的协议

    ===================
        传输层 
        TCP/UDP
    ===================
        网络层
        ICMP
        IP
    ======# ARP #=======
        链路层
        Ethernet 以太网帧

发送数据报到子网外 / 路由到其他LAN

• Walkthrough :发送数据报：由A通过R到B，假设A知道B的IP地址

• 在路由器R上有两个ARP表，分别对应两个LAN

• 在源主机的路由表中，发现到目标主机的下一跳时111.111.111.110

• 在源主机的ARP表中，发现其MAC地址是E6-E9-00-17-BB-4B, etc

• A创建数据报，源IP地址：A；目标IP地址：B

• A创建一个链路层的帧，目标MAC地址是R，该帧包含A到B的IP数据报
  

• 帧从A发送到R

• 帧被R接收到，从中提取出IP分组，交给上层IP协议实体
  

• R转发数据报，数据报源IP地址为A，目标IP地址为B

• R创建一个链路层的帧，目标MAC地址为B，帧中包含 A到B的IP 数据报.

  • R查询路由表得知下一跳的IP，然后查询ARP表，进而得知下一跳的MAC地址，进而将MAC地址写入链路层帧中
    

Ethernet 以太网

• 基于集线器(hub)/交换机(switch)的星形拓扑结构
  • 每个节点以及相连的交换机端口使用（独立的）以太网协议(不会和其他节点的发送产生碰撞)
  • 集线器只是重新生成接收的bit，将其能量强度放大并向其他接口传输出去
  • 

以太帧结构

• 发送方适配器在以太网帧中封装IP数据报，或其他网络层协议数据单元

• 地址：6字节源MAC地址，目标MAC地址

  • 如：帧目标地址=本站MAC地址，或是广播地址，接收，递交帧中的数据到网络层
  • 否则，适配器忽略该帧

• dest address : 6 bytes

  • 目标适配器的MAC address
  • 若收到以太网帧，
    • 其目的地址是本机MAC地址或者MAC广播地址，则将该帧的数据字段传递给网络层;
    • 否则丢弃

• src address : 6 bytes

  • 源mac地址

• 类型：指出高层协议(IP , Novell IPX , AppleTalk , ARP等)

• payload : 承载 IP 数据报。

  • payload最大 即 以太网的最大传输单元(MTU) 1500 字节
    • 如果IP数据报 > 1500 byte 则必须分片
  • payload最小 为 46bytes
    • 如果IP数据报 < 46 byte 则必须填充到46bytes

• CRC：在接收方校验

  • 如果没有通过校验，丢弃错误帧

以太网 : 无连接、不可靠的服务

• 无连接：帧传输前，发送方和接收方之间没有握手
• 不可靠：接收方适配器不发送ACKs或NAKs给发送方
  • 递交给网络层的数据报流可能有gap
  • 传输层使用TCP(rdt)，应用不会看到gap(tcp协议会导致重传)(这里以太网确实会重传数据，只不过是因为tcp协议而非以太网协议)
  • udp，应用层就会看到gap
• 以太网的MAC协议：采用二进制退避的CSMA/CD
  介质访问控制形式

以太网的MAC协议 : CSMA/CD

略

IEEE 802.11 Wireless LAN 略

以太网是一种广泛应用的局域网 是有线的

WLAN也是一种局域网 是无线的

802.11 LAN 体系结构

帧结构

WLAN帧

略

链路层交换机

我对链路层交换机的印象 : 对Host来说完全透明. 从TCP/IP协议栈到最底层的网卡Network Interface都不需要管链路层交换机. 不需要在帧里指定的填写字段说明发送给某个链路层交换机. 链路层交换机更像是一个被动的捕获网络中的帧, 作用仅仅是 将其信号放大 , 并正确的转发出去.

链路层交换机

• 执行转发和过滤

  • 交换机基于 MAC 地址而不是基于 IP 地址转发分组
  • 通过交换机表(switch table)a完成
    • 该表记录了从交换机某接口出发可以到达的MAC地址
    • 交换机表中的一个表项包含:
      • 一个MAC 地址
      • MAC 地址的交换机接口
      • 表项放置在表中的时间
        

• 透明：主机对交换机的存在可以不关心

  • 通过交换机相联的各节点好像这些站点是直接相联的一样

• 即插即用，自学习：

  • 交换机无需配置
  • 如何自学习配置switch table ?
    • 1. 交换机表初始为空
    • 2. 对于在每个接口接收到的每个人帧，该交换机在其表中存储:
      • 在该帧源地址字段中的 MAC 地址;
      • 该 帧到达的接口;
      • 当前时间
      • 交换机如此记录了发送节点所在的局域网网段 如果在局域网上的每个主机最终都发送了一个帧，则每个主机最终将在这张表中留有记录.
    • 3. 如果在一段时间(aging time)后，交换机没有接收到以该地址作为源地址的帧，就在表中删除这个地址.

• 可以多路同时传输

  • 主机有一个专用和直接到交换机的连接
  • 交换机缓存到来的帧
  • 对每个帧进入的链路使用以太网协议，没有碰撞；全双工
    • 每条链路都是一个独立的碰撞域
    • MAC协议在其中的作用弱化了
  • 交换：A-to-A’ 和 B-to-B’ 可以同时传输，没有碰撞

  • 

链路层交换机 vs 路由器

P316

• 都是存储转发设备，但层次不同
  • 交换机：链路层设备（检查链路层头部）,根据MAC地址进行转发
  • 路由器：网络层设备（检查网络层的头部）, 根据IP地址进行转发
    以下还有点不懂
• 都有转发表：
  • 交换机：维护交换表，按照MAC地址转发
    • 执行过滤、自学习和生成树算法
    • 即插即用；二层设备，速率高
    • 执行生成树算法，限制广播帧的转发
    • ARP表项随着站点数而增多
  • 路由器：维护路由表，执行路由算法
    • 路由算法能够避免环路，无需执行生成树算法，可以以各种拓扑构建网络
    • 对广播分组做限制
    • 不是即插即用的，配置网络地址（子网前缀）
    • 三层设备，速率低
      

VLANs

略

链路虚拟化：MPLS

略

数据中心网络

略

a day in life of web request