内容

  • Multiple access protocol 多路访问协议
  • A real system(LAN): Ethernet 以太网
    • 以太网是利用MAC将各个电脑连接起来的一种协议
    • IEEE802.3
  • Data Link Layer Switching 数据链接层的交换
    • Bridge 桥
    • switch 交换机

Medium Access Control

这一章的内容

  • Learn random access protocol(随机访问协议)
  • Master pure ALOHA and slotted ALOHA
  • Master the characteristics of each type of CSMA
    • 1-P CSMA
    • CSMA/CD
  • Learn collision-free protocol (无冲突的协议)
    • Bit-Map
    • Binary Countdown

The problem of Broadcast network 广播网络的问题

  • Data communication 数据通讯
    • Unicast（单播）：One - to - One
    • Broadcast（广播）：One - to - Everyone
    • Multicast（组播）：One - to - A group
  • 在任何广播网络中，关键问题是如何在多个竞争用户之间分配单个广播信道。
    • allocate a single broadcast channel
  • 广播信道有时被称为多路访问信道或随机访问信道。
    • multiaccess channels or random access channels

What is MAC ?

  • 用于确定谁在多路访问信道上的下一步且属于数据链路层的子层的协议，称为 MAC（Medium Access Control）子层
  • MAC 子层在 LAN 中尤为重要，其中许多 LAN 使用多路访问信道作为通信的基础。

Allocating channel 分配通道

  • 有两种分配通道的方法：
    • 静态分配 -- static allocation
      • 频道就像一个电路——只允许一个人使用它。
      • 未使用的带宽会丢失（浪费）
    • 动态分配 -- dynamic allocation
      • 通道是开放的，一些计算机可以访问其他计算机未使用的带宽。
      • 没有专用带宽

Static allocation

  • FDM（频分多路复用 Frequency Division Multiplexing）
  • TDM（时分多路复用 Time Division Multiplexing）
Problem of Static Channel Allocation
  • FDM在什么情况下是有效的？
    • 当只有少量且固定数量的用户，并且每个用户都有大量（缓冲）流量负载时
  • FDM 有什么问题？
    • 如果当前对通信感兴趣的用户少于 N 个，则频谱的某些部分将被浪费。
    • 如果超过 N 个用户想要通信，其中一些将被拒绝权限
    • 即使用户数为N且不变，当一些用户处于静止状态时，其他人无法使用他们的带宽，因此只是浪费。
    • 对于突发数据流量（峰值流量与平均流量比为1000:1），分配的小子信道大部分时间都处于空闲状态，但无法处理峰值流量。
Poor Performance Of Static FDM 性能不佳

无 FDM

  • 信道容量 C bps
  • 到达率 λ frames/sec
  • 平均帧长 1/μ(bit/frame)
  • 平均时延 T

有FDM

  • 分成N个子通道
  • 每个子信道容量 C/N bps
  • 平均输入率 λ/N

恰好适用于 FDM 的相同论点也适用于时分复用 (TDM)。

Dynamic Channel Allocation

  • 在进行动态分配之前，我们必须考虑 5 个关键假设：
    • Station Model
    • Single Channel Assumption
    • Collision Assumption
    • Continuous/Slotted Time
    • Carrier/No Carrier Sense
1 – Station Model
  • 该模型由 N 个independent stations（也称为terminals）组成。
  • 每个站生成用于传输的帧。
    • generate frames
  • 一旦生成了一个帧，该站就会被阻塞，并且在该帧成功传输之前什么都不做。
2 – Single Channel Assumption
  • 它是模型的核心。
  • 单个通道可用于所有通信。
  • 就硬件而言，所有站都是等效的。
  • 但是协议软件可能会为不同的站点分配优先级。
3 – Collision Assumption
  • 如果同时传输两帧，它们就会“冲突”。
  • 在碰撞中，两帧都完全丢失。
  • 冲突的帧必须稍后再次重传。
  • 所有站点都可以检测冲突。
  • 除了冲突，没有其他错误。
