一周总结(四)

发表于

前言

The Medium Access Sublayer

概念解析以及习题分析

  1. ALOHA协议：

    • Pure ALOHA：传输点可以在任意时刻发送帧，当两个传输点同时向频道传输数据时会发生冲突，
      这时这两个传输点停止一个随机时间后再次发送帧。它不需要一个全局时钟。设G为每单位时间传输的包量，S为吞吐量，则有
      S = Ge-2G，当G=0.5时最大值为18.6%
      • Slotted ALOHA： 时间被分段，每个传输点必须在一个时间槽的开始时传送，传送的数据必须小等于
        这个时间槽。它需要全局时钟来同步。效率为S = Ge-G，当G=1时最大值为36%

  2. CSMA协议

    • 发送数据前先监听信道，若空闲，则立即发送数据。若监听到冲突，等待随机时间，再重新发送
    • Nonpersistent CSMA：若空闲，发送数据，若忙碌，则等待随机时间再监听。减少冲突，信道利用率降低
    • 1-persistent CSMA： 若空闲，发送数据，若忙碌，则一直监听到空闲再发送。提高信道利用率，增大冲突
    • p-persistent CSMA： 若忙，继续监听，若空闲，根据p概率发送，1-p概率继续监听。有效平衡，但复杂
  3. CSMA/CD
    • 在CSMA的基础上增加Collision Detected，即发送数据时监听冲突。若冲突则立即停止发送数据，等待随机时间后重发
    • 随机时间采取了二进制指数退避算法(binary exponential backoff)。
      • 基本退避时间为端到端的往返时间2t(冲突期、争用期)
      • 当冲突次数k小于10时，在[0,1,2,3,…,(2k-1)]在随机选取整数r，等待时延为r*2t
      • 当冲突次数大于10时，取k为10
      • 当冲突次数超过16，发送失败
    • 它是抢占(Seize)的，即一个站点发送数据，其他的就等待
    • 发送时间必须大于两倍传输时间。假设A与B相隔1km，当A发送数据到B。这个数据帧在非常接近B的时候与B发送出的数据冲突了(即经过传输时间t后冲突)，
      那么A需要在经过一个传输时间t才能检测到冲突。如果小于2t，那么发送停止后才会接收到返回的冲突帧，监听冲突就失败了。
  4. Collision-Free Protocols
    • Bit-Map Protocol：tp
      竞争周期由N个间隙组成，站点j可以在时隙j填入1bit，表明有1帧发送，然后按照顺序发送。效率=d/(N+d),N每帧开销，d数据量/帧，高负荷下N=1
    • Token Ring： 就是令牌在环形总线中传递，只有拿到令牌的节点才能发送数据
    • Binary Countdown：每一个站点产生一个二进制地址，如0010，0100，1001。站点在每一个位时间按序发送一个bit，在发送时这些地址被取或返回。
      第一个位时间发送0，0，1，取或后，0010和0100看到了1，则他们知道有高序地址在竞争，就放弃发送。1001发送帧之后，开始新一轮竞争。效率为d/(d+log2N)
    • Limited-Contention Protocol: 在低载荷时采用竞争法使时延较短，在重载荷时采用无冲突法，使信道利用率较高，
  5. IP地址与MAC地址的区别
    • IP地址是指互联网协议地址（Internet Protocol Address），长32位，是分配给网络和主机的逻辑地址
    • MAC地址是指物理地址、硬件地址，是烧到网卡里的，具有全球唯一性
  6. 二级交换机
    • 设A1，A2为同处VLAN1的PC，B1，B2为同处VLAN2的PC，且它们均连在了交换机S1，S1与路由器R1相连。
    • VLAN内通信：A1给A2发送信息
      • 交换机收到A1的数据帧，分析报头，得到目标MAC地址。
      • 交换机在内部的MAC地址表中查找对应端口A2，若找到，则发送给A2；若未找到，则向VLAN1内所有端口(A2,R1)进行广播，收到A2回应后，将A2加入到MAC地址表中，并发送帧给A2
      • 交换机可以建立记录和维护地址表。这也称为交换机学习能力(auto learn)
    • VLAN间通信：A1给B1发送信息
      • 交换机收到A1的数据帧，分析报头，得到目标MAC地址
      • 交换机查找对应端口，如果地址表中记录端口对应路由器，则发送给路由器；否则则向VLAN1内所有端口(A2,A3,R1)进行广播，路由器分析知B1属于Vlan2，则回应交换机。交换机将路由器地址加入到对应的表中，把帧发送给路由器
      • 路由器通过交换机Vlan2把帧发给B1
  7. 三级交换机
    • 网络内通信：设A1，A2为同处网络1的PC，B1，B2为同处网络2的PC，且它们均连在了交换机S1。
      • A1使用A2的IP地址和子网掩码取得A2的网络地址(IP地址 & 子网掩码)，确定它们属于同一网段
      • A1给A2发送ARP，得到A2返回的MAC，A1用A2的MAC封装数据包，发送给交换机。
      • 交换机用二层交换，查找MAC地址表，转发数据包
    • 网络间通信：
      • A1使用B1的IP与子网，确定不在一个子网内
      • A1将数据包发送给缺省网关(即交换机的三层路由)
      • 路由通过查询路由表，以缺省网关的MAC为源地址，以B1的MAC地址为目标MAC，构建新帧头。
      • 三层路由将A1与B1的MAC地址以及转发端口的对应关系加入地址映射表中
      • A1发送给B1的数据将可以直接通过二层交换进行。(一次路由，多次转发)
  8. CSMA/CA
    • 包括载波监听(CSMA)与冲突避免(CA)
    • 发送之前开始监听，若信道为空，则等待一个帧间隔，再次监听，若空，则开始随机后退，结束后再次监听，若空则发送数据。以上任一阶段不空，则停止本次发送。之后重新开始本过程
    • 帧间隔分为SIFS、PIFS、DIFS、EIFS，优先级依次降低。参见
      • SIFS：control frame or next fragment (ACK CTS)
      • PIFS: PCF frames (用以获得在无竞争访问周期启动时访问信道的优先权)
      • DIFS: DCF frames (一般数据帧和管理帧)
      • EIFS: Bad frame recovery
    • 当一个站发送第一个帧时并且检测到此时信道为空，则不进行二进制退避
  9. 网桥的自学习与转发
    • 当网桥收到一个帧时，就在自己的转发表中进行查找，若没有，则将(地址，端口)加入到表中
    • 当网桥转发一个帧时，也查找自己的转发表，若没有，则从其他端口进行转发；若有，则将该端口与该帧进入网桥的端口进行比较，若相等，则丢弃该帧，因为目的主机已经收到了，否则转发。
  10. Spanning Tree Bridges (STP,生成树协议)
    • 交换网络互联，会造成网络环路，引发广播风暴。
    • STP就是把环形结构变成一个树形结构，在逻辑上阻塞一些端口
    • 依据网桥ID(由网桥优先级和网桥MAC地址决定)选择根网桥(小者优先)
    • 依据根路径成本选择根端口和指定端口
  11. MACA(Multiple Access with Collision Avoidance)协议(冲突避免多路访问)
    • RTS(Request To Send)帧，该帧由发送方发送，包含了随后将要发送的数据帧的长度
    • CTS(Clear to Send)帧，由接收到RTS的站点返回，包含了数据长度(从RTS复制)
    • 发送方收到CTS后开始发送
    • 其他站收到RTS，则保持沉默，至少等待足够长的时间以便在无冲突的情况下CTS返回给A。
    • 如果其他站收到CTS，则它可以检查CTS帧获得数据帧长度，保持沉默在接下来的数据传输中
    • 收到RTS但没有收到CTS的站点可以在数据帧传输过程中自由发送任何信息
    • 收到CTS帧，则无论是否收到RTS帧，都要延缓发送任何信息直到那个帧如期传送完毕
  12. 名词解析
    • Application layer: Application gateway
    • Transport layer: Transport gateway
    • Network layer: Router(路由器)
    • Data link layer: Bridge(桥接器), switch(交换机)
    • Physical layer: Repeater(中继器，延长网络距离), hub(集线器,连接多个设备)
  13. Frame header、Packet header、TCP header、User data、CRC。斜体是packet，由网络层构建，整个是Frame，由数据链路层构建

  14. VLAN，讲的很详细，摘抄一点如下

    习题解析

  15. A group of N stations share a 56-kbps pure ALOHA channel. Each station outputs a 1000-bit frame on an average of once every 100 sec, even if the previous one has not yet been sent (e.g., the stations can buffer outgoing frames). What is the maximum value of N?

    • 思路：计算出纯ALOHA的带宽，以及每个站需要的带宽。
    • 纯ALOHA的带宽=信道利用率(0.184)x56kb/s，站点需要的带宽为1000bit/100sec=10b/s
  16. What is the baud rate of the standard 10-Mbps Ethernet?
    • 以太网标准10M 802.3 LAN采用曼彻斯特编码，即每一位都有两个信号周期，所以为20Mbaud
  17. Consider building a CSMA/CD network running at 10 Mbps over a 1-km cable with no repeaters. The signal speed in the cable is 200,000 km/sec. What is the minimum frame size?
    • 信号传输时间t=1km / 200000km/sec，最小发送时间为2t，则最小帧为2t*1G。
  18. The reason for binary exponential backoff in the classical Ethernet is that this algorithm is adaptive to network load
  19. A network interface card mainly works at physical and data link
  20. 1000Base-F network: Fiber Optics