CN100499647C - 高效处理路由聚合的方法及设备 - Google Patents
高效处理路由聚合的方法及设备 Download PDFInfo
- Publication number
- CN100499647C CN100499647C CNB200410006584XA CN200410006584A CN100499647C CN 100499647 C CN100499647 C CN 100499647C CN B200410006584X A CNB200410006584X A CN B200410006584XA CN 200410006584 A CN200410006584 A CN 200410006584A CN 100499647 C CN100499647 C CN 100499647C
- Authority
- CN
- China
- Prior art keywords
- route
- polymerization
- concrete
- property
- aggregation
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000012545 processing Methods 0.000 title claims abstract description 37
- 230000002776 aggregation Effects 0.000 title claims abstract description 32
- 238000004220 aggregation Methods 0.000 title claims abstract description 32
- 238000000034 method Methods 0.000 title claims abstract description 18
- 238000006116 polymerization reaction Methods 0.000 claims description 147
- 238000013507 mapping Methods 0.000 claims description 40
- 238000012217 deletion Methods 0.000 claims description 20
- 230000037430 deletion Effects 0.000 claims description 20
- 238000007792 addition Methods 0.000 claims description 12
- 230000008859 change Effects 0.000 claims description 8
- 230000008569 process Effects 0.000 description 6
- 238000011282 treatment Methods 0.000 description 5
- 238000012360 testing method Methods 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 2
- 238000012423 maintenance Methods 0.000 description 2
- 230000004044 response Effects 0.000 description 2
- 230000008901 benefit Effects 0.000 description 1
- 230000033228 biological regulation Effects 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 239000012467 final product Substances 0.000 description 1
- 230000003993 interaction Effects 0.000 description 1
- 230000002452 interceptive effect Effects 0.000 description 1
- 230000006855 networking Effects 0.000 description 1
- 230000001172 regenerating effect Effects 0.000 description 1
- 230000006641 stabilisation Effects 0.000 description 1
- 238000011105 stabilization Methods 0.000 description 1
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
本发明提供了一种高效处理路由聚合的方法及设备，属于计算机网络通信领域。该方法为每一个聚合路由建立与其下属具体路由属性继承的映射关系，当网络拓扑发生变化，路由振荡时，同步更新聚合路由的属性信息，生成或删除属性映射关系，当需要计算聚合路由的属性时，重新进行聚合路由的属性计算，保存结果信息，并通过在聚合路由中增加属性映射表，用于维护与其下属具体路由属性的映射关系。由于保存了路由聚合属性计算的中间变量而非最终结果，废除聚合路由的时间消耗与其下属具体路由条数之间的线性关系，即以空间换取时间，最终实现提高路由聚合的处理效率。
Description
所属技术领域
本发明属于计算机网络通信领域，具体涉及一种BGP高效处理路由聚合的解决方法及设备。
背景技术
BGP(边界网关协议)作为一类用于在自治系统间实现路由发现与传递的EGP协议，常常工作在网络的核心层。该协议交互和维护的路由数目很多，据统计，目前Internet网的路由已经超过了10万条，而且这个数字还将继续增长，路由数目的持续增长，路由表的急剧膨胀，给传统的BGP路由交互方式带来了挑战。
在这种情况下，聚合被广泛应用于BGP协议，聚合就是将具体路由归纳成更为抽象的路由，从而大大地减少BGP向外通告路由的数目，并最终有效地减小路由表的空间消耗，在实际的组网应用中，聚合是一个非常有用且常被使用的功能。
对于聚合，协议中有如下规定：只有当聚合地址覆盖至少一条具体路由时，聚合地址对应的路由(即聚合路由)方可生效；另外，在策略允许的情况下，聚合路由需要继承所有下属的具体路由的属性信息。从上面的约定中，不难看出，任何一条具体路由的增删，都有可能触发聚合路由的相关处理，即聚合路由需要对下属具体路由属性进行继承。传统的聚合采取以下方式实现：当具体路由增加或者删除时，首先删除之前产生的所有聚合路由，随后，根据当前BGP路由表的信息，重新生成新的聚合路由(当然，前提条件是该聚合地址至少覆盖一条具体路由)。这样做的好处不言而喻：流程简单。BGP协议不用为聚合路由专门维护其下属具体路由的属性信息，在每一次具体路由的增加、删除后，聚合路由都在执行先删除后添加的过程，在聚合路由添加的同时，实现了属性信息的继承和同步。但缺点也是明显的，由于每一条具体路由的增删，都将触发聚合路由的删除，并重新计算、生成新的属性信息，所以，效率低下。
举个例子，当第一条具体路由增加，聚合路由在重新生成时，需要继承所有下属具体路由的属性信息，由于当前只有一条被覆盖的具体路由，因此属性计算需要1次；当第二条具体路由增加时，聚合路由需要先删除再添加。属性生成过程中，由于覆盖了两条具体路由，因此需要计算2次；以此类推，当第N条具体路由增加时，聚合路由的属性则需计算N次。假设每一次属性计算的时间均为T，忽略聚合路由删除过程的时间消耗，当N条被聚合地址覆盖的具体路由添加时，聚合模块处理的时间为T*n*(n+1)/2，效率的低下，可见一斑。
通过实地的测试，进一步验证了上述的结论。
测试环境：100条路由，连续增删1000次
1.没有配置任何聚合的情况下，处理时间约为41s；
2.配置一个聚合地址时，处理时间约为380s；
3.配置两个聚合地址时，处理时间约为710s；
修改一下测试环境，如果当前只配置了一个聚合地址，且这条聚合地址覆盖了十万条具体路由，路由仍然振荡1000次，聚合的处理需要大约12年。这显然不是我们所希望的，所以，如何高效的处理路由聚合，就成了每一个网络设备供应商首当其冲应该考虑的问题。
发明内容
本发明能有效的解决上述由于聚合的出现所引发的BGP处理效率低下的问题，提供了一种高效处理BGP路由聚合的解决方法及设备。
本发明的技术内容：一种高效处理路由聚合的方法，包括：
(1)为每一个聚合路由建立与其下属具体路由属性继承的映射关系；
(2)当网络拓扑发生变化，路由振荡时，同步更新聚合路由的属性信息，并生成或删除属性映射关系；
(3)当需要计算聚合路由的属性时，重新进行聚合路由的属性计算，并保存结果信息。
所述步骤(1)包括：
a.在处理每一条具体路由时，将其对应的所有属性信息放入公共缓冲池中，进行暂存；同时，增加引用计数信息，记录此条属性信息被路由引用的情况；
b.聚合路由在继承其下属所有具体路由的属性信息时，只需要维护聚合路由与其下属具体路由属性之间的映射关系，使得每一条聚合路由都能够清楚的知道其所有下属具体路由的属性信息；
c.当一条具体路由对应的属性信息也同时被聚合路由所继承时，需要递交公共缓冲池中，记录该具体路由属性的引用计数。
所述步骤(2)为：当新配置了一条聚合地址表项，需要遍历本地路由信息库，生成实时的属性映射关系；当取消一条聚合地址表项的配置时，需要删除聚合路由，废除聚合路由与其下属具体路由属性的映射关系。
一种高效处理路由聚合的设备，包括BGP聚合路由处理模块，在BGP聚合路由处理模块内增加构造一为每一个聚合路由建立与其下属具体路由属性继承映射关系的聚合路由属性映射表。
进一步包括一聚合路由增删仲裁模块，用于判断是否有新的符合条件的聚合路由生成，或是否触发对原聚合路由的撤销。
进一步包括一聚合路由属性计算仲裁模块，用于判断是否需要聚合路由属性的重新计算。
本发明的技术效果：通过在聚合路由中，增加建立聚合路由与其下属具体路由属性继承的映射关系，通过维护与其下属具体路由属性的映射关系，废除聚合路由的时间消耗与其下属具体路由条数之间的线性关系，即保存了属性计算的中间变量而非最终结果，实现二者之间的线性无关，以空间换取时间，最终实现聚合路由与其下属具体路由的时间复杂度由当前的O(n)转变为O(1)，从而，高效地提高路由聚合的处理效率。
附图说明
图1是本发明中聚合路由属性与具体路由属性的映射关系示意图；
图2是本发明中路由变化在聚合模块中处理的流程示意图；
图3是本发明中聚合路由属性计算处理的流程示意图。
具体实施方式
BGP高效处理路由聚合的一种解决办法包括以下步骤：
参考图1，为每一个聚合路由建立与其下属具体路由属性继承的映射关系。在每一条具体路由中，都会保存自己的属性信息，从而表明具体路由的特性；在本地路由信息库中，具体路由属性信息的存储是必不可少的。同时，聚合路由将继承所有下属具体路由的属性信息，因此，如果在聚合路由中保存一个关于下属具体路由属性的映射表，通过此映射表，可以简单、快捷地定位到具体路由属性的字段信息，最终实现在聚合路由中，只保存属性计算所要用到的中间变量，即各具体路由的属性信息。
当网络拓扑发生变化，路由振荡时，调用BGP聚合处理的仲裁模块，得出该具体路由在聚合模块中需要进行何种处理的结论：如果此具体路由增加，同时聚合仲裁模块的结论是需要同步更新聚合路由的属性信息，则遍历本地路由信息库，对符合条件的聚合路由，在其属性映射表中，增加对此新路由的属性映射关系；如果此具体路由撤销，同时聚合仲裁模块的结论是需要同步更新聚合路由的属性信息，则遍历本地路由信息库，对符合条件的聚合路由，在其属性映射表中，去除对此具体路由的属性映射关系。其处理过程为：
a.在处理每一条具体路由时，将其对应的所有属性信息放入公共缓冲池中，进行暂存；同时，增加引用计数信息，记录此条属性信息被路由引用的情况；
b.聚合路由在继承其下属所有具体路由的属性信息时，只需要维护聚合路由与其下属具体路由属性之间的映射关系，使得每一条聚合路由都能够清楚的知道其所有下属具体路由的属性信息；
c.当一条具体路由对应的属性信息也同时被聚合路由所继承时，需要递交公共缓冲池中，记录该具体路由属性的引用计数。
参考图2，当收到一条具体路由的变化信息后，将送交聚合仲裁模块，进行仲裁，确定该具体路由是否需要进行聚合处理：如果不需要聚合处理，则直接退出聚合处理模块；否则，需要进行聚合处理，还需进一步区分此具体路由的变化类型：如果是路由更新，则需要确定是否触发新聚合路由的生成，并更新聚合路由中属性映射表的关系；如果是路由的撤销，则要在更新聚合路由属性映射表之后，判断是否触发对原聚合路由的撤销。即增加一聚合路由增删仲裁模块，用于判断是否有新的符合条件的聚合路由生成，或是否触发对原聚合路由的撤销。
当有一条具体路由发生变化，需要将其送交聚合仲裁模块，进行决策。如果此时用户配置了聚合地址，同时，该聚合地址覆盖了此具体路由，则需要对此具体路由执行聚合处理；否则，无需进行聚合处理。
在对此具体路由进行聚合处理过程中，需要进一步区分此具体路由的变化类型：如果此具体路由为路由更新，则需要首先送交聚合路由增删仲裁模块，确定是否有新的符合条件的聚合路由生成；随后，更新聚合路由的属性映射表，将此具体路由的属性信息映射到聚合路由的属性映射表中，最终实现聚合路由对此具体路由属性信息的继承；如果此时具体路由为撤销路由，则首先进行聚合路由属性映射表的更新操作，去除关于此具体路由的属性映射关系；随后，仍然需要送交聚合路由增删仲裁模块，判断是否触发对已存在聚合路由的删除处理。
其中，关于聚合配置响应的处理过程：当新配置了一条聚合地址表项，需要遍历本地路由信息库，对其聚合地址覆盖的各个具体路由，主动调用上述的变化路由处理响应过程，其中，路由的变化事件为路由更新；从而实现为当前新配置下的聚合路由，生成实时的属性映射关系；当取消一条聚合地址表项的配置时，需要删除聚合路由，同时，废除聚合路由属性映射表中维护的与其下属具体路由属性的映射关系。
当本地需要向外通告聚合路由抑或本地在进行聚合路由的显示时，需要计算出当前聚合路由属性的结果信息，用于BGP路由报文的构造以及显示；基于效率的考虑，在此增加一个聚合路由属性计算仲裁模块，用以决策是否必须需要聚合路由属性的重新计算，对于必须的，则重新进行计算，并保存结果信息；而对于不是必须的，则只需取出之前的结果信息即可，从而，尽可能的减少了聚合路由属性计算的次数，再次提高了路由聚合的处理效率。
参考图3，在所有可能需要对聚合路由属性计算的地方，调用聚合属性重新计算仲裁模块进行处理：如果仲裁结论是需要对属性进行重新计算，则计算聚合路由的属性，并保存结果信息，以减少网络稳定时，多次计算聚合路由属性的可能；如果仲裁结论是不需要对属性进行重新计算，则直接使用之前计算的结果信息，无需对此再做任何后续操作。
下面以一条路由处理为例，简单说明一下具体的处理过程：
当有一条具体路由发生变化，需要将其送交聚合仲裁模块，进行决策。如果此时用户配置了聚合地址，同时，该聚合地址覆盖了此具体路由，则需要对此具体路由执行聚合处理；否则，无需进行聚合处理；
在聚合路由中保存一个关于下属具体路由属性的映射表，在对此具体路由进行聚合处理过程中，如果此具体路由为路由更新，则需要首先送交聚合路由增删仲裁模块，确定是否有新的符合条件的聚合路由生成；随后，更新聚合路由的属性映射表，生成实时的属性映射关系；如果此时具体路由为撤销路由，则首先进行聚合路由属性映射表的更新操作，去除关于此具体路由的属性映射关系；随后，仍然需要送交聚合路由增删仲裁模块，判断是否触发对已存在聚合路由的删除处理。
当需要计算聚合路由的属性时，调用聚合属性重新计算仲裁模块进行处理：如果仲裁结论是需要对属性进行重新计算，则计算聚合路由的属性，并保存结果信息；如果仲裁结论是不需要对属性进行重新计算，则直接使用之前计算的结果信息，无需对此再做任何后续操作。
Claims (5)
1.一种高效处理路由聚合的方法，其特征在于：
(1)为每一个聚合路由建立与该聚合路由的下属具体路由属性继承的映射关系；
(2)当网络拓扑发生变化，路由振荡时，调用BGP聚合处理的仲裁模块，得出该具体路由在聚合模块中需要进行何种处理的结论，如果需要同步更新该聚合路由的属性信息，则通过聚合路由增删仲裁模块的判断，同步更新该聚合路由的属性信息，并生成或删除属性映射关系；
(3)当需要计算聚合路由的属性时，重新进行聚合路由的属性计算，并保存结果信息。
2.如权利要求1所述的高效处理路由聚合的方法，其特征在于：所述步骤(1)包括：
a.在处理每一条具体路由时，将其对应的所有属性信息放入公共缓冲池中，进行暂存，并增加引用计数信息；
b.聚合路由在继承其下属所有具体路由的属性信息时，只需要维护聚合路由与其下属具体路由属性之间的映射关系；
c.当一条具体路由对应的属性信息也同时被聚合路由所继承时，需要递交公共缓冲池中，记录该具体路由属性的引用计数。
3.如权利要求1或2所述的高效处理路由聚合的方法，其特征在于：所述步骤(2)为：当新配置了一条聚合地址表项时，遍历本地路由信息库，生成实时的属性映射关系；当取消一条聚合地址表项的配置时，删除聚合路由，废除聚合路由与其下属具体路由属性的映射关系。
4.一种高效处理路由聚合的设备，包括BGP聚合路由处理模块，其特征在于：在BGP聚合路由处理模块内包括：为每一个聚合路由建立与其下属具体路由属性继承映射关系的聚合路由属性映射表；
所述高效处理路由聚合的设备还包括聚合仲裁模块和聚合路由增删仲裁模块，其中，所述聚合仲裁模块，用于当网络拓扑发生变化，路由振荡时，确定该具体路由是否需要进行聚合处理，如果需要且需要同步更新该聚合路由的属性信息，则同步更新该聚合路由的属性信息，并生成或删除属性映射关系；所述聚合路由增删仲裁模块，用于判断是否有新的符合条件的聚合路由生成，或是否触发对原聚合路由的撤销。
5.如权利要求4所述的高效处理路由聚合的设备，其特征在于：进一步包括一聚合路由属性计算仲裁模块，用于判断是否需要聚合路由属性的重新计算。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CNB200410006584XA CN100499647C (zh) | 2004-03-09 | 2004-03-09 | 高效处理路由聚合的方法及设备 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CNB200410006584XA CN100499647C (zh) | 2004-03-09 | 2004-03-09 | 高效处理路由聚合的方法及设备 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN1561063A CN1561063A (zh) | 2005-01-05 |
| CN100499647C true CN100499647C (zh) | 2009-06-10 |
Family
ID=34439809
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CNB200410006584XA Expired - Fee Related CN100499647C (zh) | 2004-03-09 | 2004-03-09 | 高效处理路由聚合的方法及设备 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN100499647C (zh) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102724130B (zh) * | 2012-06-28 | 2016-01-20 | 杭州华三通信技术有限公司 | 一种bgp路由管理方法和路由设备 |
| CN107547374B (zh) * | 2017-06-01 | 2020-04-28 | 新华三技术有限公司 | 一种聚合路由处理方法和装置 |
| CN108696433B (zh) * | 2018-07-24 | 2021-04-06 | 新华三技术有限公司 | 路由振荡抑制方法及bgp路由设备 |
| CN112468395B (zh) * | 2020-12-08 | 2022-07-01 | 信而泰(无锡)信息技术有限公司 | 边界网关协议bgp路由的处理方法和装置 |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1408160A (zh) * | 1999-12-06 | 2003-04-02 | 艾利森电话股份有限公司 | 特定网中的路由更新 |
| CN2687973Y (zh) * | 2004-03-09 | 2005-03-23 | 港湾网络有限公司 | 高效处理路由聚合的设备 |
-
2004
- 2004-03-09 CN CNB200410006584XA patent/CN100499647C/zh not_active Expired - Fee Related
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1408160A (zh) * | 1999-12-06 | 2003-04-02 | 艾利森电话股份有限公司 | 特定网中的路由更新 |
| CN2687973Y (zh) * | 2004-03-09 | 2005-03-23 | 港湾网络有限公司 | 高效处理路由聚合的设备 |
Also Published As
| Publication number | Publication date |
|---|---|
| CN1561063A (zh) | 2005-01-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Mukherjee et al. | Survey of fog computing: Fundamental, network applications, and research challenges | |
| Paganini | A global stability result in network flow control | |
| CN110213036B (zh) | 基于物联网雾计算-边缘计算的安全数据存储和计算方法 | |
| CN105429811B (zh) | 网络管理系统及方法 | |
| CN110392108A (zh) | 一种公有云网络负载均衡系统架构及实现方法 | |
| CN108027805A (zh) | 数据网络中的负载分发 | |
| JP6176245B2 (ja) | 制御装置、通信システム、スイッチ制御方法及びプログラム | |
| CN101895482A (zh) | 对点到点技术网络的逻辑拓扑信息进行抽象的方法和装置 | |
| CN106528289A (zh) | 资源的操作处理方法及装置 | |
| CN107707557A (zh) | 匿名访问方法、装置、网络设备及可读存储介质 | |
| Rodrigues et al. | Performance and availability evaluation of an smart hospital architecture | |
| CN107220259A (zh) | 一种数据库扩展系统、设备和用于扩展数据库的方法 | |
| Singh et al. | QoS-aware optical fog-assisted cyber-physical system in the 5g ready heterogeneous network | |
| CN105872110A (zh) | 一种云平台服务管理方法及装置 | |
| CN100499647C (zh) | 高效处理路由聚合的方法及设备 | |
| Jiang et al. | QoS constraints-based energy-efficient model in cloud computing networks for multimedia clinical issues | |
| CN103795770B (zh) | 在网络基础设施中提供高速缓存服务的方法和装置 | |
| Holme et al. | An integrated model of traffic, geography and economy in the internet | |
| Ren et al. | Broadcast tree construction framework in tactile internet via dynamic algorithm | |
| Kumar et al. | Scalable key parameter yield of resources model for performance enhancement in mobile cloud computing | |
| CN101729413A (zh) | 基于atca的多业务处理系统及方法 | |
| CN2687973Y (zh) | 高效处理路由聚合的设备 | |
| CN104838624A (zh) | 一种控制业务数据在虚拟网络中转发的方法、装置及系统 | |
| Sajnani et al. | Secure workflow scheduling algorithm utilizing hybrid optimization in mobile edge computing environments | |
| Arabas et al. | Router activation heuristics for energy-saving ECMP and valiant routing in data center networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| ASS | Succession or assignment of patent right |
Owner name: HUAWEI TECHNOLOGY CO., LTD. Free format text: FORMER OWNER: GANGWAN NETWORK CO., LTD. Effective date: 20060922 |
|
| C41 | Transfer of patent application or patent right or utility model | ||
| TA01 | Transfer of patent application right |
Effective date of registration: 20060922 Address after: 518129 Bantian HUAWEI headquarters office building, Longgang District, Guangdong, Shenzhen Applicant after: Huawei Technologies Co., Ltd. Address before: 100089, No. 21 West Third Ring Road, Beijing, Haidian District, Long Ling Building, 13 floor Applicant before: Harbour Networks Holdings Limited |
|
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| ASS | Succession or assignment of patent right |
Owner name: HUAWEI DIGITAL TECHNOLOGY CO., LTD. Free format text: FORMER OWNER: HUAWEI TECHNOLOGY CO., LTD. Effective date: 20100612 |
|
| C41 | Transfer of patent application or patent right or utility model | ||
| COR | Change of bibliographic data |
Free format text: CORRECT: ADDRESS; FROM: 518129 HUAWEI HEADQUARTER BUILDING, BANTIAN, LONGGANG DISTRICT, SHENZHEN CITY, GUANGDONG PROVINCE TO: 100085 NO.3, XINXI ROAD, SHANGDI, HAIDIAN DISTRICT, BEIJING |
|
| TR01 | Transfer of patent right |
Effective date of registration: 20100612 Address after: 100085 Beijing, Haidian District on the road, No. 3 Patentee after: Huawei Digit Technology Co., Ltd. Address before: 518129 Bantian HUAWEI headquarters office building, Longgang District, Guangdong, Shenzhen Patentee before: Huawei Technologies Co., Ltd. |
|
| C17 | Cessation of patent right | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20090610 Termination date: 20120309 |