Skip to content

2020 计网重修班

三

image.png|600

类似作业题 ALOHA 1） 记每个时隙 \(A\) 成功为事件 \(S\) 概率为 \(P(S)=p(1-p)^{3}\) 时隙 4 第一次成功，则为 \(P(S)(1-P(S))^{3}\) 2） 某个结点在时隙 3 中成功的概率是多少？ 注意：由于 \(p,p,(1-p),(1-p)\) 这种会由于碰撞而无法成功，所以无法简单对 \((1-p)^{4}\) 取补得到答案。 记为事件 \(N\), \(P(N)={1\choose4}p(1-p)^{3}=4p(1-p)^{3}\) 3) 出现首个成功节点的概率，则前 3 个时隙都没有某个成功且第 4 个时隙某个节点成功 由乘法原理 \((1-4p(1-p)^{3})^{3}(4p(1-p)^{3})\) 4) 效率分析： 每个时隙，每个节点能发送成功的概率为 \(p(1-p)^{3}\) 每个节点是否决定发送相互独立。 设单位时隙发送包的总数量为 \(r.v.X\) \(E[X]=4p(1-p)^{3}\)

四

  1. CSMA/CA
    1. 发送之前，检查信道是否空闲
    2. 如果空闲，等待 DIFS ，发送 RTS，如果收到了 CTS 就开始传输数据
      1. 如果没有收到 CTS，并超时了，也进入退避等待。
    3. 如果不空闲，则等待，计算退避时间
    1. 无线链路隐藏终端，即不知道发送方在哪，有线链路则不是
    2. 无线链路是半双工的，即不能同时发送和接受，有线链路是全双工的
    3. 无线链路信号比较弱不稳定，有线链路稳定。
    4. CSMA/CD 需要在发送的同时检测拥塞能量，而无线链路接收信号能量远小于发送能量，并且半双工机制也难以在发送的同时检测，且隐藏终端问题难以定位碰撞故不适合。
  3. 隐藏终端形成的原因
    1. 无线网络传输中，由于障碍物等的存在，导致节点无法监听对方，故无法确定对方是否正在发送。
    2. 解决：4-frame-exchange
      1. 发送前，先发送 RTS，表示我准备好发送
      2. 对方回复 CTS，表示可以发送
      3. 发送 packet
      4. 对方回复 ACK
      5. 这样就能确定对方是否处于可以通信的状态，解决 hidden terminal 问题。
      1. A 发送 B（此时 C 不能发送）time 1
      2. C 发送 D，B 回复 ACK 给 A time 2
      3. A 发送新包给 B，D 回复 ACK 给 C time 3
      4. C 发送新包给 D，B 回复 ACK 给 A time 4
      5. 循环.... 根据此分析，最大速率为 0.5 message/n time slot

五

