Category: Network

Posted on

一个概率论Bound问题

昨晚和以前实习的同学讨论一个上界的问题，如果在未来博士的过程中也能有这样的氛围就好了。

主要就是一道概率论题

已知\(\begin{array}{l}A \sim B i n o m(n, p) \ B \sim B i n o m(\frac{A(A-1)} 2, q)\end{array}\)，求H（B），即B的entropy。

这里的难点是如何求二项随机分布的二项分布。直观上感觉后者的熵值是前者的 \(log(log())\) 这种。可对A的展开太过繁琐。敲在mathmetica当中可以是 \(P(B=i) = Sum[P(B=i|A=j)*P(A=j),{j,0,n}]\)，暂时我只想到这种解法。

这个问题我找了找网络前两节课上的信息论推荐的书，上面有类似对于二项式分布的相关性质，可是唯一提到的也就是在 \(p\) 上做文章。fix n，H（A）的 max 在 p 取 \(\frac12\) 时取到。然而没啥卵用。

概率论与图论背后的算法

算这个事为了做一个算法去recover这个
ER random graph，given每次只能query graph的一小部分里面有没有edge的存在。

这个 random graph 很有名，很多概率图都是基于此。也是 TCS 求 lower bound 的一种方式，很多人梦寐以求的方向。

Posted on

谈体系结构的进步对网络的影响

最近量子位又发了一篇体系结构的进步，TCAM，所谓的三态内容寻址储存器。可以说，从图灵机的角度来说，上层建筑下的基层还有很多没有解决，从现在那么多Startup 在真正的做业务Oriented 的数据库及网络链路优化，体系结构还有很多可以探索的部分。同时，新的架构真的是否安全，如TPU的数据通路是否有没有被侦测到的部分可以被攻击。多数的攻击来自于软硬结合，汇集了多少工程师的智慧结晶。

交换机的简化结构


这是一个去掉2个要素的冯诺伊曼体系结构图，交换机的OutBound 和Input的Throughput是显见的bottleneck，除此之外还有延时，这就需要主存储器性能或者包的传输协议的革新。

三态内容寻址储存器（TCAM）

我在当年写VB的时候记得有个slide的参数，是一个三进制数来表示不动，向上滑和向下滑的参数。而这种0、-1，1三进制在苏联当年的计算设备上有所尝试，可惜最终失败了。0.5或许是更好的一种表示中间态或者亚稳态的编码方式，可以用于模糊匹配，或者Not Set。

CAM本质上是一个数据查找硬件方法，读写数据的速度与RAM相同，查找数据能相对模糊的匹配到数据。

这时ARP 协议从报头或者CRC来验证数据正确性起到了很大的作用，就是不管怎样，数据到了，不管对不对，以最快的速度发出去，等到了再做检验的思路是一样的。（有点像高频交易架构的gateway。

Reference

  1. Constant-time Alteration Ternary CAM with Scalable In-Memory Architecture
  2. 三态内容寻址存储器(TCAM)工作原理
Posted on

[Network] 网络链路层路由算法总结

Routing protocols

  • Routing information protocols（RIP）
    • Algorithm: Distance Vector
  • Open Shortest Path First (OSPF)
    • Algorithm: Link State
  • BorderGatewayProtocol (BGP)
    • Another type of vector Routing: widely used in the AS Protocals
    • demo
    • Problem with integrate wit intra domain Routing
      • static method ALL unknown IPs send to D.
      • Entry Translation: high cost
      • interior BGP

ARP

之前打ctf 的时候搞过这个协议，主要是在MAC 层能对网卡欺骗，从而把destination 当成自己，就能抓取同路由器下的其他设备的包。

这种需要规避就得ip-mac 绑定。

Posted on

[Network] 几个Mac层的协议

我校网络老师不太Care 概率模型下的网络分析，只Care 实现。（但是我最近正好在学概率统计，权当一道作业题复习

ALOHA协议

主要思路就是让所有能发的人都发，有错误就随机掷骰子决定发送，如果碰撞，随机范围翻倍再掷骰子。


可问题是，非常容易冲突。

如果我们做一道概率题。

  1. 帧时T：发送一个标准长的帧所需的时间
  2. 吞吐率S：在一个帧时T内发送成功的平均帧数（0<S<1，S=1时信道利用率100%）
  3. 运载负载G：一个帧时T内所有通信站总共发送的帧平均值（包括原发和重发帧）（G≥S，G=S表示无冲突）
  4. P0：一帧发送成功（未发生冲突）的概率，发送成功的分组在已发送分组的总数中所占的比例；公式：S = G*P0

两个标准长的帧才会第二次碰撞，舍冲突危险期为2T，同时设这是的帧平均值为2G一个T内生成k个帧到的概率符泊松分布。

由柏松分布可知：

\(\operatorname{Pr}[\mathrm{k}]=\frac{\mathrm{G}^{\mathrm{k}} \mathrm{e}^{-\mathrm{G}} }{ \mathrm{k} !}\)

\(P(\text{success in 2T})=Pr(0)\times Pr(0)=e^{-2G}\)

带入S= G*P0 得
\(\mathrm{S}=\mathrm{Ge}^{-2 \mathrm{G}}\)

最高信道利用率是18.4%

Time-slotted ALOHA

  1. 分隙ALOHA是把时间分成时隙（时间片），时隙的长度对应一帧的传输时间
  2. 新帧的产生是随机的，但分隙ALOHA不允许随机发送，凡帧的发送必须在时隙的起点
  3. 冲突只发生在时隙的起点，冲突发生时只浪费一个时隙，一旦某个站占用时隙并发送成功，则在该时隙内不会出现冲突

显然刚刚 \(P(\text{success in 2T})=Pr(0)=e^{-G}\), \(S=\mathrm{Ge}^{-2 \mathrm{G}}\)
最高信道利用率是36.8%

CSMA/CD

一种带有冲突检测的载波监听多路访问，可以检测Mac传输的冲突。

主要流程是

  • 以广播发，看看有无其他节点（carrier sense）没有其他包就发包。
  • 检测 carrier detection。 如果碰撞再广播碰撞了。然后掷骰子重新发包
  • 15次失败报告timeout

CSMA/CA

WLAN 中实现不了CSMA/CD 主要原因是有hidden和exposed 的情况。一种不太好的解决方法是RTS-CTS。可这比较容易被攻击。