非对称广域覆盖信息共享网络理论与关键技术

1信息共享网络的复杂性研究——理论与关键技术报告人：任勇清华大学电子工程系2010.07.26引子2010第六届全国网络科学论坛大会报告2Contents2网络信息共享的背景网络信息共享难题目前研究工作241几个课题5互联网的复杂性33网络信息获取的主要方式：搜索获取→网站→网络信息分类：−个性化信息：专业性强，面向少数人−共享信息：大量网络用户需要的内容网络业务分类：−个性化信息业务−共享信息业务4我国网民规模、普及率网民网站网页2009-063.38亿306万166亿2009-123.84亿323万366亿2010-064.20亿279万X?（摘自CNNIC报告，以下同）5全球互联网普及率（2009-12）09年12月，28.9%，超过全球25.6%09年06月，25.5%，超过全球23.8%10年06月，31.8%，超过全球平均水平超级大国6城乡差异（2010-06）农村网民：27.4%（11508万人）搜索：76.3%（8780万人）农村网民搜索用户2009-069565万/30%6700万/70%2009-1210681万/27.8%7829万/73.3%2010-0611508万/27.4%8780万/76.3%7网络应用已发生显著变化•信息交换信息共享email点对点一点对多点，多点对多点8典型应用9主流业务量P2P业务是因特网的最大单项流量，白天占35-60%，晚上占50-90%。WWW（HTTP）、P2P等信息共享业务构成互联网的主流业务量。4大类网络应用：网络娱乐、信息获取、交流沟通、商务交易16种网络应用：网络音乐，82.5%网络新闻，78.5%网络搜索，76.3%即时通信，72.4%…………主流业务量：10信息共享业务的特点课题：非对称、广域覆盖的信息共享网络传输特点：相同信息大量冗余传输，带宽浪费；流量、流向：下行上传，即非对称业务；地域特点：按75%普及率：11亿网民：未来5年，网民数7亿规模中西部地区：人口密集、经济落后，需低成本偏远地区：人口稀少，需广域覆盖11Contents11目前研究工作4几个课题5互联网的复杂性3网络信息共享难题2网络信息共享的背景112网络信息共享服务现状信息共享造成冗余传输→带宽的无度浪费（收费不增加）IP网承载共享信息业务，有若干问题难以解决结构性矛盾→制约非对称业务用户规模可扩展性网站信息下载到用户端，要多跳传输→无法保证服务质量Overlay资源搜索与共享下载的拓扑失配→无效传输端到端透明IP传输→安全问题、信任危机现有信息共享应用的服务模式，存在天然的缺欠B/S、P2P、DTN、CDN、M-cast、IPTV、Web2.0（RSS、Blog）在用户规模、带宽有效占用、服务质量三方面，存在结构性缺欠结论：基于IP的端到端的对等式信息交换网络结构，不适于支持巨大量用户以信息共享为主的非对称传输业务。13Contents13目前研究工作4几个课题5网络信息共享的背景1互联网的复杂性3网络信息共享难题214Contents14几个课题5网络信息共享的背景1网络信息共享难题2目前研究工作4互联网的复杂性315当前工作：1.信息共享网络演示验证示范系统——Demo系统完全播存——共产主义过渡时期——初级阶段2.分布式代理节点的数量、位置分布3.P2P成簇算法4.网络失配解决方案——基于匹配度的相变点控制5.网络信息聚合及其在农业价格领域里的应用16161、Demo系统：信息共享网络新结构InternetInternetWebCrawlerOriginalWebPagesInformationAggregationServerLocalServer1LocalServer2AggregatedWebPagesDestinationGateway1AggregatedWebPagesDestinationGateway2LocalServerNLocalServerX本地服务器分布式代理汇聚服务器（1）动态、树状、多身份代理、多通道的兼容服务模式（2）Wide-areaBrodcasting、LocalP2P星级用户17iu用户、资源耦合行为资源节点is资源节点jsjsis应用层网络用户节点iu物理网络层应用层网络与物理网络的双层耦合模型2、代理节点的数量及分布规律51943AB7826A18iu用户、资源耦合行为资源节点is资源节点jsjsis应用层网络用户节点iu物理网络层访问行为引入分布式镜像代理2log1dpk剥离核心资源节点增加资源节点镜像引导数据包改变路由缩短路由路径长度节点处理负载得到均衡传输负载被均衡镜像代理数量：1900.10.20.30.40.50.60.70.80.910100200300400500600700800数据包注入概率节点数据包平均排队长度“对称”访问“非对称”访问代理节点00.10.20.30.40.50.60.70.80.910100020003000400050006000700080009000数据包注入概率数据包平均生存时间“对称”访问“非对称”访问代理节点00.10.20.30.40.50.60.70.80.9100.10.20.30.40.50.60.7数据包注入概率节点丢包比例“对称”访问“非对称”访问代理节点问题：镜像代理怎样分布？202.8448%3.8547%14.766%42.5616%2.6724%23.3005%1.9335%3.0296%5.0369%4.7313%6.056%8.2892%60.106%4.2392%2.0439%1.9304%4.9584%7.6457%5.2956%5.1063%8.1714%50.9224%2.3638%2.988%2.7916%7.1333%15.2276%24.3689%4.5631%23.5922%51.165%1.6505%4.0777%2.4272%7.1845%0.9709%Cluster2:1112users123x104123x10401000200005001000ikwCluster4:679usersCluster9:212usersCluster20:92users(a)(b)(c)(e)(d)MovieTVdramaMusicGameComicVarietyshowsSoftwareMaterialsSportsMovieTVdramaMusicGameComicVarietyshowsSoftwareMaterialsSports1NLikiiikNwwwL3、P2P成簇算法——用户兴趣指纹识别港台综艺节目美剧2100.100.100.10.200.10.2Cluster2Cluster6Cluster13Cluster17PopularityMovieTVdramaMusicGameComicVarietyshowsSoftwareMaterialsSportsTorrent网络分簇——资源条码识别各簇均表现出各类Torrent的相关性大簇内文件流行度较高，且由于大多数兴趣广泛的用户下载使其包含的文件种类多小簇内文件流行度不高，但得到具有特殊兴趣的用户的集中下载资源条码224、P2P网络的拓扑失配peer节点路由器资源节点BAABCOverlay网络物理网络C1233211Peer2李一鹏博士搜索结果远程节点邻居节点路径2路径1Peer23匹配度定义：•匹配度·所需资源的副本总数C·所需资源距离自己最近的节点n·所需资源距离自己最远的节点f·节点i与节点j之间的度量dij：反映节点跳数、延迟，流量1ifijinijifinijififininiijfddddddddddddij，或单资源节点称为节点从节点获取资源的匹配度。240.050.10.150.20.250.30.350.40.450.5012345678x105数据包注入概率路由器节点数据包排队长度0.8950.3680.1050.63200.10.20.30.40.50.60.70.80.910123456789x105数据包注入概率骨干链路传输负载0.8950.3680.1050.6322500.10.20.30.40.50.60.70.80.910123456789x105数据包注入概率骨干链路传输负载0.8950.6320.5260.7890.4210.1580.0530.2630.050.10.150.20.250.30.350.40.450.5012345678x105数据包注入概率路由器节点的数据包排队长度0.8950.6320.5260.7890.4210.1580.0530.263临界点匹配度相变点控制动态镜像资源分布265、基于本体的网络信息聚合及其应用•信息源：网页•爬取：爬虫(含动态网页)•解析：•基于本体的语义标注·全局本体=概念+关系+实例·局部本体-表格：1+1+N方法-文本：条件随机场•生成聚合信息•存储、发布、应用中间件层应用层信息源层•报价单位•产品•价格•报价日期27应用举例：粮食价格分析•数据来源：-中华粮网（）-东北粮食网（）-中国农业信息网（）-中国畜牧网（:8001/html/market/index.html）-中原畜牧网（）-阿里巴巴农业资讯（）•粮食价格分析–稻谷–小麦–玉米–2009.7—2010.7时间序列分析：统计软件(SPSS17.0)•周价格曲线•事件关联分析•区划价格差异•中、长期预测，短期预测•指数平滑法•自回归法•ARIMA模型法•季节分解法•谱图分析法28稻谷•09.12-10.02：春节临近，消费旺季，涨价•10.03-10.04：旱情严重，涨价•10.05：稻谷轮换出库，需求淡季，降价•10.06：水灾，减产，涨价红色：观测值蓝色：拟合值2009.7.152010.7.1029小麦•出现离群值(outlier)：2月、3月、6月中旬原因：原始数据错误、聚合处理错误、突发事件驱动•6月末-7月初：涨价（春季低温、化肥涨价、惜售）•预测：出现误差；短期预测难度大！须深入研究！红色：观测值蓝色：拟合值绿色：预测值真值OutlierOutlierOutlier2010.1.12010.7.1030小麦区划•周期性：7天•预测：误差较小，周期性华东中南华北西北东北西南红色：观测值，蓝色：拟合值，绿色：预测值31小麦区划•3-4月份：西南地区价格明显高！•原因：春季旱情严重。32网络信息聚合的意义•聚合信息服务·热门信息推送·按需求订制·难点：完整、精度、重组•行业领域应用·可靠建模依据·政策制订支持•事件关联分析·短期预测•方法与手段：基于本体的语义理解+时间序列分析33行为层面网络层面流量行为抽象模型SOC相变时空行为网络仿真随机矩阵理论整体模式无线传感网元胞自动机应用层/流量行为应用/物理网络耦合/失配相变用户/资源偏好/社区P2P网络分割加权社交网络共享行为/需求播存网络系统设计分析理解综合设计移动行为物理感知移动互联网物联网分析设计早期近期当前总结1999年以后2009年以后34ContentsAchievement5网络信息共享的背景1网络信息共享难题2互联网的复杂性3几个课题5目前研究工作435