传输文件传输

第24卷第1期山东科技大学学报(自然科学版)Vol.
24No.
12005年3月JournalofShandongUniversityofScienceandTechnology(NaturalScience)Mar.
2005文章编号:1672-3767(2005)01-0089-03基于图论的网络文件并行传输问题分析廉文娟1,范昊1,2,段华1(1.
山东科技大学信息科学与工程学院,山东青岛266510;2.
中国科学院计算技术研究所,北京100080)摘要:根据网络文件分配与调度的特点,用图论的方法对文件并行传输问题进行了详细的分析,并且结合具体的实例提出了优化文件并行传输的调度算法.
关键词:并行传输;完全多边形;图论;调度算法中图分类号:TP393.
01文献标识码:AAnalysisofParallelTransfersofGraphTheoryBasedWebFilesLIANWen-juan1,FANHao1,2,DUANHua1(1.
CollegeofInfoScienceandEng.
,SUST,Qingdao,Shandong266550,China;2.
InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100080,China)Abstract:Thispaperanalyzestheparalleltransferproblemsoffilesindetailwithgraphtheorymethodbasedonthecharacteristicsofdistributionandschedulingofwebfilesandpresentstheschedulingalgorithmofoptimizingfilesparalleltransferscombiningwithpracticalexample.
Keywords:paralleltransfers;completepolygon;graphtheory;schedulingalgorithm网络是一个使用分布资源的基础设施.
为了共享资源,网络环境下的多个计算机可能要频繁的交换数据.
解决共享资源的冲突问题,优化网络数据的并行传输过程,可以有效的减少数据传输的时间,对提高网络的通信性能有重要的意义.
在分布式并行环境中,网络通信问题研究如何把网络上一组通信任务合理的调度,解决共享网络节点的冲突问题,优化网络通信的并行处理过程[1,2].
合理有效的通信调度算法可以减少并行通信完成的时间.
基于图论的方法[2,3]是研究通信任务调度常用的方法,通信主机和通信任务可以用有权图表示,顶点代表处理机,边代表通信关系.
常用的通信调度模型主要是有向无环图(DAG)模式和任务交互图(TIG)模式[4].
DAG模式表示主机通信有一组有先后关系限制的通信任务组成,主要研究通信任务之间的拓扑关系给出合理的调度方案.
但它没有考虑通信的执行时间问题,不能给出通信时间最短的调度方案[5].
TIG模式表示一类没有先后限制,只有相互通信的任务,主要研究如何优化的分配通信任务到具有不同通信开销的链路上,以减少整个通信的执行时间.
虽然解决了通信时间上的优化,但TIG模型需要复杂的建模过程和调度算法.
本文提出的方法建模简单清晰,分析方法可行易于实现,对于简单的网络文件传输问题是一种高效的解决方法.
1问题和文件传输系统实例下面给出一个具体的实例[6],来说明网络环境下文件并行传输所要解决的问题.
例1:节点名v1v2v3v4v5并行能力11213文件名e1e2e3e4e5e6e7起止点v1,v3v1,v2v2,v3v3,v4v3,v5v4,v5v2,v5费时5322643图1文件传输系统实例Fig.
1Anexampleoffiletransfersystem收稿日期:2004-10-03作者简介:廉文娟(1977-),女,山东济宁人,助教,从事计算机图形学、电子商务教学及科研工作.
图1中的两个表格分别给出了计算机网络节点vi(iE1,2……5)并行传输文件的能力(并行传输文件的个数)及传输文件ej(jE1,2……7)的性质:传输起止节点及所需的时间.
要求最佳传输方案,使传输时间最短.
基于图论的算法解决传输方案的思想就是把在传输过程中存在冲突的文件排一个合理的顺序,消解文件传输过程中的冲突,并且使网络总的传输时间最短.
2基于图论的文件传输系统模型定义1:无向图GE(E,V)为文件传输系统的传输关系图,其中(1)VE{ei(ti)}为顶点集,每个顶点代表一个被传输的文件,ei为文件名.
ti为该文件对应的传输时间称为顶点ei的跨度.
(2)EE{}为边集,表示文件ei,ej的传输起止点共享网络节点vk.
定义2:顺序关系图G的每个完全多边形顶点的跨度之和为该完全多边形的跨度.
顺序关系图G的跨度则是其完全多边形中跨度最大的一个.
首先考虑图1中的计算机节点v1,v2,v4,这些节点的并行能力为1,画出该模型的传输关系图,如图3.
图2不完整的传输关系图(不考虑节点v3)Fig.
2Apartoffiletransformationrelationgraph根据定义1,图2中的每个顶点表示一个文件,括号中的数字是该顶点的跨度,表示文件传输所需的时间.
两顶点ei,ej有边vk相关联,表示图1中对应的文件ei,ej在传输中都要使用计算机节点vk,也就是说ei,ej间有顺序关系,必须顺序传输,传输顺序可以是eiej,也可以是ejei,但不能并发传输.
所以顺序关系图中完全多边形中的顶点必须顺序发生.
根据定义2传输关系图的跨度就是可能实现的最短传输时间.
图2的跨度为8.
t(e1)+t(e2)E8,t(e2)+t(e3)+t(e7)E8.
图3完整的顺序关系图Fig.
3Acompletesequencerelationgraph把图1中的节点v3加入到传输关系图2中.
节点v3要传输4个文件,e1,e3,e4,e5把4个文件分两组,同在一组的文件共享节点v3中的一个接口(一个并行能力),另一组共享v3中的另一个接口.
相应的在图2中同为一组的顶点增加关联边v3,不一组的不增加边.
以不增加或少增加顺序关系图的跨度作为文件的分组规则.
若e3,e4为一组,e1,e5为一组,传输关系图的跨度为t(e1)+t(e5)E5+6E11.
若e1,e4为一组,e3,e5为一组,顺序关系图的跨度仍为8.
根据分组规则,围绕节点v3的分组应是{e1,e4},{e3,e5}.
由定义1可以得到例1的完整传输关系图3.
例1中文件e5,e6,e7在传输中要使用节点v5,但v5的并行能力为3,也就是说在整个传输过程中节点v5不会发生冲突.
所以在顺序关系图中可以不考虑节点v5.
根据定义1,图3就是例1完整的传输关系图.
3基于图论的文件传输调度算法传输关系图中有边{}相连的节点表示:文件ei,ej的传输共享节点vk,因此文件ei,ej的传输必须顺序完成.
由定义2可以看出,传输关系图中跨度最大的完全多边形的度是整个网络完成所有的文件传输可能实现的最短时间,为了使整个网络的传输时间最短,应该优先传输关系图中跨度最大的完全多边形的顶点.
图3中跨度最大(8)的完全多边形有三个:{e1,e2},{e2,e3,e7},{e3,e5},同时开始并行传输这三组文件的可能性有{e1,e3},{e1,e5,e7}和{e2,e5}.
本文提出了基于图论的文件传输调度算法可以对传输方案进行分析.
文件传输调度算法:09山东科技大学学报(自然科学版)第24卷(1)选取传输关系图中跨度最大的完全多边形的顶点优先并行传输.
(2)在传输关系图中将开始传输的顶点和与该顶点相关联的边染成红色.
(3)如果存在顶点ex,ex及与ex关联的边全为黑色,将ex与ex关联的边全染成红色.
也就是说文件ex可以开始传输.
(4)查看文件传输的情况,找出最早传输完毕的文件.
将其在传输关系图中对应的顶点及相关联的边删除.
(5)是否所有顶点都已被删除(所有文件都已传输.
)是,算法结束.
否,执行(3).
应用文件传输调度算法分析方案{e1,e3}.
根据算法步骤1和2,图3中{e1,e3}不同属于一个完全多边形,可以并行传输如图4(a).
根据算法步骤3此时顶点e6及与e6相关联的边全为黑色,文件e6也可以优先并行传输,如图4(b).
根据算法步骤4,由图5看出在时间2时e3结束,删除e3及其相关联的边如图4(c).
根据算法步骤3此时文件e5,e7可以并行传输,如图4(d).
由图5,时间4时e6结束,删除e6及其相关联的边如图4(e).
根据步骤3此时没有可以选取的顶点,转步骤(4)寻找传输完毕的文件,根据图5在时间5时e1,e7同时结束,删除e1,e7及其相关联的边,如图4(f).
此时选文件e2,e4并行传输,将其染成红色,根据图5在时间7时e4传输结束,时间8时e2,e5传输结束.
算法结束.
根据文件传输调度算法,由图5看出,选择{e1,e3}为优先并行传输的,整个传输过程耗时为8.
顺序关系图3的跨度也为8,所以{e1,e3}可以产生最佳方案.
最佳方案为如图5所示.
同理可以分析{e2,e5}也可以产生最佳方案.
{e1,e5,e7}不能产生最佳方案.
到此,对例1做了完整的解答,说明如下:(1)在边点着色的顺序关系图中两顶点间无边:对应的文件无共享的节点,可以并行传输.
两顶点间有黑边:对应的文件有共享节点,需要顺序传输.
两顶点间有红边:对应的文件有一方正在传输,占用节点,另一方不能传输.
(2)图5可以在分析过程中逐渐生成,并非事先给出.
e2(3)··e5(6)e4(2)·(f)图4算法分析过程Fig.
4Processofalgorithmanalysis图5调度时间分析Fig.
5Analysisofschedulingtime基于图论的方法分析文件的并行传输问题的步骤如下:建立实际问题的传输关系图;根据传输关系图确定优先传输的文件集合;应用文件传输调度算法找出最佳传输方案.
(下转第111页)19第1期廉文娟等:基于图论的网络文件并行传输问题分析镀件电镀前需经除油、酸洗、机械磨光或滚桶滚光来清洁表面.
使镀件在入槽前达到无油、无锈、无厚的氧化膜和无脏物覆盖.
一般用化学法可达到清洁表面的目的.
应尽可能的采用滚桶滚光法[10],用较低浓度的酸、碱或表面活性剂,借机械摩擦可将钢铁件的油垢和铁锈等除去,并可将零件表面磨光滑.
这些措施能大幅度的减少酸碱废水的排出量.
但仍然会有碱洗和酸洗产生的酸碱废水以及地面清洗废水.
一方面可以利用产生的酸、碱液相互中和达到处理目的;也可以在其他系统中加以利用,例如:用酸性、碱性废水用来调整pH值.
使另加药品中和酸碱废水变为补充措施,可大大降低治理废水的成本.
3结论实践证明用以上所述工艺处理电镀废水,首先可大幅度减少废水的排放量;按系统分别处理电镀废水,简化了处理方法,提高了处理效果;由于回收铬等重金属,有效的防止了污泥对环境造成的二次污染.
所以该方法有近一步研究完善和推广的必要.
参考文献:[1]黄瑞光.
21世纪电镀废水治理的发展趋势[J].
电镀与精饰,2000,(3):1~2.
[2]国家环保总局.
1999年中国环境状况公报[J].
环境保护,2000,(7).
[3]曾祥德.
闭路循环技术的理论与应用[J].
电镀与涂饰,1994,13(3):46~51.
[4]曾祥德.
电镀废水处理技术的综合应用[J].
电镀与精饰,2000,22(1):39~41.
[5]彭昌盛,孟洪,等.
化学法处理电镀废水的工艺流程既药剂选择[J].
水处理技术,2003,29(6):363~365.
[6]汤荣年,康思奇,等.
电镀废水综合治理新工艺研究[J].
五邑大学学报,2002,16(4):39~42.
[7]黄瑞光.
五十年来我国电镀废水治理的回顾[J].
电镀与精饰,2000,22(2):6~8.
[8]华中师范学院,华北师范学院,陕西师范学院编.
分析化学[M].
北京:人民教育出版社,1983.
[9]尹洪.
电镀废水中铬得处理与回收[J].
1998,5(1):24~25.
[10]王小军.
半自动倾斜潜浸式滚镀设备的改进[J].
电镀与精饰,1994,16(4):28~29.
(上接第91页)4结束语本文根据网络中文件传输调度的特点,提出了一种基于图论的文件传输调度算法,通过该算法,可以找出时间上最优的文件传输方案,提高网络通信的性能.
基于图论的方法理论性强,有严格的数学分析方法,本文通过具体的实例分析证明了该算法的正确性.
提出的算法在多媒体通信方面也有较好的参考价值.
参考文献:[1]D.
Angulo,I.
Foster,c.
Liu,etal.
DesignandEvaluationofResourceSelectionFrameworkforGridApplications[A].
ProceedingofIEEEInternationalSymposiumOnHighPerformanceDistributedComputing(HPDC-11)[C].
Edinburgh,Scotland,July2002.
[2]StallingsW.
High-SpeedNetworks:TCP/IPandATMDesignPrinciples[M].
Macmillan,1998.
[3]ChartrandG.
TheTheoryandApplicationsofGraphs,(FourthInternationalConference)[C].
JohnWiley&Sons,1981.
[4]胡凯,张怡,胡建平.
网络计算环境下任务调度问题研究[J].
北京航空航天大学学报,2001.
[5]林闯,杨士强.
多服务器多队列系统调度方案性能分析[J].
电子学报,2002,(5).
[6]AndrewS.
Tanenbaum.
计算机网络(中译本)[M].
北京:清华大学出版社,1998.
111第1期马小隆等:电镀废水处理存在的问题及解决方案