一个概率论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 的一种方式,很多人梦寐以求的方向。

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

最近量子位又发了一篇体系结构的进步,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)工作原理

[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 绑定。

[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。可这比较容易被攻击。