image.png|600 Flags: 有 3bits - reserve bit: 未用 - DF (Don't Frag) bit = 0 代表可以做 fragmentation，DF bit = 1 代表不能做 fragmentation。 - MF (More Frag) bit= 0 代表该数据包是整个数据流里面最后一个包，MF bit = 1 代表还有更多被 fragment 的数据包 - Fragment Offset：该片偏移原始数据包开始处的位置。偏移的字节数是该值乘以8。 - 非尾部分片 datagram 的 payload_len 数据量都应该是 8 的整数倍。 - ID image.png|600 - 拆分出的值一样 - 关于  Identification 字段。该字段占 16 bit，IP 软件在存储器中维持一个计数器，每产生一个数据报，计数器就加1，并将此值赋给标识字段。但这个“标识”并不是序号，因为 IP 是无连接服务，因此数据报不存在按序接收的问题。那么该字段究竟有什么用？当一个数据报长度过长，超过网络 MTU 而需要分片时，则把标识字段的值复制到所有分片数据报中，最后在目的设备才能依据标志字段而正确的重组数据报，因此该字段可以唯一标识某个 IP 报文。

  • Total Length：ip 包头和 ip 内容的总长度（不包括以太头）
    1. 转发过程中, Destination Mac address 和改变，具体是根据路由器存储更改。
    2. TTL 会更改：转发时候，TTL--
    3. Header Checksum 会更改（因为 IP 改变，校验和自然变）
    4. offset 会根据以太网传输 MTU 变化而变化，因为此 total length 也可能变化
    1. 每个包最多能装 1500-28=1472bytes
    2. 4000/1472=2.7173913, 故一共要 3 个子包
      1. subpacket 1, Length=1500,fragment flag：001, offset=0,ID=66
      2. subpacket 2, Length=1500,fragment flag: 001,offset=184,ID=66
      3. subpacket 3, Length=1056+28=1084,fragment flag: 000,offset=368,ID=66

六

image.png|600

  1. 对子网进行进一步划分 已知路由器子网号为 192.168.2.0/24 0000 0010 | 0000 0000 假设 192.168.2.0/24 为主网络，并将其划分为两个子网：
  2. 子网 1：192.168.2.0/25，可用地址范围 192.168.2.1 - 192.168.2.126。
  3. 子网 2：192.168.2.128/25，可用地址范围 192.168.2.129 - 192.168.2.254。 地址分配如下：
  4. Router：
    • 子网 1 接口：192.168.2.1/25
    • 子网 2 接口：192.168.2.129/25
  5. PC1：192.168.2.2/25
  6. PC2：192.168.2.3/25

  7. PC3：192.168.2.130/25 子网掩码均为 /25 (255.255.255.128)。

    1. 用子网掩码划分子网，非常高效（只需要用 & 操作就可以快速操作比较是否在一个子网）
    2. 同时方便更新子网
    3. 方便优化网络资源，分层转发。
    1. PC1 可以和 PC2 相互通信。他们在一个子网内，通信的包直接通过交换机，而不需要路由器将转发到自接口发回。
    2. PC1 可以和 PC3 相互通信与否取决于是否配置了转发表。他们不在一个子网内，需要路由器进行转发。
    1. PC1 到 PC2
      1. 他们在同一个子网，通过交换机转发。PC1->Switcher
      2. Switcher->PC2
    2. PC1 到 PC3
      1. 不在同一个子网，需要路由器转发
      2. PC1->Switcher
      3. Switcher->Router interface 1
      4. Router interface 1 -> Router interface 2
      5. Router interface 2->Switcher
      6. Switcher->PC3

七

image.png|600 - 1） 链路状态算法（OSPF）使用了 dijkstra 距离向量算法（DV）使用了 Bellman-Ford 链路状态算法维护一个全局的数据库，通过 LSU 数据包的 LSA 信息维护，用 dijkstra 生成路由表。收敛快，但是实现配置较为复杂 距离向量算法在每个节点维护距离向量，当距离向量发生改变的时候就发包通告邻居，并洪泛到整个体系。之后，根据距离向量信息利用 Bellman-Ford 计算。实现简单，但是收敛比较慢 - 2）使用链路状态算法写出路由器 B 中的路由信息的更新过程 - B 获取到邻居 A 和 E 发来的通告，得知 - B到 E 距离为 1 - B到 A 距离为 10 - B 通过 Dijkstra 算法，算出路由表 (0) - 同时，其他节点也在通过 LSA 完善链路数据库 - A 从 C 和 D 将知道自己到达 C 1，到达 D121 - 同理，E.. - B 得到更新后的路由表，得知到 C 的路由的下一跳是 E、到 D 的下一跳是 E 等.. - 最后稳定后，B 将获得稳定的链路数据库。 - 稳定的数据库是全局的信息。B 再运行一次dijkstra 将获得正确的路由表 - 3） - 假设使用距离向量算法并使用毒性逆转，提出 1 个引起计数到无穷问题的链路改变方式并说明理由 - image.png|600