《李幼平任勇am教学文案》由会员分享,可在线阅读,更多相关《李幼平任勇am教学文案(56页珍藏版)》请在金锄头文库上搜索。
1、双结构互联网,中国工程物理研究院 李幼平 2005.11.21 于中国复杂系统论坛,万维网是复杂网络,67.8万个网站(存储节点)与1亿网民(生理节点)互动,形成万维网的复杂性 无尺度的物理基础:存储器一次写入,可多次读出,读出次数没有上限 小世界的生理基础:人类注意力资源的有限性 某种意义上,因为存在“小世界”,所以出现“无尺度”;同一复杂事物的两个简单的侧面 网站度值幂律分布,网民度值随机分布,创意的由来,摩尔定律下无限的物理比特,与DNA制约下人类只能接受有限的生理(熵)比特,产生了冲突,揭示了矛盾 揭示TCP/IP结构“用户规模不能自由增长”,揭示广播结构“内容规模不能自由增长” 在T
2、CP/IP互联结构基础上,增添一种“播存结构”,让更多人群自由选择更有用的内容 科学发展观要求人类与大自然和谐相处,我们希望网络与人类的文化活动和谐相处 用PPT表达创意的由来,CN Internet 一亿网民,CN Web 66万网站,CN Core 1000网站,CN Core 1000网站,CN NGI 5亿网民,主结构 Primary,次结构 Secondary,和谐整合电信与广播,当前的互联网,物理层是构建在电信网双向连接之上的,无缘于单向的广播网 次结构:广播分流最活跃的热门网页,使“平均距离”大幅降低 克服“数字鸿沟,实现“数字文化村村有” 主结构将缓解拥堵,显得格外通畅 为实现
3、“网页主动寻找网民”的“语义网”理想提供物理基础,向理论家请教,2005年10月9日,我向汪秉宏老师请教: 1,请用复杂网络理论描述中国现有的万维网(尽量采用科学院中国互联网信息中心CNNIC的最新统计数据)。 2,请沿用用CNNIC“前一百”的提法,在现有67万提供内容的网站中,分离出“前100”、“前500”、“前1000”、“前3330”“前xx”,形成“主流网站” 3,假设,有人想出办法(如播存结构),有能力把“前xx”主流网站的访问距离(或跳数)统统变为1,试问:中国万维网的的理论图象会发生什么变化?,有中心?无中心?,在拓扑图中,互联网是一片“云”;从技术上看,各节点完全平等,无主
4、次,无中心,无结构 可是统计结果却是有主次,有中心,有结构 为什么?网络专家忽略了人文活动对网络的反作用,古语云:“不知卢山真面目,只缘身在此山中” 其实,CNNIC早就有察觉,只是没有抽象化、形式化,提高到数学高度去认识,CNNIC的“前一百个”,2005.7.11CNNIC王恩海告诉我:网站拥有字节量”比例悬殊,前一百家(占网站总数万分之1.7)占字节总数13.3% 网站总数595550个,前一百家平均拥有34.3万个网页,而所有网站平均只有523.7个网页,相差近千倍 就在一百家内部也拥有极大差异 怎么说是没有中心呢?,网站链接情况(摘自2003年中国互联网络信息资源数量调查报告 ),没
5、有连接:占41% 连接1-5家:占29.9% 连接5-10家:占15.0% 连接11-20家:占7.4% 连接21-50家:占3.6% 连接51家以上:占2.7% 绝大多数网站,连接数很少(97%网站少于50家),只有极少数网站才拥有极大的连接数,用Scale-free定律 拟合,请参见马卫东的报告:中国互联网资源幂次分布分析 结论:,中国互联网也是无尺度网络,中国互联网也是无尺度网络,幂数为2.124 67.8万个网站,被访问量差异极大,社会地位(Google称为rank)差异极大 前100个,前500个,前1000个,或前2000个是中心,是主流 互联网的流量,相当大的比例,源于这些网站,
6、启示:打造国家级群体,无尺度现象启示我们打造国家级文化群体的灵感 只要把几千个甚至几百网站整合起来,就可以形成满足社会上绝大多数人群需求的“普适化”pervasive主流媒体 如果技术上想出办法,能让主流群体普及下去,普及到每个村庄或家庭,就可以在普及数字文化的进程中实现历史性跨跃。,互联网有一个“芯”(core)?,Web是Internet的中心,网上流动着网页,多是源自Web 1000-3000个网站又是Web的芯(core),多数流动着的网页源于这些网站 这些网站也是互联网的“芯” 这个“芯”就是主流文化群体,也许,其中包括300种报纸、500种网站、800种期刊、上千种课程 这个“芯”
7、引发我们创新的灵感,营造Scale-free的共享环境,次结构,播存结构,用户数目可以无上限自由增长,不受带宽限制 对应物理上的辐射,点对面,各向同性 不是对流,不是点对点,不是公路,是阳光 我国人口众多,我们致力于寻找一种网民数目可以无上限增长的共享结构 参见中国工程科学两篇文章:信息阳光-无冲突共享结构(2000.2,p24-27);共享信息的第二类网络(2002.8,p8-11),营造Small-world的服务环境,连接主结构与次结构的透明计算 透明:按需取用,不必顾及具体来历 融合两种信道:大量文件下载,依靠单向广播与存储的次结构;双向互联,仍然依靠主结构 复杂问题简单解决:最常用的
8、,放在最近! 服务将是低成本的,主动的,惠及全民的 分布全国、无所不在的普适计算:Pervasive computing,主次结构和谐整合,什么是下一代互联网(NGI)?主流派的回答是:IPV6加光纤到户 我们补充说:应该添上播存结构 电信业接入的主结构,同广播业接入的次结构,通过透明计算和谐整合 请理论家计算平均距离、度值分布、集聚系数会有什么变化 恭请诸位评论“双结构互联网”的前景,谢 谢 ! 李幼平 liyp ,双结构互联网定量分析,Internet与WWW的业务与大尺度模型 模型定参与算法描述 部分仿真结果 任 勇,清华大学电子工程系复杂工程系统实验室(CESL),国家自然科学基金-网
9、络与信息安全重大研究计划项目: (1)复杂互联网络整体动力学理论、方法与应用(No.90204004) (2)互联网络业务源模型与业务量预测(No.90304005),Internet的物理模型,AS,AS,AS,Public exchange point,Private peering,Hosts/Endsystems,Access networks,Stub Domain,Transit Domains,Border routers,Routers,Internet 中大约存在近 15,000个自治域 (ASes),Internet与WWW的业务与大尺度模型,WWW的物理拓扑在Intern
10、et中的位置,Internet与WWW的业务与大尺度模型,WWW的逻辑拓扑,Internet与WWW的业务与大尺度模型,Internet核心及接入,World-Wide Web,AS,Routers,用户,URL: ,URL: ,URL: ,Internet业务种类,弹性数据业务 实时业务:VoN Voice and Video over the Net 流媒体业务 承载其它网络接入业务 无线网实时业务接入 无线网数据业务接入 IPv6所能解决的本质问题只有一个:地址空间 Internet作为生长型网络,永远无法满足带宽需求,WWW业务特征,文件传输为主 Poisson到达:负指数分布 文件长
11、度服从重拖尾分布:Bounded Pareto 网站文件服务时间也服从重尾的BP分布 重尾业务:持续时间具有重拖尾分布特性的业务 重拖尾业务实质:被长流调制的慢变的布朗运动 用户满意度指标:阻塞概率、平均响应时间 播存结构理论分析:有限忍耐度的排队系统分析,文件长度服从BP分布(Bounded Pareto) k = 1.22 kbyte, p = 1 Mbyte, = 1.1 文件长度均值6.56 kbyte,方差7.17108 大于100kbyte的文件占0.72% 大文件产生的数据量占27.1% 文件长度服从负指数分布,则大于100kbyte的文件占2.4/千万,数据量占3.7/百万。
12、M/ G/ 1、 M/ G/ 、 M/ M / c可解析。 M/ G/ c无法直接分析,没有分析工具!,重尾业务特点及其处理方法,大方差(LV):15分钟,却占50% 突发性分解:-分解,Agg+ 3Aggstd 临界速率, Elephant and Mice ! Dragon flies and Tortoises!,仿真网络系统模型,N1 核心网,N2 接入网,N3 WWW网,N4 用户子网,N3 依实测WWW 数据复现,N1-N3 依实测Internet 数据复现,N4 实现事件触发,模型定参与算法描述,1、用Transit-stub模型生成Internet物理拓扑N1-N2; 2、依照
13、CNNIC数据,用可调幂指数BA模型生成WWW逻辑拓扑N3; 3、依照CNNIC数据(用户兴趣统计),生成业务触发节点N4; 4、改变了WWW逻辑拓扑,改变了N4节点访问TOP n% N3节点的路由,实现核心节点播存。 5、统计Internet流量变化:负载等网参变化与性能评估。 N1=N2=5000, N3=2500, N4=2000,N1 核心网,N2 接入网,N3 WWW网,N4 用户子网,核心内容 用于播存,Internet节点度分布 WWW节点度分布 网络流量分布对比 网络平均流量变化 骨干链路流量变化 节点负载分布对比 平均节点负载变化 骨干节点负载变化 与其它共享技术对比,Int
14、ernet的节点度分布*,*数据来源:软件学报,2005,16(5):847-856,结果,WWW的节点度分布*,结果,*数据来源:CNNIC,2003年中国互联网络信息资源数量调查报告,播存前后Internet网络流量分布对比,结果,播存的核心节点数量:10%,Edge weight distribution when top 10% nodes are to be selected for broadcasting.,Blue: before Red : after,减少了重载链路的数量!,播存前后Internet网络流量分布对比,结果,Core = 10%,Core = 20%,Core
15、 = 30%,Core = 40%,Core = 50%,Core = 60%,网络平均流量 vs. 播存网站数量,结果,骨干链路流量 vs. 播存网站数量,结果,播存的核心节点数量:10%,播存前后Internet节点负载分布对比,结果,Blue: before Red : after,减少了重载节点的数量!,Node weight distribution when top 10% nodes are to be selected for broadcasting.,播存前后Internet节点负载分布对比,结果,Core = 10%,Core = 20%,Core = 30%,Core
16、= 40%,Core = 50%,Core = 60%,网络平均节点负载 vs. 播存网站数量,结果,骨干节点负载 vs. 播存网站数量,结果,播存网与其它信息共享技术比较,与组播技术比较 规模不受用户数和组数的限制 大规模组播无法实现 与DTN技术比较 时效性更好 与信息网格技术组合,建立基于播存结构的文化网格,信息网格技术示意图,仿真分析结论,播存结构显著减少WWW共享信息业务量压力: 用户数量增加 双结构互联网,能够有效降低WWW流量负载即等效带宽成本;随着用户数量的不断增加,降低效果越发明显。 网络规模增加 双结构WWW网,其流量负载即等效带宽成本几乎不随网络规模变化而变化;而单结构WWW网的带宽成本会随网络规模增加而增加。 扩展性与性价比优于现有其它技术(M