节点上万的网络，如何做流量控制？欢迎讨论

bigrong

这个帖子真该给那些野鸡厂，原厂看看，开发了半天，还不如人们用开源的方法搞得好，没面子极了！

skylove

原帖由 happyhunter 于 2006-12-19 19:09 发表
感谢bigrong兄的发言，很有启发和实用性。关于IDS联动的问题我这里已经实现，当然是厂家开发的，呵呵，和802.1X联动，IDS提交异常IP，通过snmp来关断端口（幸好全网交换机都支持snmp下发），这个思路我觉得是校园 ...

是这样的，如果您的内网是一个大的vlan内（有点猛，这么多机器同一个vlan），那么理论上是可以在网关机器上可以用tc工具作到流量控制，具体可以去看看cu上JohnBull先生翻译的那一本电子书，我自己本人也亲自尝试过，结果是在我的网络内会让nat效率受到一些影响，不过具体情况不同，您可以实际试一下。而且由于流量控制事实上是控发不控收的，所以对内网的客户端而言，只有是做到对控制它们的下载速度。如果nat后面还有不少小的vlan，那么就无法限制到每个最终ip，而只能在nat位置限制到每个vlan总的流量控制了。

sorry，回复完才发现，您上面提到过已经用tc做过流量整形了。。。那么，您首帖子提到过却是未用tc控制，有点矛盾。。。理论上，使用tc可以做，但是，即使是用哈希方式，大概每个ip还是得被查询40多次呢。。。绝对会影响到效率的。。。

[ 本帖最后由 skylove 于 2006-12-20 11:28 编辑 ]

platinum

原帖由 skylove 于 2006-12-20 11:14 发表
但是，即使是用哈希方式，大概每个ip还是得被查询40多次呢。。。

请教 skylove，这个是如何统计出来的？

skylove

原帖由 platinum 于 2006-12-20 13:09 发表

请教 skylove，这个是如何统计出来的？

万node，分成子网大概是 40多个 /24 的子网。。。 哈希的做法可以做到以 最后的ip位来进行判断，然后再丢到相关的子表里去

比如
     ....
     192.168.11.33
        ....
       192.168.44.32
       192.168.44.32

那么要查192.168.44.33 的限制，那么就先进入 33 表（1-255，一共255个表），然后33表里有40多条记录

192.168.1.33
...
192.168.11.33
...
192.168.44.33

所以从上到下就得查40多次咯。

当然或许可以再改良一下的。。。 我这里只是例举了最标准的做法，没有试着研究划分2级子表。。。 因为想来把1w多个ip划分在同一个子网里。。。真的是很疯狂也。。。寒

platinum

如果是 hash 的话，通过巧妙的算法直接可以通过下标找到元素位置，不是你说的线性搜索，除非碰撞了
所以不可能是 40 多次

skylove

原帖由 platinum 于 2006-12-20 14:23 发表
如果是 hash 的话，通过巧妙的算法直接可以通过下标找到元素位置，不是你说的线性搜索，除非碰撞了
所以不可能是 40 多次

我上面提到了，没有分2级表。。。 如果分了，就是你说的这样了， 问题是在于前提—— 1w多个ip在一个vlan内本身会造成多大的麻烦，其次才是关于流控tc这里的算法问题了。 况且—— 搜索固然需要时间，“巧妙的算法”就不需要计算时间？

platinum

我上面提到了，没有分2级表。。。 如果分了，就是你说的这样了

这句我没有明白

况且—— 搜索固然需要时间，“巧妙的算法”就不需要计算时间？

不知道你是否理解 hash 的原理，根据我的理解，只要内存足够大，hash 检索的时间几乎可以忽略不计，比如大数组下标

skylove

原帖由 platinum 于 2006-12-20 15:56 发表

这句我没有明白


不知道你是否理解 hash 的原理，根据我的理解，只要内存足够大，hash 检索的时间几乎可以忽略不计，比如大数组下标

