第２７卷第３期２００６年３月
通信学报
Ｊｏｕｍａｌ
ｏｎ
、，０１．２７Ｎｏ．３
Ｃｏｍｍｕｌｌｉｃａｄｏｎｓ
Ｍ眦ｈ２００６
大规模网络管理中的任务分解与调度
刘波，罗军舟，李伟
（东南大学计算机科学与工程系，江苏南京２１００９６）
摘要：集中式的管理模式和简单的基于移动ａｇｅｎｔ的网络管理方法都已不能满足大型网络管理的需要，为此，
在给出基于多ａｇｅｎｔ的网络管理框架的基础上，提出了一种基于任务依赖关系的任务分解算法，把网络管理任务分解为具有不同优先级的子任务，处于同一优先层次的子任务可以并行执行，根据子任务的优先级产生结合网络管理特点的调度策略，理论分析和实验表明：在大规模网络管理中采用任务分解技术能够提高时间效率和减轻网络负载。
关键词：网络管理；多ａｇｅｎｔ；任务分解；任务调度；控制依赖；数据依赖中图分类号：ＴＰ３９３．０７
文献标识码：Ａ
文章编号：１０００．４３６ｘ（２００６）０３．００６４．０９
ＴａｓｋｄｅｃｏｍｐｏｓｉｔｉｏｎａｎｄｓｃｈｅｄｕＨｎｇｉｎｌａｒｇｅ－ｓｃａｌｅｎｅｔｗｏｒｋ
ＬＩＵＢｏ，ＬＵＯＪｕｎ—ｚｈｏｕ，ＬＩ
ｍａ朐ｇｅｍｅｎｔ
Ｗ文
（Ｄ印釉ｅｎｔ
Ａｂｓｔｒａｃｔ：Ｗｉｔｈ
ｎｏｒ
ｏｆｃｏｍｐｕｔｅｒ
Ｓｃｉ锄ｃｅ柚ｄ
Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｏｕｔｌｌｅａｓｔ
ｕｎｉｖｅｒｓｉ吼Ｎ删ｉｎｇ２１００９６，Ｃｈｉｎａ）
Ｉａｒｇｅ—ｓｃａｌｅｎｅｔｗｏｒｋｍａｎａｇｅｍｅｍｂｅｃｏＩＩｌｉｎｇｍｏｒｅｃｏｍｐｌｉｃａｔｅｄ，ｎｅｉｍｅｒｃｅｎ廿ａｌｉｚｅｄｎｅｔｗｏｒｋｍａｎａｇｅｍｅｎｔ
ｇｅｎ甜ｃ
ａｇｃｎｔ＿ｂａｓｅｄｎｅｔｗｏｒｋ
ｏｎ
ｍａｎａｇｅｍｅｎｔｃｏｕｌｄｓａｔｉｓ匆ｔＩｌｅｉｎｃｒｅａｓｉｎｇｄｅｍ粕ｄｓ．Ａ（ｈ∞ｅ－￡ｉｅｒｎｅｔｗｏｒｋｍａｎａｇｅｍｅｎｔ
行ａｍｅｗｏｒｋｂａｓｅｄ
ａ
ｍｕｌｔｉ—ａｇｅｍｗａＳｐｍｖｉｄｅｄ，ｗｌｌｉｃｈｇａｖｅｍｕｌｔｉ—ａｇｅｎｔｍｅｃｏｌｌａｂｏｍｔｉｏｎｅｎＶｉｍｎｍｅｎｔ．Ｉｎｔｌｌｉｓ
ｆ№ｅｗｏｒｋ，
ｔａｓｋ
ｄｅｃｏｍｐｏｓｉｔｉｏｎａｌｇｏｒｉｔｌｌｍｂａｓｅｄｏｎｔａｓｋｄｅｐｅｎｄｅｎｃｅｒｅｌａｔｉｏｎｓｌｌｉｐｗａｓ
ｐｍｐｏｓｅｄ，ａｃｃ删ｎｇｗｈｉｃｈｓｃｈｅｄｕｌｉｎｇｍｅｔｌｌｏｄ
ｓａｖｅ
ｗａｓ
ｐｍｄｕｃｅｄｆｏｒｍｕｌｔｉ—ａｇｅｎｔｃｏｎｓｉｄｅｒｉｎｇｔｈｅｃｈａｒａｃｔｅＩｉｓｔｉｃｏｆｎｅｔｗｏｒｋｍ柚ａｇｅｍｅｎｔｆｕｎｃｔｉｏｎ．Ｔｈｅｔｈｅｏｒｅｔｉｃ柚ａｌｙｓｉｓａＩｌｄ
ｎｅｔｗｏｒｋ
ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｒｅｖｅａｌｍａｔｕｓｉｎｇｔａｓｋｄｅｃｏｍｐｏｓｉｎｏｎｍｅｔｔｌｏｄｃ柚ｄｅｃｒｅａｓｅｔａｓｋｓｅｘｅｃｕｔｉｏｎｔｉＩｎｅａｎｄ
ｂ锄ｄｗｉｄｔｌｌ
ｉｎｌａｒｇｅ－ｓｃａｌｅｎｅｔｗｏｒｋｍ柚ａｇｅｍｅｎｔ．
Ｋｅｙｗｏｒｄｓ：ｎｅｔｗｏｒｋＩｎａｎａｇｅｍｅｎｔ；ｍｌｌｌｔｉ—ａｇｅｎｔ；ｔａｓｋｄｅｃｏｍｐｏｓｉｔｉｏｎ；ｔａｓｋｓｃｈｅｄｕｌｉｎｇ；ｃｏｎ廿ｏｌ
ｄｅｐ蚰ｄｅｎｃｅ；ｄａｔａ出删ｄｅｎｃｅ－
１
引言
随着计算机网络的应用规模迅速增长，网络复
或者不频繁访问的有限的信息管理，例如监控路由器的状态，涉及小部分的网络参数的管理。然而，对于大型网络的高级管理，
基于ＳＮＭＰ的网络管
杂性和异构性的特点日益突出，使得网络管理问题上升到战略性地位。在传统的集中式网络管理中，管理工作站通过ＳＮＭＰ协议收集被管设备中的管理数据，基于ＳＮＭＰ的网络管理使管理者可在一个地方实现对整个网络的灵活管理，适合于小型网络
理方式不再适用【ｌ】，首先，网络管理对管理工作站的依赖容易使其成为瓶颈。其次，传统的网络管理在强调了网络成员之间必须遵循的标准之外，较少
考虑各网络成员的自身特点，在外界环境发生变化
时，不能对网络成员之间的关系自动做出适当的调
收稿日期：２００４—１０—０８；修回日期：２００６．０１．１４
基金项目：国家自然科学基金资助项目（９０２０４００９）；高等学校博士学科点专项科研基金课题（２００３０２８６０１４）
ＦｏｕｎｄａＵ蚰Ｉｔｅ麟：ｎｅ
ｔｏｒａｌ
Ｎａｔｉｏｎａｌ
ＮａｍｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（９０２０４００９）；ＣｈｉｎａＳｐｅｃｉａｌｉｚｅｄＲｃｓｅａｒｃｈＦｕｎｄｆｏｒｔｈｅＤｏｃ－
Ｐｒｏｇｒ锄ｏｆＨｉｇｈｅｒＥｄｕｃａｔｉｏｎ（２００３０２８６０１４）
万方数据
第３期刘波等：大规模网络管理中的任务分解与调度
整和响应。第三，网络成员缺乏自组织、自适应的
能力，不能很好地协同工作以处理日益复杂的网络管理事务。而智能ａｇｅｎｔ的自治性和移动性等特性
恰能解决目前网络管理中存在的问题。Ｂｕｃｈａｎａｎ【２Ｊ总结了在网络管理中使用ａｇｅｎｔ的优点：节省网络带宽，增加扩展的灵活性，解决网络连接的间断性
和不可靠性。
目前，研究者们提出了多种基于ａｇｅｎｔ的分
布式网络管理方法【２４】，也逐渐深入研究如何利用
智能ａｇｅｎｔ的特性实现分布式的网络管理【５’６】，但
是却很少对ａｇｅｎｔ的应用模式进行研究，大规模网络管理任务往往需要分派多个ａｇｅｎｔ去完成，
如何合理划分和分配任务给不同功能的ａｇｅｎｔ呢？
任务的分解与调度问题在相关领域已有很多
的探索，特别是在并行计算领域，从对串行程序的并行划分【『刀到对程序切片【８】的研究，逐步深入，但
是对于大型网络管理中多ａｇｅｎｔ任务，如果采用程
序级的划分方法，那么会产生为数众多的子代码，这会使创建、分配ａｇｅｎｔ和ａｇｅｎｔ之间的通信变得非
常烦杂，即使对划分后的子代码再进行组合以增加粒度，也会破坏网络管理子功能的完整性和划分的
准确性，不利于ａｇｅｎｔ发挥智能管理的特性。其它
的划分方法有均匀划分技术、方根划分技术、对数
划分技术和功能划分技术等，这些方法对于数据并行机制是有效的，而对于数据不规则的任务，例如
网络管理任务，就需要设计出适合其任务特点的功
能分解方法。Ｓｉｎ曲和ＰａＩｌｄｅ【ｗ提出了两种ａｇｅｎｔ迁
移策略，一种是ａｇｅｎｔ迁移时携带它未来路线中节点所需要的全部代码，以减少迁移次数；一种是只携带路线中下一个节点所需要的数据，以减少ａｇｅｎｔ
携带数据量，这两种方法各有其适应的情况，采用
任何一种方法都不能解决大规模的任务处理。ｚｈｕａＩｌ一１０Ｊ运用图论分别以最小迁移次数（ＭＮＭ）
和最小数据传输（ＮＤＴ）为优化指标对单个ａｇｅｎｔ
系统中的ａｇｅｎｔ路线进行了静态和动态规划，但其
只考虑系统中只有一个ａｇｅｎｔ的情况，而没有考虑多个ａｇｅｎｔ的情况。针对上述问题，本文将从适合
ａｇｅｎｔ并行执行的角度出发，通过对网络管理任务
关系进行分析，设计适合复杂的大规模网络管理
任务特点的任务分解算法，在分解任务的基础上设计ａｇｅｎｔ分组调度策略，由多个ａｇｅｎｔ协作完成网络管理任务。
万
方数据２基于多ａｇｅｎｔ的网络管理框架
为了满足网络管理需求，提出了一种基于多
ａｇｅｎｔ的网络管理框架（如图１所示），包括三层结
构：数据库层；ａｇｅｎｔ管理层；被管对象层。数据库
层包括服务单元库和ａｇｅｎｔ信息库，服务单元是进行任务分解的最小粒度单元；ａｇｅｎｔ管理层包括网络管理任务定义模块、网络管理任务分解模块、ａｇｅｎｔ任务调度模块、通信模块及ａｇｅｎｔ管理模块；被管对象层包括支持ＳＮＭＰ的网络设备和其它类型的
被管网络对象。
图ｌ基于多ａｇｃｎｔ的网络管理框架
首先，网络管理任务定义功能以Ｗ曲方式提供给用户，用户可以根据网络拓扑图来选择希望
管理的域，也可以指定需要管理的ＩＰ组。ＯＳＩ定义的五个管理功能域中，每个功能域都包含了许
多具体的功能实现，由于在这些功能中存在着不
少相同或相近的功能，因此，系统中定义了以下功能：ＭＩＢ管理、对象管理、状态管理、条件关
系管理、阈值检查、告警报告、事件报告、日志
管理、安全警告、安全审计跟踪、计费管理、工
作负载监视、测试管理等。这些功能及其子功能
以列表的形式提供给用户，用户可以选择需要的
管理功能，可以对同一对象进行多种功能的管理，
也可以同时对多个对象实现多种管理功能。系统
中提供的功能可能对应服务单元库中的一个单元
或多个单元。网络管理任务定义模块收到用户的
提交以后，根据用户定义的功能的步骤和这些功能的内在关系形成任务流程图，网络管理任务定义模块中的形式化处理子模块会根据服务单元库中的服务单元与用户定义的功能的对应关系对任 