4 – Continuous/Slotted Time
  • 连续时间 Continuous Time
    • 时间被视为一个连续体。
    • 时间不分为离散的间隔。
    • 帧传输可以在任何时刻开始。
  • 空档时间 Slotted Time
    • 时间被划分为离散的间隔（槽）。
    • 帧传输总是从一个时隙开始。
    • 一个时隙可能包含 0、1 或更多帧。
      • 0 frames = 空闲时隙
      • 1 frames = 成功传输
      • 2+ frames = 碰撞
  • 有些系统使用一种，有些系统使用另一种。 但是对于给定的系统，只有其中一个成立。
5 – Carrier/No Carrier Sense
  • Carrier sense（载波侦听）
    • station可以在发送之前判断频道是否正在使用
    • 如果信道被感知为繁忙，则没有站将尝试使用它，直到它变为空闲。
  • No carrier sense 非载波侦听
    • station在尝试使用该频道之前不会感应到该频道。
    • 只有稍后他们才能确定传输是否成功。
  • LAN一般都有载波侦听。
  • 请注意，此处的“载波”一词是指电缆上的电信号。

Multiple access protocol 多路访问协议

  • Random Access Protocol 随机访问协议
    • 特点：竞争使用通道，可能导致冲突
    • 典型的随机访问协议
      • ALOHA
        • pure ALOHA；
        • slotted（分槽，分槽）ALOHA
      • CSMA
      • CSMA/CD（以太网）
  • Controlled Access 受控访问协议
    • 特点：已分配信道，无冲突

ALOHA Protocol

  • Pure ALOHA:
    • A Frame is sent at once when it is generated
    • Collision may be occurred all the time
    • 冲突时间为2D
      • 前面D时间内传输的帧的后面部分会冲突
      • 后面D时间内传输的帧的前面部分就冲突
  • Slotted ALOHA
    • Frame is sent only at the very beginning of interval
    • Frame is sent successfully once no collision is occurred at the beginning of interval (slot)
    • 冲突时间为D
      • 前一个帧传输完毕后，进入时隙的起点，可能在D时间(时隙持续时间)一直发生冲突
  • 总结

Carrier Sense Protocols

  • CSMA：Carrier Sense Multiple Access

  • Characteristic：“先听后发”

    • Improve ALOHA

  • Types

    • Non-persistent CSMA
    • Persistent CSMA
      • 1-persistent CSMA
      • P-persistent CSMA
      • 1-persistent is a special example of p-persistent
      • 但前者是连续时间的，后者是分槽的

  • 问题：对于1-persistent CSMA，如果一个频道空闲后站点进行发送数据，是否会造成冲突

    • 会，有两种情况
      • 有两个或多个站点同时发送数据
      • 传播延迟时间--Propagation
    • 传输时延是指一个站点从开始发送数据帧到数据帧发送完毕所需要的全部时间
    • 传播时延是指发送端开始发送数据到接收端收到数据所需要的全部时间。
    • 传输时延和发送数据帧大小有关，而传播时延和传输距离相关。

  • 例子：计算冲突窗口

  • CSMA/CD -- Carrier Sense Multiple Access with Collision Detection
    • “先听后发、边发边听”
    • 所有站点在发送时都接收到自己的信号，因此，如果信号不同，站点就会检测到冲突。
    • 一旦检测到冲突，立即中止传输，并在发生冲突时发送阻塞信号(a jam signal)以通知其他站点；
    • 所有站点都需要一个随机的时间来再次重传。
    • 广泛应用于局域网LANs的MAC子层
    • 有三个状态
      • Contention竞争
      • Transmission 传输
      • idle 空闲

