学位论文 > 优秀研究生学位论文题录展示

面向广域网的分布式搜索引擎中任务调度技术的研究

作　者: 刘爽
导　师: 李东
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: 分布式搜索引擎网络距离预测 Web划分广域网任务调度负载均衡
分类号: TP391.3
类　型: 硕士论文
年　份: 2009年
下　载: 68次
引　用: 0次
阅　读: 论文下载

内容摘要

由于Web的地域分布式特性以及网络基础条件等方面的限制,随着Web的迅速膨胀,目前的搜索引擎由于其集中式的结构遇到覆盖率和更新率方面的瓶颈。使用广域网下的分布式搜索引擎,可以很好的适应Web信息管理的需求,获得比传统搜索引擎更高的效率。分布式搜索引擎设计中最重要的部分之一是调度系统,它将特定Web页面的抓取任务调度至广域网上效率较优的爬虫,以提高整个搜索引擎的抓取效率。准确并且迅速的调度策略是分布式调度系统研究的关键问题。本文针对分布式搜索引擎的特点,综合考虑分布式结构中调度系统的需求,研究分布式调度中关键技术并设计实现广域网上的分布式搜索引擎调度系统。本文分析了基于随机哈希、基于网站域名后缀及文件类型、基于地理位置、基于IP注册信息等传统Web划分策略的弊端,首次将网络距离预测应用在Web爬虫调度研究中。为了更准确地预测爬虫下载网页的速率,本文提出使用应用层上网络距离测量代替传统的网络层距离测量。之后,根据分布式搜索引擎爬虫加入退出的随机性和不确定性,选用不依赖于固定测量点的距离预测算法计算Web节点网络坐标。接着,在网络时延空间的基础上,研究和设计了划分准确性较高的基于迭代自组织的高质量Web划分算法。针对Web划分结果,研究了一种对广域网上的分布式搜索引擎按划分集合进行调度的算法,兼顾初始任务分配和动态调度时的负载均衡性。最后,将坐标建立、Web划分、调度三部分功能组合起来,设计了一种可靠性高,支持节点动态组织,易于扩展的分布式调度系统体系结构。本文针对应用层网络距离预测、Web划分和负载均衡算法均进行了实验分析。实验说明本文提出的广域网分布式调度系统的Web划分和负载均衡性能都比较理想。

全文目录

摘要  3-4
Abstract  4-9
第1章绪论  9-15
  1.1 课题背景和研究意义  9-10
  1.2 国内外研究现状  10-13
    1.2.1 调度问题的研究动态  10-11
    1.2.2 Web划分的研究动态  11-13
  1.3 本文的主要工作  13-14
    1.3.1 课题研究思路  13
    1.3.2 主要工作  13-14
  1.4 本文的组织结构  14
  1.5 本章小节  14-15
第2章基于应用层测量的网络距离预测算法  15-29
  2.1 网络距离预测方法  15-20
    2.1.1 三角启发式算法  15-16
    2.1.2 经典网络距离预测算法  16-19
    2.1.3 路标结点的选择  19-20
  2.2 网络距离的应用层测量手段  20-22
    2.2.1 应用层网络距离测量操作  20-21
    2.2.2 网络时延的准确性保证  21-22
  2.3 PIC算法  22-26
    2.3.1 PIC算法基本框架  22-23
    2.3.2 爬山法  23-24
    2.3.3 安全测试机制  24-25
    2.3.4 PIC算法的改进  25-26
  2.4 PIC准确性实验  26-28
  2.5 本章小结  28-29
第3章基于网络坐标的Web划分策略  29-54
  3.1 Web划分  29-31
    3.1.1 Web划分定义  29-30
    3.1.2 Web划分单元  30-31
  3.2 随机性Web划分算法  31-32
  3.3 基于网络相对位置的Web划分策略  32-35
  3.4 基于网络坐标的Web划分策略  35-44
    3.4.1 简单聚类算法  35-38
    3.4.2 基于迭代自组织的高质量Web划分  38-44
      3.4.2.1 ISODATA算法  39-40
      3.4.2.2 爬虫不足的划分集合的控制  40-44
  3.5 基于迭代自组织的高质量Web划分策略的性能验证  44-53
    3.5.1 TopK调度算法  45-46
    3.5.2 实验设置  46
    3.5.3 划分结果对比  46-47
    3.5.4 系统性能对比  47-53
      3.5.4.1 吞吐量对比  47-52
      3.5.4.2 时延累计对比  52-53
    3.5.5 实验总结  53
  3.6 本章小结  53-54
第4章分布式任务调度及负载均衡技术  54-63
  4.1 分布式搜索引擎静态任务分配  54-55
  4.2 划分集合内部的负载均衡技术  55-57
    4.2.1 负载指标的选择  55
    4.2.2 平衡目标的确定  55-56
    4.2.3 分布式系统启动动态任务调度策略  56
    4.2.4 分布式系统迁移策略  56-57
    4.2.5 负载均衡算法  57
  4.3 分布式爬虫负载均衡性能试验  57-62
    4.3.1 负载累计曲线对比  58-61
    4.3.2 离散系数对比  61-62
  4.4 本章小结  62-63
第5章分布式搜索引擎调度系统设计  63-76
  5.1 网络坐标计算模块  64-68
    5.1.1 爬虫的坐标计算模块  64-66
    5.1.2 调度系统的坐标计算模块  66-68
  5.2 Web划分模块  68-72
    5.2.1 增量划分单元  70-71
    5.2.2 IAWP划分单元  71
    5.2.3 划分计时器单元  71-72
  5.3 调度模块  72-75
    5.3.1 静态调度单元  73-74
    5.3.2 动态调度单元  74-75
  5.4 本章小结  75-76
结论  76-78
参考文献  78-83
攻读学位期间发表的学术论文  83-85
致谢  85

相似论文

随机路由在无线传感器网络中的研究与应用,TN929.5
高校教务管理网上选课系统优化研究,TP393.09
基于Linux集群系统的负载均衡算法研究及在Webgis中的应用,TP393.05
LTE-A异构网络中的自组网技术研究,TN929.5
基于一种新经济模型的异构网络选择算法,TN929.5
基于QoS的无线Mesh网络路由协议及相关技术的研究,TN929.5
构建分布式系统的关键技术研究与实现,TP338.8
基于S2SH框架的雅砻江虚拟研究中心系统研究与设计,TP311.52
基于负载均衡的混合型应用层组播模型研究,TP393.02
异构网络联合接纳与切换控制技术研究,TN929.5
基于逻辑卷的分级存储系统设计与实现,TP333
虚拟环境中多网络接口卡I/O调度系统的研究,TP334.7
分布式搜索引擎索引安全及缓存策略研究,TP333
RFID数据清洗处理策略与算法,TP391.44
基于分布式实时数据库的事务调度策略研究与改进,TP311.13
分布式内存数据库存储研究,TP311.13
负载均衡调度系统的设计与实现,TP393.02
基于CDN和P2P技术的混合流媒体内容分发机制研究,TN919.8
图像检索的并行计算方法与系统,TP391.3
并行与分布入侵检测技术研究,TP393.08
基于负载均衡的3G视频传输系统的设计与实现,TN919.8