12.4. 当过滤器很多时如何使用散列表
如果你需要使用上千个规则——比如你有很多需要不同QoS的客户机——你可
能会发现内核花了很多时间用于匹配那些规则.
缺省情况下,所有的过滤器都是靠一个链表来组织的,链表按priority的降序排
列.如果你有1000个规则,那么就有可能需要1000次匹配来决定一个包如何处
理.
而如果你有256个链表,每个链表4条规则的话,这个过程可以更快.也就是说
如果你能把数据包放到合适的链表上,可能只需要匹配4次就可以了.
利用散列表可以实现.比如说你有1024个用户使用一个Cable MODEM,IP地
址范围是1.2.0.0到1.2.3.255,每个IP都需要不同容器来对待,比如"轻量级",
"中量级"和"重量级".你可能要写1024个规则,象这样:
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.1 classid 1:1
...
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.3.254 classid 1:3
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.3.255 classid 1:2
为了提高效率,我们应该利用IP地址的后半部分作为散列因子,建立256个散
列表项.第一个表项里的规则应该是这样:
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.1.0 classid 1:1
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.2.0 classid 1:3
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.3.0 classid 1:2
下一个表项应该这么开始:
# tc filter add dev eth1 parent 1:0 protocol ip prio 100 match ip src \
1.2.0.1 classid 1:1
...
这样的话,最坏情况下也只需要4次匹配,平均2次.
70
具体配置有些复杂,但是如果你真有很多规则的话,还是值得的.
我们首先生成root过滤器,然后创建一个256项的散列表:
# tc filter add dev eth1 parent 1:0 prio 5 protocol ip u32
# tc filter add dev eth1 parent 1:0 prio 5 handle 2: protocol ip u32 divisor 256
然后我们向表项中添加一些规则:
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.0.123 flowid 1:1
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.1.123 flowid 1:2
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.3.123 flowid 1:3
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 2:7b: \
match ip src 1.2.4.123 flowid 1:2
这是第123项,包含了为1.2.0.123,1.2.1.123,1.2.2.123和1.2.3.123准备的匹配
规则,分别把它们发给1:1,1:2,1:3和1:2.注意,我们必须用16进制来表示
散列表项,0x7b就是123.
然后创建一个"散列过滤器",直接把数据包发给散列表中的合适表项:
# tc filter add dev eth1 protocol ip parent 1:0 prio 5 u32 ht 800:: \
match ip src 1.2.0.0/16 \
hashkey mask 0x000000ff at 12 \
link 2:
好了,有些数字需要解释.我们定义散列表叫做"800:",所有的过滤都从这里
开始.然后我们选择源地址(它们位于IP头的第12,13,14,15字节),并声明
我们只对它的最后一部分感兴趣.这个例子中,我们发送到了前面创建的第2个
散列表项.
这比较复杂,然而实际上确实有效而且性能令人惊讶.注意,这个例子我们也可
以处理成理想情况——每个表项中只有一个过滤器!

======================================
以上是转自高级路由流量控制的， 如果要所有ip都使用一个规则：比如所有ip出口都控制在50k （不要惊讶，对于lz的网络同时在线的，如果想平均分配，也就这么点带宽了），那么的确简单 hashkey那里的 mask修改地大一些，全部匹配进去就ok了，这就是你所谓的快速；但是，真正实施的时候，经常是针对着不同的区域乃至不同的用户来进行流量控制的（我们这里按照lz的想法，不在下面的switch上做qos，所有的qos都在nat位置做），那么势必就需要增多规则，并将不同的ip划分到不同的规则里，需要不同的hashkey mask了，确认否？然后再仔细一点，教工区的行政/教师办公/乃至给敬爱的校长大人们是否又需要特别地设置不同地带宽（要真够胆子让校长家/办公室只有那么点平均带宽，怕是年终考评不想及格了！？）？ 这样仔细地分下去，那么到最后很可能需要的就是一段ip乃至一个ip就需要一个特别的hashkey mask，也就是说针对每个ip需要独立而且不同的流量控制了~~~ 这时候散列表的需求就出来了。 说得明白否？

platinum

原先看的时候始终没有明白那段话的意思，现在终于明白了，谢谢 skylove ^_^