Other Multiple Access Protocol

  • Collision-Free protocol (无冲突的协议)
    • A Bit-Map protocol(位图协议,预留协议)
      • 竞争期
      • 传输期
    • Binary Countdown protocol (二进制倒计数协议)
  • Limited-Contention protocol (有限竞争协议)
  • WDMA（波分多路访问协议）
  • MACAW（无线局域网协议）
    • MACA：Multiple Access with Collision Avoidance
    • MACAW ：MACA for wirless

IEEE Ethernet naming rule

  • 10Base2（IEEE 802.3a）
    • –10：baseband（unit: Mbps） 10Mbps
    • –Base：baseband transmission (基带传输)
    • –2（或5）：support segment （100米为单位，四舍五入）
  • 10Base-TX（IEEE 802.3X）
    • –T：copper UTP
    • –F：fiber

检测粗或细同轴电缆的问题

  • 检测电缆断裂、过长（超长）、不良分接头或连接器松动可能是粗同轴电缆或细同轴电缆的主要问题。
  • 时域反射计（时间域反射计）
    • 发帖
    • 定时发送和接收回声之间的时间间隔
    • 定位回声的来源

Topology of 10Base-T

  • Physical topology is star
  • Logical topology is bus（compete the bus）

  • 优势
    • 安装成本低于同轴电缆
    • 即插即用，组网灵活
    • 星型拓扑，易分离故障
    • 开放
  • 问题
    • 多用户共用一条10M总线（通道）

以太网编码 Ethernet encoding

  • 不能直接使用二进制表示电压0V和5V，因为你分不清空闲的发送端(0 volts)和0 bit(0 volts)
  • 使用Manchester encoding，1bit表示一个高伏加低伏，0bit表示一个低伏加高伏

IEEE 802 standard (chapter 1)

Ethernet MAC sublayer protocol

有两种不同的MAC子层协议：

  1. DIX(DEC, Intel, Xerox)
    • 使用最广，首先发明
  2. IEEE 802.3
    • 后发明，使用范围没那么广
Destination/Source address

10-Mbps baseband standard 只使用6个字节的地址

MAC address (physical address)

Ethernet MAC Address

  • Manufacture ID (OUI，Organizationally Unique Identifier ) + NIC ID=24bit + 24bit
  • 例子

区别：

  2. The Type/Length Field

    • 大于1536的是Type，小于等于1536(0x600)的是Length

  3. Data field

    • 0~1500字节
    • 以太网要求有效帧必须至少64个字节
      • 其他必须的部分为6+6+2+4=18个字节
      • 最大帧长：1500+18=1518

为什么需要至少64字节

  • CSMA/CD：帧的传送时间大于等于\(2\tau\)
  • 所以小于这个值的说明发生了冲突，提前送回
  • 对于以太网

Binary Exponential Backoff 二进制指数回退算法

  • 发生碰撞后，该站等待一个随机时间并重试。 随机化是如何完成的？
  • 时间被分成离散的时隙，其长度等于最坏情况的往返传播时间 (2τ)。
    • 第一次碰撞后，每个站随机等待 0 或 1 个时隙。
    • 第二次碰撞后，每个站随机等待 0、1、2 或 3 个时隙时间。
    • 在 i 次冲突后，会选择 0 到\(2^i-1\) 之间的随机数，并跳过该数量的时隙。
    • 达到 10 次冲突后，随机化间隔将冻结在 1023 个时隙。
    • 16次碰撞后，控制器放弃并报告失败。

Typical Ethernet

  • 10base2
  • 10base5
  • 10base-T
  • Improve performance
    • Up to 100Mbps
    • Switched network

