一个概率论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
- Constant-time Alteration Ternary CAM with Scalable In-Memory Architecture
- 三态内容寻址存储器(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
- static method ALL unknown IPs send to D.
ARP
之前打ctf 的时候搞过这个协议,主要是在MAC 层能对网卡欺骗,从而把destination 当成自己,就能抓取同路由器下的其他设备的包。
这种需要规避就得ip-mac 绑定。
[Network] 几个Mac层的协议
我校网络老师不太Care 概率模型下的网络分析,只Care 实现。(但是我最近正好在学概率统计,权当一道作业题复习
ALOHA协议
主要思路就是让所有能发的人都发,有错误就随机掷骰子决定发送,如果碰撞,随机范围翻倍再掷骰子。
可问题是,非常容易冲突。
如果我们做一道概率题。
- 帧时T:发送一个标准长的帧所需的时间
- 吞吐率S:在一个帧时T内发送成功的平均帧数(0<S<1,S=1时信道利用率100%)
- 运载负载G:一个帧时T内所有通信站总共发送的帧平均值(包括原发和重发帧)(G≥S,G=S表示无冲突)
- 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
- 分隙ALOHA是把时间分成时隙(时间片),时隙的长度对应一帧的传输时间
- 新帧的产生是随机的,但分隙ALOHA不允许随机发送,凡帧的发送必须在时隙的起点
- 冲突只发生在时隙的起点,冲突发生时只浪费一个时隙,一旦某个站占用时隙并发送成功,则在该时隙内不会出现冲突
显然刚刚 \(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。可这比较容易被攻击。