电路设计漫谈之17 - 两个有趣的IP交换机电路

sun_ic

电路设计漫谈之17 - 两个有趣的IP交换机电路

有些很复杂的技术其原理大多时是很简单。但往往人们看看到的是问题解决的办法或实现
后的复杂样子，更糟糕的是对初学者或者初次从事该技术的工程师也从最后已经
实现的技术和系统讲解起。这往往忽略了问题的本质和技术的本来面目。始终认
为学数学物理前应该先读一本数学物理的发展史，了解当时科学家们遇到了什么
问题，受什么启发才发展出了相应的理论。不要一开始就微积分，量子力学方程
。电路技术也是一样。下边聊一下两个有意思的IP交换机原理和相应的电路。最
后的实现很复杂，但其原理是可以可日常生活中大家最熟悉的交通系统来对应的。

1）交换机的VOQ技术.

交换机可以等效成为一个N口入，N口出的简单模型。再简化一下可以等效成一个口
(称为接口A)入，N个口出的模型（图1）。一般从A口来的packet会在一个输入
buffer里暂存一下，然后做header分析，lookup等操作来决定每个packet应该送到哪个目的口输出。

假设有这种情况：某个目的口（B）大家都朝它送traffic造成了堵塞，但这时其它
目的口还是畅通的。 这时口A的buffer中送到口B的数据就要暂存一下直到口B解
除阻塞。而送到其它目的口的数据可以马上通过交换矩阵送出。可这时如果输入
口A只有一个buffer，送到口B的packet先来的，这样后来的送到其它目的口的packet
被阻塞住了，即使它们的目的口是畅通的也送不出去。这种现象叫HOL（head of line
blocking)。解决的办法可以借鉴交通道口的设计方式。

         

                 Fig1                                             Fig2A  


      

                       Fig2B                                     Fig3

我们看一下在图2A中所示的一个交通路口，南来的车道原来只有一条。想直行的
红色车由于是红灯等在了路口，虽然东西向的道路是畅通的，后边要右拐的车辆
也只好等在那。在图2B中，把南来的车道重新设计了一下。在路口前分出了几个
“缓冲车道”，每个方向一个或者若干个。这样即使出现上述情况，右转的车辆也
可以走了。在这里，东西北三个方向相当于交换机的目的口。南来的车道是口A。
南来车道的packet进入道口区域后根据去的目的口，分别放入相应的buffer（车道）。
这样就解决了前边提的HOL问题。

在交换机的设计中这种思想叫做VOQ（virtual output queue,虚拟的输出队列）
。即在每个输入口，根据输出的目的地建立相应的缓存器（FIFO或Queue）。
实际应用中还可以再根据packet的不同的优先级来进一步细分成更多的queue，
来支持QoS及Diffserv等功能。如图3所示.

电路设计时，一般是用一个大的DRAM来实现几千甚至几万以上的VOQ。DRAM一般
分成一个个基本的小片，根据VOQ的大小和多少动态的分配若干片给每个VOQ。这
就牵扯到存储片的分配，管理，回收，竞争等等。这时数据结构的一些思想可以
应用到这里了。本人始终认为利用DRAM实现动态管理的FIFO是logic设计的最高
境界之一。

2）交换机流量控制的Leaky Bucket技术

我们经常听到运营商说你付多少银子给你多少带宽。尤其是那种Ethernet to
home/building, 虽然传输带宽是100Mb/s但你实际得到的服务可能只是5M或者
10M之类。这种功能在交换机实现上成为rate limiting，flow control，等等。
这可以用高速公路入口的车辆控制来解释。

美国的高速公路入口是这么设计的。入口处有一个或者几个信号灯，根据拥堵的
情况每隔若干秒亮一次绿灯。每亮一次允许一辆车进入高速，以此达到控制流量
的目的。图4所示.

             

                     Fig4                                                Fig5

这个原理可以用到交换机的流量控制上。图5所示的一个篮子，每隔一定时间T朝
里边扔进去一定数量N的硬币￥。篮子下边有个固定大小的口，硬币以一定的流
量漏出篮子。每流出一个硬币就可以放行一个packet。大家可以看出，通过控制
篮子漏口的大小就可以控制每个口进入（或者流出）交换机的数据流量.

packet是先在buffer中暂存的。如果某时间来了一串bursty的packet，也是先存
在buffer里，再根据漏出的硬币一个个（或一次几个）把packet取出。这样也达
到了平滑数据流的作用。如果口开大了，放进篮子的硬币少或者更新的周期长，数据可能
从buffer中一次送一段后（bursty），停一段时间等篮子里有了新的硬币再继续送。调
节参数T/N/￥可以调节允许的流量和bursty的大小。更复杂点的流量控制还有
guaranteed   bandwidth, best effort bandwidth等。这可以采用dual leaky
bucket实现。一个篮子管保证的带宽控制，另一个篮子管best effort（不保证
，只有在网路不阻塞时提供服务）。

leaky bucket控制电路的设计其实就是一个计数器。这个计数器每隔一定时间T
赋一个值。之后每次减一。每减一次就允许一定数量的packet通过。减到0了就
要等下一次计数器赋值。实际应用中可能比这复杂，但基本原理如此。


当年上学看书学了不少数据处理交换机原理等，始终云里雾里的。尤其老师们总
是卖力的介绍协议中每个bit的意义。做了几轮项目后，才领悟出交换机的好多
原理其实跟公路交通的设计类似。如果我去做教师教这门课，我会从交通系统讲
起。用集装箱和或者车皮的原理类比IP/ATM的packet和cell。道路路口的设计类
比VOQ等输入/出口的数据处理。邮寄的快慢件处理类比数据优先级的处理。高速
路汇入车辆的控制类比flow/rate control等等。复杂的系统，原理一定都是很
简单的。只有简化到最简单的原理才算了解掌握。一开始千万不要被数学公式复
杂的协议灌晕了。

以前的漫谈：


电路设计漫谈之 1~9
http://bbs.eetop.cn/thread-178347-1-1.html


电路设计漫谈之10： 接地（1）
http://bbs.eetop.cn/thread-197205-1-1.html

电路设计漫谈之11：物联网大跃进http://bbs.eetop.cn/thread-251965-1-1.html


电路设计漫谈之12：高频喜欢低感抗，低频喜欢低(电)阻抗 - 再谈接地。http://bbs.eetop.cn/thread-253126-1-1.html

电路设计漫谈之13 - Accuracy/Precision 和数模系统的参数选择
http://bbs.eetop.cn/thread-257967-1-1.html


电路设计漫谈之14 - 放大器漫谈
http://bbs.eetop.cn/thread-260935-1-1.html


电路设计漫谈之15 - 同步/异步设计及metastability
http://bbs.eetop.cn/viewthread.php?tid=262937&highlight=%B5%E7%C2%B7%C9%E8%BC%C6%C2%FE%CC%B8%D6%AE15


电路设计漫谈之16 - （转贴）编程高手的故事和一些回忆http://bbs.eetop.cn/thread-287087-1-1.html

flyinghawk

好贴

deepsky

回复 1# sun_ic


   难得的好文章，楼主能否把相应的参考文献也贴出来下呢，想看看更具体的内容。

oliversitp

楼主的解释真是深入浅出,受益非浅!

skyeyes

学习学习

Juneje

Thanks for sharing

wangwhbet

学习了

窜天猴

好文章，收藏了