交换式以太网

  • 高速背板：backplane
  • 插件卡: plug-in cards

  • Hub：集线器

  • Switch：交换机

  • Repeater：中继器

  • 插入式卡检查帧是否以连接到同一卡的其他站之一为目的地。

    • 如果是，则将帧复制到目标站。
    • 如果没有，帧将通过高速背板发送到目标站的卡。

  • 如果连接到同一个插件卡的两台机器同时传输帧会怎样？

    • 情况 1：卡上的所有端口都连接在一起形成本地卡上 LAN -- Hub
      • 在任何时候，每张卡只允许传输一次，但所有卡都可以并行传输。
      • 每张卡形成自己的冲突域，独立于其他。
    • 情况 2：每个输入端口都可以在卡的板载 RAM 中缓冲传入帧 -- Switch
      • 所有输入端口都可以同时接收（和发送）帧 - 并行和全双工(parallel and full-duplex)
      • 每个端口都是一个单独的冲突域，因此不会发生冲突。

100Mbps Ethernet—802.3u 快速以太网

  • 带宽：10Mbps -> 100Mbps

  • 快速以太网（IEEE 802.3u）于 1995 年 6 月被 IEEE 正式批准。

    • 向下兼容
      • 保留旧的数据包格式、接口和程序规则
    • 更快
      • 比特时间从 100 (10 Mbps) 纳秒减少到 10 纳秒 (100 Mbps)。
    • 自动协商 -- autonegotiation

  • 快速以太网使用集线器或交换机连接计算机，就像 10Base-T 接线一样。

  • 快速以太网允许使用以下三种类型的电线。

Gigabit Ethernet（吉比特以太网）千兆以太网

  • 千兆以太网 (IEEE 802.3z) 于 1998 年被 IEEE 批准。
    • 向下兼容
    • 比现有的 802.3 和 802.3u 标准更快。
  • 千兆以太网的所有配置都是点对点而不是多点。
  • 千兆以太网支持两种不同的操作模式
    • 全双工：基于交换机的连接
    • 半双工：基于集线器的连接
  • 千兆以太网支持流量控制：一端可以向另一端发送一个特殊的控制帧，告诉它暂停一段时间

解决一些问题

  • carrier extension（载荷扩充）
    • 将帧填充到 512 字节 (8)
    • 所以，最大距离可以是200m=25*8
    • 缺点：线路利用率低，仅为9%（46/512）
  • frame bursting （帧串）
    • 在一次传输中传输多个帧
    • 改善线路效用

IEEE802.2

  • LLC 在以太网和其他 802 协议之上运行。
  • LLC 通过向网络层提供单一格式和接口来隐藏各种 802 网络之间的差异。
  • LLC 提供三种服务选项：
    • 不可靠的数据报服务，
    • 确认数据报服务
    • 可靠的面向连接的服务。
  • LLC 标头包含三个字段：
    • 目的地接入点
    • 源接入点
    • 一个控制字段。

数据链路层交换

为什么有多个局域网？

  • 每个部门的目标可能不同
  • 可能在地理上分布在几个建筑物上
  • 可能需要拆分成单独的 LAN 以适应负载
  • 最远的机器之间的物理距离可能太大
  • 为了提高性能
  • 桥梁(Bridge)可以为组织的安全做出贡献
Provide a higher load

Bridge-operation from 802.11 to 802.3

Bridge from 802.X to 802.Y
  • 问题：
    • 不同的帧格式——重新封装 re-encapsulation
    • 不同的传输速度 - 缓冲 buffering
    • 不同的最大帧长（如，802.3 1526 字节、802.11 2346 字节）
    • 不同的安全策略
    • 不同的QoS策略

Local internetworking 本地互联

  • 通过透明网桥(transparent bridges)连接的多个 LAN 不需要对其硬件和软件进行任何更改。
    • 透明网桥
      • 即插即用，无需任何配置
      • 网络中的站点无需感知网桥的存在与否
  • 透明网桥以混杂模式（promiscuous mode）运行，接受在它所连接的所有 LAN 上传输的每一帧。
  • 当帧到达时，网桥必须决定是丢弃还是转发它，如果是后者，则将帧放置在哪个 LAN 上。
  • 通过在网桥内的大（散列）表中查找目标地址来做出决定。

透明网桥

  • 网桥维护一个目的地址表和相应的输出行，如下所示：
  • 最初所有的哈希表都是空的。
  • flooding algorithm：（泛洪）
    • 未知目的地的每个传入帧都在网桥连接到的所有 LAN 上输出，除了它到达的那个。
  • backward learning （逆向学习）
    • 通过查看传入帧的源地址，网桥能够知道哪个机器可以在哪个 LAN 上访问，因此它在其哈希表中创建一个条目，将源机器与传入 LAN 链接起来。
  • 如何处理动态拓扑？
    • 每当创建哈希表条目时，都会在条目中注明帧的到达时间。
    • 每当来自条目中地址的帧到达时，条目时间就会更新。
    • 桥中的进程会定期扫描哈希表并清除（清除）超过几分钟的所有条目。

  • 传入帧的路由过程：
    • 如果目的局域网和源局域网相同，则丢弃该帧 -- discard
    • 如果目标 LAN 和源 LAN 不同，则转发该帧 -- forward
    • 如果目标 LAN 未知，请使用泛洪 -- flooding
  • 当每一帧到达时，必须应用上述算法。
  • 特殊用途的 VLSI 芯片可以在几微秒内完成查找和更新表条目。

转发

过滤

泛洪

透明网桥小结

  • Bridge can segment collision-domain 可以分割冲突域
例子

Spanning tree bridge

  • 为了提高可靠性，一些站点在 LAN 对之间并行使用两个或多个网桥。
  • 这种安排在拓扑中创建了环路。
  • 如果到达未知目的地的帧会发生什么？

  • 解决方案是让网桥相互通信，并使用到达每个 LAN 的生成树覆盖实际拓扑。
  • 在生成树中，从每个源到每个目的地都有唯一的路径，循环是不可能的。
  • 构建生成树
    • 选择一座桥作为树的根
      • 序列号最小的网桥成为根。
    • 构建了从根到每个网桥和 LAN 的最短路径树。
    • 如果网或 LAN 出现故障，则会计算新的生成树。

Remote Bridges

  • 远程网桥可用于互连远程 LAN。
    • 在每个 LAN 上放置一个网桥
    • 用点对点线成对连接桥。

Network Devices

  • Repeaters 中继站
    • Are analog devices to connect two cable segments.
    • A signal appearing on one segment is amplified and put out on the other segment.
    • Can not understand frames, packets, or headers, but understand volts.
  • Hubs 集线器
    • Frames arriving on any of the lines are sent out on all the others.
    • The entire hub forms a single collision domain.
    • All the lines coming into a hub must operate at the same speed.
    • Do not amplify the incoming signals and are designed to hold multiple line cards each with multiple inputs (one collision domain).
    • Do not examine the 802 addresses or use them in any way.
  • Bridge 网桥
    • A bridge connects two or more LANs.
    • When a frame arrives, software in the bridge extracts the destination address from the frame header and looks it up in a table to see where to send the frame.
    • A bridge may have line cards (like a hub) for different network types and speeds.
    • Each line forms its own collision domain.
  • Switches 交换机
    • A switch is similar to bridge in its routing on frame addresses.
    • Switches are often used to connect individual computers (no collision).
    • Switches must have space for many more line cards.
    • Each line card provides buffer space for frames arriving on its ports.
    • Each port forms its own collision domain.
  • Routers 路由
    • When a packet comes into a router, the frame header and trailer are stripped off and the packet located in the frame's payload field is passed to the routing software.
    • The routing software uses the packet header to choose an output line.
    • For an IP packet, the packet header will contain a 32-bit (IPv4) or 128-bit (IPv6) address, but not a 48-bit 802 address.
  • Gateways
    • Transport gateway
      • Connect two computers that use different connection-oriented transport protocols
      • Copy the packets from one connection to the other, reformatting them as need be.
    • Application gateway
      • understand the format and contents of the data
      • translate messages from one format to another.

  • Network interface card (NIC) 网络适配器/网卡
  • Bridge
  • Switch