当前位置：文档之家 › Routing Algorithms on the Bus-Based Hypercube Network

Routing Algorithms on the Bus-Based Hypercube Network

  • 格式：pdf
  • 大小：804.39 KB
  • 文档页数：14

Routing Algorithms on the Bus-BasedHypercube NetworkLee-Juan Fan,Chang-Biau Yang,and Shyue-Horng ShiauAbstract —In this paper,we study the properties of the bus-based hypercube,denoted as U ðn;b Þ,which is a kind of multiple-busnetworks (MBN).U ðn;b Þconsists of 2n processors and 2b buses,where 0 b n À1,and each processor is connected to either d b þ22eor d b þ12e buses.We show that the diameter of U ðn;b Þis d b þ12e if b !2.We also present an algorithm to select the best neighbor processor via which we can obtain one shortest routing path.In U ðn;b Þ,we show that if there exist some faults,the fault diameterDF ðn;b;f Þ b þ1,where f is the sum of bus faults and processor faults and 0 f d b À32e .Furthermore,we also show that the bus-fault diameter DB ðn;b;f Þ b b 2c þ3,where 0 f d b À12e and f is the number of bus faults.These results improve significantly the previous result that DB ðn;b;f Þ b þ2f þ1,where f is the number of bus faults.Index Terms —Multiple-bus network,hypercube,routing algorithm,diameter,fault tolerance.æ1I NTRODUCTIONONEof the most important components of a parallel processing system is the interconnection network.The method of connecting processors is also an important consideration for design and performance of the system.Various interconnection networks have been proposed and studied.Notable examples include the crossbar switch and multiple bus systems,multistage networks,and point-to-point (direct)connection schemes.In this paper,we consider a kind of interconnection networks called the multiple-bus network (MBN)[6],[7],[8],[12],[15],[17],[19],[22],[23],[32],[33],[34].The MBN is an extension of the single bus network.An MBN consists of a set of processors and a set of buses.Any pair of processors can communicate via the buses which they both are connected to,and only one message may be transmitted on a bus during a time step.MBNs have several advantages over point-to-point networks.Some of them are listed as follows:.In a point-to-point network,a communication link is connected to a pair of processors.In an MBN,a cluster of processors share a single communication bus,therefore it can be used more efficiently..The number of buses is independent of the numberof processors.Hence,the network designer can make a trade off between the performance of the architecture and the physical resource..MBNs allow easy broadcasts and readily extend tolarger systems.One of the disadvantages of MBNs is that it is difficult to implement buses with a large number of connections.Asthe number of connections to a bus increases,the system will operate slowly.Some overlapping connectivity net-works were proposed to solve the problem,and bandwidth formulas for these networks were derived by using probabilistic analysis methods [33],[34].These kind of networks allows each processor to access a group of memory modules.The simulation results of these networks show that the bandwidth of them is superior to conven-tional MBNs.But,additional switches are required in the overlapping connectivity network.Vaidyanathan and Padmanabhan proposed a bus-based hypercube network,which can perform uniform [1],[26]hypercube algorithms optimally [32].The bus-based hyper-cube network U ðn;b Þconsists of 2n processors and 2b buses,where 0 b n À1.U ðn;b Þcan run any step of a uniform n -dimensional hypercube algorithm optimally in 2n À1Àb steps.The number of buses connected to a processor is either d b þ22e or d b þ12e .In this paper,we shall concentrate our attention to the investigation of properties of U ðn;b Þ.Many other MBNs have been proposed.Ali and Vaidyanathan presented the exact lower bounds on running ASCEND/DECEND and FAN-IN algorithms on synchro-nous MBNs [1].Dighe et al.proposed a class of MBNs called bus-connected ring trees and bus-based trees [7],[8].Multiple buses have also been used in some synchronous reconfigurable systems [24],[25],[29],[31].Some modified network topologies have been proposed to enhance com-munication performance [2],[9],[10],[12],[13],[30].Ishikawa proposed a modified hypercube with multiple buses which used a bypass routing method to reduce the diameter to two [14].Lee et al.[19]proposed the time division multiplexed hypercube (TDM-cube)and the time/wave-length division multiplexed mesh (TWDM-mesh).The TDM-cube (N )implements the binary hypercube interconnection among N nodes in log 2N time slots.The TWDM (n 2)has a small network delay along with much higher network throughput than the Bus-Mesh.Louri et al.[22],[23]proposed a hybrid network,called the spanning multichannel linked hypercube (SMLH),whose features include the possibility of a constant diameter and a constant degree network.And,the network is also scalable and fault-tolerant.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.16,NO.4,APRIL 2005335.L.-J.Fan is with the Department of Applied Mathematics,National Sun Yat-sen University,No.61,Wendong 5th St.,Guishan Shiang,Taoyuan County,Taiwan 333.E-mail:mxlcfan@.. C.-B.Yang and S.-H.Shiau are with the Department of Computer Science and Engineering,National Sun Yat-sen University,Kaohsiung,Taiwan 804.E-mail:{cbyang shiaush}@.tw.Manuscript received 20Aug.2003;revised 25Mar.2004;accepted 7July 2004;published online 23Feb.2005.For information on obtaining reprints of this article,please send e-mail to:tpds@,and reference IEEECS Log Number TPDS-0142-0803.1045-9219/05/$20.00ß2005IEEEPublished by the IEEE Computer SocietySerrano and Parhami proposed an optimal architecture with separable ROW/COLUMN buses for mesh-connected parallel computers [28].In this architecture,semigroup and prefix computations can be performed in optimal time complexity.Cheung and Lau presented an iterative walk-and-ride technique for solving routing with locality problems on meshes [5].An efficient routing algorithm is a key to the perfor-mance of multiprocessor systems.Although there are many results on MBNs,the study of routing problems on U ðn;b Þhave not been proposed.Some good properties on U ðn;b Þwere presented by Vaidyanathan and Padmanabhan [32].Based on the properties,in this paper,we obtain more properties on U ðn;b Þwith which messages can be trans-mitted efficiently.We propose an algorithm to select the best neighbor processor with which we can obtain one shortest routing path.And,we show that the diameter of U ðn;n À1Þis d n 2e .The result can be extended to U ðn;b Þ,where 0 b n À1.If b !2,its diameter is d b þ12e .Fault tolerance is also very important in multiprocessor systems.Fault diameter is one of the important measure-ments of fault tolerance.In this paper,we show that if there exist some faults in U ðn;b Þ,the fault diameter DF ðn;b;f Þ b þ1,where f is the sum of bus faults and processor faultsand 0 f d b À3e .Furthermore,we also show that the bus-fault diameter DB ðn;b;f Þ b b 2c þ3,where 0 f d b À12e andf is the number of bus faults.Our results on bus-fault diameter improve significantly the previous result [32]that DB ðn;b;f Þ b þ2f þ1,where f is the number of bus faults.The rest of this paper is organized as follows:In Section 2,we shall review the construction of the network.In Section 3,we shall give the terms and notations we shall use in this paper.In Section 4and Section 5,the distance properties between two processors will be investigated.We show thatthe diameter of U ðn;b Þ,b !2,without faults is d b þ12e .Accordingly,we design the shortest path routing algorithm for the network,which has never been designed before.In Section 6,we shall present some fault tolerant properties of this network.By finding disjoint paths,we obtain the diameters with some bus faults and with some bus and/or processor faults.Finally,the conclusion will be given in Section 7.2C ONSTRUCTION OF THE B US -B ASED H YPERCUBE N ETWORKIn this section,we shall describe how to construct U ðn;b Þ[32].U ðn;b Þconsists of 2n processors and 2b buses,where 0 b n À1.The fan-out of each processor,the number ofconnections to buses,is either d b þ22e or d b þ12e .A highprocessor has fan-out d b þ22e and a low processor has fan-out d b þ12e .Note that one low processor must not have more connections than one high processor.The state of processor is either high or low.The construction of U ðn;b Þis similar to that of the hypercube.In U ðn;b Þ,each processor has a unique identifier between 0and 2n À1,and each bus also has a unique identifier between 0and 2b À1.U ðn;b Þcan be defined by the following recursive ways:1.The initial structures,U ð1;0Þand U ð1;0Þ,are shown in Fig.1.In the figure,L and H are used to denote a low processor and a high processor,respectively.U ð1;0Þis a dual of U ð1;0Þ.In U ð1;0Þor U ð1;0Þ,the only one bus is called the host bus of these two processors,because the processors are connected to the bus first.2.The construction of U ðn þ1;b þ1Þcan be obtained bycombining U ðn;b Þand U ðn;b Þ.Assume i and j ,0 i;j 2n À1,are a low and a high processors in U ðn;b Þ,respectively.Then,i and j are high and low in U ðn;b Þ,respectively.A connection is added from a low processor i of U ðn;b Þto the host bus d of the high processor i of U ðn;b Þ.Here,the bus d is called a guest bus of i of U ðn;b Þ.And,similarly,a connection is added from a low processor j of U ðn;b Þto the host bus c of the high processor j of U ðn;b Þ,and the bus c is a guest bus of j of U ðn;b Þ.Finally,since a low processor must not have more connections than a high proces-sor,all low processors are changed to high processors,and high processors are changed to low processors.Processor i of U ðn;b Þis still identified as i of U ðn þ1;b þ1Þ,and processor i of U ðn;b Þis identified as i þ2n of U ðn þ1;b þ1Þ.Bus k of U ðn;b Þis still identified as k in U ðn þ1;b þ1Þ,and bus k of U ðn;b Þis identified as k þ2b of U ðn þ1;b þ1Þ.3.To obtain U ðn þ1;b Þ,two U ðn;b Þs are combined,butthe buses are not doubled.The buses in the two U ðn;b Þs are overlapped.Since all processors are not added any extra connections,all low processors are still low processors,high processors are still high processors.Processor i of the first U ðn;b Þis still identified as i of U ðn þ1;b Þ,and processor i of the second U ðn;b Þis identified as i þ2n of U ðn þ1;b Þ.Bus k of the first U ðn;b Þand the second U ðn;b Þis the same one and is identified as k of U ðn þ1;b Þ.As examples,the constructions of U ð2;1Þ,U ð3;1Þ,and U ð3;2Þare shown in Figs.2,3,and 4,respectively.In U ð3;2Þ,the buses connected to processor 100are 00and 10.Bus 10is the host bus of processor 100since bus 10is the bus connected to processor 100first among all ter,Theorem 4will give an easy way to identify the host bus of a processor.Constructing a U ðn;b Þcould be done in any order from two choices.The first method is to double both the number of processors and the number of buses,which is called the fully doubling method .The second method is doubling only the number of the processors,which is called the partially doubling method .Starting from U ð1;0Þ,to construct U ðn;b Þ,there are many permutations to apply the fully doubling method b times,and the partially doubling method n Àb À1times.Different orders of the two methods in construction of U ðn;b Þ336IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.16,NO.4,APRIL2005Fig.1.Initial structures of U .(a)U ð1;0Þ.(b)U ð1:0Þ.would produce different architectures.In this paper,we assume that U ðn;b Þis constructed by applying fully doubling first and then partially doubling.Note that the structure U ðn;b Þis unique if b ¼n À1,because only fully doubling is repeatedly applied.The network U ðn;b Þallows the network designer to choose different values of b due to the cost consideration,thus he can make a trade off between the performance of U ðn;b Þand physical resources [32].As we know,such a trade off is not possible for a point-to-point interconnection network.For example,an n -dimensional hypercube gener-ally must have 2n processors and n 2n À1links.The following theorem gives some properties of U ðn;b Þand U ðn;b Þ.Theorem 1[32].For all 0 b n À1,1.U ðn;b Þcan run any step of a uniform hypercube algorithm optimally.2.Each bus is connected by ðb þ2Þ2n Àb À1processors.3.Processor i ,0 i 2n À1,is a high (low)processor of U ðn;b Þif and only if processor i is a low (high)processor of U ðn;b Þ.4.Each bus j of U ðn;b Þor U ðn;b Þis connected to at least two processors i 1and i 2such that 0 i 1 2n À1À1and 2n À1 i 2 2n À1.Vaidyanathan and Padmanabhan also showed that U ðn;b Þhas a low diameter and is highly resilient to bus faults [32].The bus-fault diameter DB ðn;b;f Þdenotes the diameter of U ðn;b Þwith any f bus faults.Theorem 2[32].For all n >b !0,for all 0 f d b À1e ,DB ðn;b;f Þ b þ2f þ1.3N OTATIONSWe first give some notations used in this paper in the following:.Bin ði;n Þ:n binary bits for representing i ,where 0 i 2n À1:The rightmost and leftmost bits of Bin ði;n Þare counted as bits 0and n À1,respectively.FANET AL.:ROUTING ALGORITHMS ON THE BUS-BASED HYPERCUBE NETWORK 337Fig.2.Construction of U ð2;1Þ.(a)Combining U ð1;0Þand U ð1;0Þ.(b)Adding connections (dashed lines)in low processors in U ð1;0Þand U ð1;0Þ.Then,change the state fromlow to high and the state from high to low.Fig.3.The construction of U ð3;1Þ.U ð3;1Þconsists of two U ð2;1Þs,and the buses are shared to each other.Fig.4.The bus-based hypercube U ð3;2Þ..ZeroðiÞ:number of bit positions(including leading zero bits)in Binði;nÞhaving value0..OneðiÞ:number of bit positions in Binði;nÞhaving value1..EvenðiÞ:number of even bit positions,excluding bit0, in Binði;nÞhaving value1..OddðiÞ:number of odd bit positions in Binði;nÞhaving value1..BðiÞ:the set of buses connected to processor i..b0ðiÞ, b0ðiÞ, b sðiÞ, b s;tðiÞ:Suppose i¼ði nÀ1,i nÀ2;ÁÁÁ,i1, i0Þ.Then,b0ðiÞ¼ b0ðiÞ¼ði nÀ1,i nÀ2,ÁÁÁ,i1ÞandbsðiÞ¼ði nÀ1,ÁÁÁ,i s,ÁÁÁ,i1Þ,1s nÀ1,where i sdenotes the inverse of i s. b s;tðiÞ¼ b sð b tðiÞÞ¼ði nÀ1,ÁÁÁ,i s,ÁÁÁ,i t,ÁÁÁ,i1Þorði nÀ1,ÁÁÁ,i t,ÁÁÁ,i s,ÁÁÁ,i1Þ,s¼t,and1s;t nÀ1..Hði;jÞ:the distance from processor i to processor j, which is the number of hops included in the shortestpath from i to j..R ij:the bit-wise exclusive-or operation on the binary representations of i and j,i.e.,R ij¼Binði;nÞL Binðj;nÞ¼ðr nÀ1;r nÀ2;ÁÁÁ;r0Þ.The operation indi-cates the different bit positions between i and j..HighðiÞ:a function.HighðiÞ¼1if and only if processor i is high,and HighðiÞ¼0if and only ifprocessor i is low.Uðn;bÞconsists of2n processors and2b buses,0bnÀ1,constructed with the method described in the previous section.Some notations for describing the properties of Uðn;bÞare given as follows:.Dðn;bÞ:the diameter of Uðn;bÞ..DBðn;b;fÞ:the bus-fault diameter of Uðn;bÞwith at most f bus faults and no processor faults..DFðn;b;fÞ:the fault diameter of Uðn;bÞ,where f is the sum of bus faults and processor faults.4D ISTANCE P ROPERTIES OF Uðn;bÞW HERE b¼nÀ1We shall present some distance properties of Uðn;bÞ,with which we can route messages efficiently.We discuss the simple case that b¼nÀ1in this section.The properties of Uðn;bÞwhen b<nÀ1can be easily extended and will be discussed in the next section.The proofs of Theorems3and4can be found in the work of Kamath[16](Lemma1and Lemma4)and our work[11] (Lemma3.1and Lemma3.2).Therefore,the proofs are omitted here.Theorem3.In Uðn;nÀ1Þ,ZeroðiÞis even iff HighðiÞ¼1,and ZeroðjÞis odd iff HighðjÞ¼0.For example,in Uð3;2Þ(see Fig.4),processor100is high and ZeroðiÞ¼2.Theorem4.In Uðn;nÀ1Þ,processor i¼ði nÀ1;i nÀ2;ÁÁÁ;i0Þis connected to the set BðiÞof buses1.b0ðiÞ¼ði nÀ1;i nÀ2;ÁÁÁ;i1Þ,which is the host bus ofprocessor i,and2. b sðiÞ¼ði nÀ1;i nÀ2;ÁÁÁ;i s;ÁÁÁ;i1Þ,whereðnÀsÞis oddif HighðiÞ¼1,andðnÀsÞis even if HighðiÞ¼0.In Theorem4,BðiÞ¼f b0ðiÞg[f b sðiÞj nÀs is odd if i is high;nÀs is even if i is low g:In the above,b0ðiÞis the host bus of i,and b sðiÞis one guest bus.For example,in Uð3;2Þ(see Fig.4),processor100is high, and it is connected to the host bus10and the guest bus00. In Uð2;1Þ(see Fig.2),processor00is high,and it is connected to the host bus0and the guest bus1.As another example,in Uð7;6Þ,processor i¼ð1111111Þis high,and processor j¼ð1000001Þis low.Then,BðiÞ¼f111111g[f011111;110111;111101g¼f b0ðiÞg[f b6ðiÞ; b4ðiÞ; b2ðiÞg andBðjÞ¼f100000g[f110000;100100;100001g¼f b0ðjÞg[f b5ðjÞ; b3ðjÞ; b1ðjÞg:Note that b0ðiÞ¼ð111111Þand b0ðjÞ¼ð100000Þare the host buses of processors i and j,respectively,the different bit positions of b6ðiÞ, b4ðiÞ,and b2ðiÞto b0ðiÞare2,4,and6, respectively.And,the different bit positions of b5ðjÞ, b3ðjÞ, and b1ðjÞto b0ðjÞare1,3,and5,respectively.Thus,no matter the state of the processor is high or low,the different bit positions at its guest buses jump every two bits.If two processors have the same states,the jumps will be at the same positions,otherwise the jumps will not be at the same positions.By observation,we find some regular relations between the two bus sets of two processors.For example, in Uð7;6Þ,consider two high processors i¼ð1111111Þand j¼ð1101110Þ.Then,BðiÞ¼f111111g[f011111;110111;111101g¼f b0ðiÞg[f b6ðiÞ; b4ðiÞ; b2ðiÞg andBðjÞ¼f110111g[f010111;111111;110101g¼f b0ðjÞg[f b6ðjÞ; b4ðjÞ; b2ðjÞg:We have BðiÞ\BðjÞ¼f111111;110111g,R ij¼ð0010001Þ, OneðR ijÞ¼2,and r4¼r0¼1.r4¼1indicates that position 4is an important position.After jumping at positions2,4, and6on the host bus of processor j,we can get the guest buses of processor j,f010111;111111;110101g.As we can see, b4ðjÞ¼b0ðiÞ.Similarly,b0ðiÞ¼ð111111Þcan be jumped at position4and transferred to b4ðiÞ¼ð110111Þ¼b0ðjÞ.We extend the observation to Theorem5.Theorem5.In Uðn;nÀ1Þ,let B denote the set of buses to which both processors i¼ði nÀ1,i nÀ2,ÁÁÁ,i0Þand j¼ðj nÀ1,j nÀ2,ÁÁÁ,j0Þare connected,i.e.,B¼BðiÞ\BðjÞ.Each of the following is true:1.Hði;jÞ¼1and HighðiÞ¼HighðjÞ¼1iff OneðR ijÞ¼2,r s¼r t¼1,where s>t,andðnÀsÞis odd,ðnÀtÞisodd or t¼0,and B¼f b sðiÞg[f b tðiÞg.2.Hði;jÞ¼1and HighðiÞ¼HighðjÞ¼0iff OneðR ijÞ¼2,r s¼r t¼1,where s>t,andðnÀsÞis even,ðnÀtÞiseven or t¼0,and B¼f b sðiÞg[f b tðiÞg.3.Hði;jÞ¼1and HighðiÞ¼1and HighðjÞ¼0iff oneof the following two subcases is true:338IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.16,NO.4,APRIL2005a.One ðR ij Þ¼1and r s ¼1,where 0 s n À1,and B ¼f bs ði Þif ðn Às Þis odd,or b 0ði Þif ðn Às Þis even or s ¼0g .b.One ðR ij Þ¼3and r 0¼r s ¼r t ¼1,where n Àsis odd and n Àt is even,and B ¼f bs ði Þg .Proof.If One ðR ij Þ!4,by Theorem 4,i and j cannot be connected to a common bus,i.e.,H ði;j Þ¼1.Hence,1 One ðR ij Þ 3.We first prove the only if part of case (1).Suppose that H ði;j Þ¼1and High ði Þ¼High ðj Þ¼1.By Theorem 3,if processors i and j have the same state,One ðR ij Þis even.Hence,One ðR ij Þ¼2.Assume r s ¼r t ¼1,and s >t !0.By Theorem 4,B ði Þ¼f b 0ði Þg [f bx ði ÞÞj n Àx is odd g .If t ¼0,then j ¼ði n À1;i n À2;ÁÁÁ;i s ;ÁÁÁ;i 1;i 0Þ.First,assumen Às is even,then B ðj Þ¼f bs ði Þg [f b y;z ði Þj one of y and z is s ,one of n Ày and n Àz is odd,and the other is even g .Then,B ¼B ði Þ\B ðj Þ¼;,i.e.,H ði;j Þ¼1.Thus,n Àsmust be odd.Then,B ðj Þ¼f bs ði Þg [f b p;s ði Þj n Àp and n Às are both odd g .Since n Àp and n Às are both odd,we can jump position p .One of the jumps should punch at positions .f bp;s ði Þj n Àp and n Às are both odd g becomes f bp;s ði Þ¼ði n À1;i n À2;ÁÁÁ; {s ;ÁÁÁ;i 1Þ¼ði n À1;i n À2;ÁÁÁ;i s ;ÁÁÁ;i 1Þ¼b 0ði Þg :If position p does not punch at position s ,it becomes f by;z ði Þj n Ày and n Àz are both odd,one of y and z is s g .Summarizing the previous inferences,we haveB ðj Þ¼f bs ði Þg [f b 0ði Þg [f b y;z ði Þj n Ày and n Àz are both odd ;one of y and z is s g :f b 0ði Þg in B ðj Þmatches f b 0ði Þg in B ði Þ.Since n Às is odd,f bs ði Þg in B ðj Þshould be matched to one of f b x ði Þj n Àx is odd g in B ði Þ.Thus,B ¼B ði Þ\B ðj Þ¼f bs ði Þ,b 0ði Þg ,where n Às is odd.If t >0,j ¼ði n À1;ÁÁÁ;i s ;ÁÁÁ;i t ;ÁÁÁ;i 1;i 0Þ.By the similar argument,we obtain that both n Às and n Àt must be odd.We haveB ðj Þ¼f bs;t ði Þg [f b s ði Þg [f b t ði Þg [f bx;y;z ði Þj all n Àx;n Ày;and n Àz are odd ;and two of x;y and z are s and t g :Thus,B ¼B ði Þ\B ðj Þ¼f bs ði Þ; b t ði Þg ,where both n Às and n Àt are odd.Next,we prove the if part of case (1).Suppose that One ðR ij Þ¼2,r s ¼r t ¼1,where s >t ,and ðn Às Þis odd,ðn Àt Þis odd or t ¼0.Since One ðR ij Þ¼2,by Theorem 3,Zero ði Þand Zero ðj Þare either both even or both odd.It means that High ði Þ¼High ðj Þ¼1or High ði Þ¼High ðj Þ¼0.Since i is connected to bus bs ði Þ,where n Às is odd,by Theorem 4,i is a high processor.Thus High ði Þ¼High ðj Þ¼1.The proof of case (1)of the theorem is completed.The proofs of case (2)and case (3)are quite similar tothat of case (1)and,so,are omitted.t u We use some examples to illustrate Theorem 5.In U ð5;4Þ,suppose processors i ¼ð00001Þ,j ¼ð10101Þ,and k ¼ð00100Þ.By Theorem 3,processors i ,j ,and k are all high processors.By Theorem 4,B ði Þ¼f 0000;1000;0010g ,B ðj Þ¼f 1010;0010;1000g and B ðk Þ¼f 0010;1010;0000g .By case (1)of Theorem 5,processors j and k are neighbors of processor i ,the buses f 0010;1000g are connected by both processors i and j ,and the buses f 0010;0000g are connected by both processors i and k .The different bits between i and j or i and k are two and at even positions,as shown in Table 1.Note that one of the two different bits between processors i and k is at bit 0.As an example of case (3)of Theorem 5,let u ¼ð11001Þ,v ¼ð00000Þ,and w ¼ð10001Þ.Processor u is high,and processors v and w are low.B ðu Þ¼{1100,0100,1110},B ðv Þ¼f 0000;0100;0001g and B ðw Þ¼{1000,1100,1001}.The bus 0100is connected by both processors u and v .The bus 1100is connected by both processors u and w .The different bit positions are also shown in Table 1.Theorem 5can be used to guide the routing from a source processor to a destination processor.If either case (1)or case (2)of Theorem 5is applied in one routing step,we call it is a 2-bit routing step .If case (3)a and case (3)b of Theorem 5are applied in one routing step,we call them are 1-bit and 3-bit routing steps ,respectively.Table 1also explains some examples of 2-bit,3-bit,and 1-bit routing steps.The first column at the table is an example for even 2-bit routing step .The changes of one odd 2-bit routing step are at two odd positions.We have some observations from Theorem 5.Suppose we perform routing from processor i to processor j and R ij ¼Bin ði;n ÞLBin ðj;n Þ¼ðr n À1;r n À2;ÁÁÁ;r 0Þ.If r 0¼0,applying only one 3-bit routing step could not make the distance shorter than changing one 2-bit if changing one 2-bit is possible.For example,in U ð5;4Þ,suppose the source is the low processor i ¼ð00000Þand the destination is the high processor j ¼ð01110Þ.By Theorem 5,one of the shortest paths from i to j is f 00000;01010;01110g .If we first apply a 3-bit routing step,then the path from i to j may be f 00000;01101;01100;01110g ,which is longer than the distance between i and j .Therefore,to send messages from source i to destination j via one shortest path,we must select a best neighbor processor from all candidates that connect to processor i .Of course,not all candidates can be selected to route messages to the destination via one shortest path.On the other hand,there are many permutations and combinations of changing different bits,but it is important to know which is the best next intermediate processor to route messages to the destination.Before presenting how to select one best neighbor processor of the source processor,we give the distance between two processors.FAN ET AL.:ROUTING ALGORITHMS ON THE BUS-BASED HYPERCUBENETWORK 339TABLE 1The Different Bits between Two Neighboring Processors。

合集下载

电子商务 中英对照E-commerce Chapter2

电子商务 中英对照E-commerce Chapter2


20世纪80年代末独立 的学术和研究网络合 并成了互联网
1979年杜克大学和 北卡罗来纳大学的 一群学生和程序员 创建了用户新闻网
20世纪90年代起 互联网成为全球 性的共享资源
1991年美国科学基金 会进一步放宽对互联 网商业活动的限制， 并对互联网实施私有 化
1996年发展到 30多万台计算 机
20世纪60年代初，美 国防部担心核武器攻 击计算机设施，意欲 创建全球性网络
1969年美国防部将加州 大学洛杉矶分校与圣巴 巴拉分校、斯坦福大学 国际研究所、犹他大学 的四台计算机连接起来
1972年 电子邮件诞 生
互 联 网 的 起 源 与 发 展
1989年美科学基金会 允许两家商业性的电 子邮件服务商与互联 网建立有限的连接
world wide web
Computer network 计算机网络 Technology allowing people to connect computers to each other Internet 因特网 A large system of interconnected computer (internet) spanning the globe(地球) World Wide Web 万维网
p58
2. Packet-switched networks
- Works well for(适用于) telephone calls
Circuit switching 线路交换
- Does not work as well for:
Sending data across large WAN, interconnected network Circuit-switched network problem 线路交换网络的问题 • Connected circuit failure - Causes interrupted connection, data loss 中断连接，数据丢失
Evolutionary Computing Algorithms

Evolutionary Computing Algorithms

Evolutionary Computing AlgorithmsEvolutionary computing algorithms, also known as evolutionary algorithms, are computational techniques inspired by biological evolution. These algorithms are used to solve optimization problems by mimicking the process of natural selection and genetic variation. Evolutionary computing algorithms have gained popularity in various fields such as engineering, finance, and computer science due to their ability to find high-quality solutions to complex problems.One of the key features of evolutionary computing algorithms is their ability to handle optimization problems with high-dimensional search spaces. Traditional optimization techniques may struggle in these situations due to the large number of variables involved. Evolutionary algorithms, on the other hand, are well-suited for tackling such problems as they can explore a large search space efficiently and converge to optimal solutions.There are several types of evolutionary computing algorithms, with genetic algorithms being the most well-known. Genetic algorithms work by maintaining a population of candidate solutions and applying genetic operators such as mutation, crossover, and selection to evolve better solutions over generations. These algorithms are particularly effective for problems with non-linear constraints and discontinuous objective functions.Another popular variant of evolutionary computing algorithms is evolutionary strategies, which are based on self-adaptation and evolution of strategy parameters. These algorithms have been successfully applied to optimization problems in the fields of robotics, engineering design, and game playing. Evolutionary strategies are known for their ability to handle noisy and dynamic optimization problems, where traditional optimization methods may struggle to find optimal solutions.Particle swarm optimization (PSO) is another type of evolutionary computing algorithm that is inspired by the social behavior of birds flocking and fish schooling. In PSO, a population of particles moves around a search space to find optimal solutionsthrough interaction and communication with other particles. PSO has been widely used in function optimization, image processing, and data clustering due to its simplicity and effectiveness.Evolutionary computing algorithms have been applied to a wide range of real-world problems, including design optimization, machine learning, and data mining. These algorithms have been successfully used to solve problems such as vehicle routing, job scheduling, and neural network training. Their ability to adapt and evolve in complex environments makes them a powerful tool for solving challenging optimization problems.In conclusion, evolutionary computing algorithms are versatile optimization techniques that have proven to be effective in solving complex problems across various domains. With their ability to explore large search spaces, handle high-dimensional problems, and adapt to changing environments, evolutionary algorithms have become an indispensable tool for researchers and practitioners seeking optimal solutions to challenging optimization problems.。

browse4

browse4

A Multi-path Energy Hole Avoidance Routing Algorithm for WSN Based on GA/,8 $Q )HQJ 0$ 0LQJ &+(1 =KL *DQJ *8, :HL +XD (College of Information Science and Engineering , Central South University ,ChangSha 410083 China) Abstract:The multi-path routing strategy can delicately balance the energy consumption of wireless sensor networks to avoid the energy hole problem and prolong the lifetime of networks. In order to delicately plan a number of next-hop routing paths of each node, this paper proposes a multi-path energy hole avoidance routing algorithm that exploits the genetic algorithm (GA) to select numbers of next-hop nodes and distribute appropriate proportions of data to be transmitted. To obtain the global optimal solution, the algorithm redefines the code, operations and rules of searching optimal solution for the genetic algorithm. The algorithm can not only be applicable to flat networks, but also it would be applicable to hierarchical networks if improved in some sort. A significant advantage of the algorithm is that it can provide global optimal routing approach for energy balance without assuming the topology structure of network. Compared with the single-path routing algorithms, the multi-path routing algorithm in this paper increases 3.2% in the performance of optimization. Finally, this paper confirms the accuracy of the algorithm through theoretical analysis and proves the effectiveness by a number of simulated experiments.Key Words: Wireless sensor network; Multi-path routing; Energy balance; Genetic algorithm; Energy hole1 IntroductionIn previous period of research, this problem was summarized as a routing optimization problem of selecting appropriate next-hop node for each node. In fact, the problem belongs to a single-path routing problem[1]. In this paper, a Multi-path Energy H ole Avoidance Routing (MPEH AR) algorithm for WSN based on GA is proposed. Firstly, the algorithm converts the routing problem into the problem of selecting a number of optimal next-hops for each node and distributing appropriate data for each next-hop for the purpose of achieving an overall optimal system. It is clear that the single-path routing is a special case of multi-path routing (that is, select only one next-hop to transmit all data). Then, the genetic algorithm[2] (GA) that is capable of approaching multi-objective optimization is exploited to solve the problems. The genetic algorithm is global optimal bionic algorithm. Under the condition of no special requirements for the problems to be solved,the algorithm searches to approach the optimal solution. Through redefinition of code, operations and rules of searching optimal solution for the genetic algorithm (GA), the multi-path energy hole avoidance routing problem is well solved.2 Energy Hole Avoidance Algorithm2.1 Description of the AlgorithmAn overall general flow is shown in Algorithm 1, in which detailed operations of each step can be found in the following corresponding sections.Algorithm 1Multi-path Energy Hole Avoidance Routing Algorithm Based on GA (MPEHAR)Input: network topology, initial population, the number of evolutionary generation TOutput: Pareto solution P*, routing schemeBegin(1)i=1;// count the number of evolutionary generations(2)use Algorithm 2 to generate GA_Population GP1// use the Algorithm 2 to generate initial population(3)DO (4)use Algorithm 3 to calculate the fitness value f(GP i ) ofthe individual // calculate the fitness value of the individual (5)P*=MostOptimal (GP i ); // select the chromosome with the optimal fitness value as// the optimal solution (6)GS i+1ĸ OptimalSelect(GP i );// Selection operation. It is shown in Section 2.5. (7)GT i ĸ MateSelec(GP i );// Crossover operation. It is shown in Section 2.6.(8)GS i+1ĸ Evolve(GT i )// Mutation operation. It is shown in Section 2.7. (9)i=i+1; (10)While (i>T) or (termination criterion is met). (11)Ouput P*;End 2.2 Representation of Chromosome Code In this paper, d d _9_× ×k integers are used for expressing a chromosome which represents a routing scheme for wireless sensor network. In theexpression, V is a set of nodes in the wireless sensor network, and |V | represents the number of nodes. k shows that each node can select k next-hop nodesfor multi-path routing. At the same time, the proportions of data to be transmitted for the next-hops also need to be expressed. Because there are |V | nodes, while each node can be expressed by 2×k digits number, a total d =|V |×2×k digits number is needed for expressing a routing scheme. The representation of chromosome coding is shown inFigure 3. Figure 1 Representation of code for multi-path routing In Figure 1, i j n represents the j -th next-hop node selected by the node i V from Next (v i ), and i jϑaccounts for the proportion of data to be transmittedfrom the node i V to the j -th next-hop node. If ij n =0,it shows that node i V does not select j-th next-hop node. If ij n =-1, it shows that the j-th next-hop node selected by the node i V is sink node.2.3 Generation of Initial Chromosome PopulationThe algorithm of generating initial chromosomepopulation is shown as follows. Algorithm 2. generate_GA_Population GP .Input: the scale of chromosome population N.Output: GP .Begin(1) GP ĕ(2) while (|GP |<N )(3) for(i =1;i <=|V| L^for (j =1; M . M ^ ij n 5DQGRP Next (v i )// Select a node as the next-hop node from Next (v i ).; ; ∪ij ni j Q 5DQGRP ¦−=11j h i h Q,I M . ij Q¦−=11j h i h Q; ; ∪ij Q`(4) PS ĕPS Ĥ;`(5) Goto (2)(6) Output GSEnd2.4 Fitness FunctionFitness function is a standard of measuring the strength and weakness of individuals in a population. The ultimate goal of the Energy-H ole Avoidance Routing optimization for WSN is to improve the network's overall lifetime, so the fitness is the values of the network's overall lifetime. The algorithm of computing fitness is shown as follows.Algorithm 3. Max_life_GA_Population GP.Input: routing scheme of networkOutput: max_life.Begin(1) max_lifeĕ∞(2) while have node ni.indegree=0 in WSN(3) ni.life= E elec/(r1*a+r2*b)// a is the received data, while b is the sent data.//r1 and r2 are respectively the energy consumption of//receiving and sending per unit data.if (ni.life<Max_life)Max_life= ni.life;for each Nj in ni’s next hop// If Nj is one of the next-hop nodes of ni.Nj.a= Nj.a+ni.b*Qj// Nj.a is the received data, and Qj is the proportion of data// transmitted by ni through Nj.Nj.b= Nj.a+Nj.data//Transmitted data is the received data plus the data generated // from its own.Nj.idegree--;end for}(4) Output Max_lifeEnd2.5 Selection StrategyIn this paper, the algorithm main exploits the selection strategy based on the ratio of fitness value. Firstly, calculate the fitness value of each individual according to the fitness function proposed above, and use the strategy of selecting the best to keep the individuals of highest fitness value in the population of filial generation.Secondly, according to the formula (3), calculate the individual's fitness value and take the value as the individual selection probability. In the formula (1), )(i If is the i-th individual’s fitness value, and N is the scale of population.¦==NiikkIfIfIp1)()()(Finally, the Roullete Wheel Selecltion Strategy[13] is used for selecting the individual: Divide a disk into N parts according to the proportion of selection probability. The central angle of the i-th sector is)(2i Ipπ.2.6 Crossover OperationsThe basic process of Crossover operation is as follows:(1).According to the Roulette Wheel Selection algorithm, select two individuals1I and2I of parent generation randomly from the population.(2). Select λ•||V different nodes’ IDs randomly from Random (1…|V|) in the proportion ofλˈand interchange the corresponding gene positions of all next-hop nodes selected by these λ•n nodes. At the same time, the corresponding gene positions of distributive proportions of data are interchanged too.2.7 Mutation and Evolution OperationsIn this paper, the mutation algorithm of selecting the gene position of next-hop node is designed as follows:(1). According to the mutation probability p, select the individuals needed for mutation operation randomly. The mutation operation for each individual is shown as follows.(2). Select γ different numbers {1ID…γID} randomly from Random (1…|V|). For the nodes whoseIDs fall into the set {1ID…γID}, select k next-hop nodes randomly from Next (vi) as the new genepositions to replace the original gene positions. As to the gene coding for the distributive proportion of data, this paper exploits the evolution strategy and selects the optimal fitness value in the father individual p I and offspring individual s I todetermine the direction of evolution. The specific operation is shown as follows:(1). According to the mutation probability p ,select the individuals needed for mutation operation randomly. The mutation operation for each individual is shown as follows. (2). Select γ different numbers {1ID …γID }randomly from Random (1…|V|). For the nodes whose IDs fall into the set {1ID …γID }, conduct the evolution the following evolution operations.(3). Assuming b I )(P I f !)(s I f "p I s IIRU K LQ ^1ID ĂγID ` s I h Q 1 h Q 2Ăhk Q b I h Q 1 h Q 2Ăhk Q 3 Experimental Results we analyze the lifetime of network in terms of 3 different routing algorithms. 1).Direct routing algorithm (or Direct algorithm)[3]: Each node transmits data directly to the sink node. 2).Relay routing algorithm (or Relay algorithm): Each node relays data to the sink node at the minimum level of energy [4]. 3). a Multi-path Energy Hole Avoidance Routing (MPEHAR) algorithm in this paper. In the simulated experiment, assuming there are 2 routing paths (k =2) at most. Figure 2 shows that 200 nodes are deployed within the scope of deployment area. As seen from it, according to MPEHAR algorithm, the death times of all nodes in the network are almost the same. From the time when the first node dies till the time when the last node dies, 59 data packets are usually transmitted. This shows that inthe homogeneous energy environment, MPEH ARalgorithm can distribute the energy expenses evenly toeach node. So the lifetime of entire network is prolonged. H owever, in terms of Relay algorithm, nodes close to the sink node will work out energy first. While Direct algorithm is just the opposite.T DM A f ra m e s The number of dead nodesFigure 2 Death time of nodes (200 nodes are homogeneous)4 Conclusion This paper propose a of GA algorithm to avoidenergy hole of WSN, meeting the requirements ofpractical applications. Finally, experimental results andtheoretical analysis confirm the effectiveness of the algorithms proposed in this paper in spite of the maindeficiency of lack of centre optimization device.Reference :[1] X B Hou , D Tipper , J Kabara1 Label based multi-path routing (LMR)in wireless sensor networks [C]1 The Int ÿl Symp on Advanced Radio Technologies ( ISART) , Boulder , CO , 2004[2] W R H einzelman , A Chandrakasan , H Balakrishnan1 Energy efficient communication protocol wireless microsensor networks[C]1 IEEE Hawaii Int ÿl Conf on System Sciences , Maui ,Hawaii , 2000 [3] A Manjeshwar , D P Agrawal1 TEEN : A routing protocol forenhanced efficiency in wireless sensor networks [C]1 IEEE Int ÿlParallel and Distributed Processing Symposium , SanFrancisco ,USA , 2001 [4] A Manjeshwar , D P Agrawal1 APTEEN : A hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks [C]1 IEEE Int ÿl Parallel and Distributed ProcessingSymposium , Fort Lauderdale , Florida , 2002。

Problem6

Problem6

Problem61.The routing function attempts to find the least-cost route through the network,with cost basedon number of hops,expected delay,or other metrics.2.Adaptive routing algorithms typically rely on the exchange of information about trafficconditions among nodes.3.Routing decisions are made on the basis of some performance criterion.Two keycharacteristics of the decision are the time and place that the decision is made.4.Decision time is determined by whether the routing decision is made on a packet orvirtual circuit basis.When the internal operation of the network is datagram,a routing decision is made individually for each packet.For internal virtual circuit operation,a routing decision is made at the time the virtual circuit is established.5.The term decision place refers to which node or nodes in the network are responsible forthe routing decision.For distributed routing,in which each node has the responsibility of selecting an output link for routing packets as they arrive.For centralized routing,the decision is made by some designated node,such as a network control center.6.The routing algorithm is that part of the network layer software responsible fordeciding which output line an incoming packet should be transmitted on.7.A router has two processes inside it.One of them handles each packet as it arrives,looking upthe outgoing line to use for it in the routing tables.This process is forwarding.The other process is responsible for filling in and updating the routing tables.That is where the routing algorithm comes into play.8.Nonadaptive algorithms do not base their routing decisions on measurements or estimatesof the current traffic and topology.Instead,the choice of the route to use is computed in advance,off-line,and downloaded to the routers when the network is booted.This procedure is sometimes called static routing.9.Adaptive algorithms,change their routing decisions to reflect changes in thetopology,and usually the traffic as well.10.Flooding is the technique requires no network information whatsoever and works asfollows.A packet is sent by a source node to every one of its neighbors.At each node,an incoming packet is retransmitted on all outgoing links except for the link on which it arrived.11.Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest pathproblem for a graph with non-negative edge path costs,producing a shortest path tree.The shortest path algorithm is widely used in network routing protocols,most notably IS-IS and OSPF(Open Shortest Path First).12.The Bellman-Ford algorithm can be stated as follows:Find the shortest paths from agiven source node subject to the constraint that the paths contain at most one link,then find the shortest paths with a constraint of paths of at most two links,and so on.13.The routers in an internet are responsible for receiving and forwarding packets through theinterconnected set of networks.Each router makes routing decision based on knowledge of the topology and traffic/delay conditions of the internet.14.Routing information is Information about the topology and delays of the internet.is The algorithm used to make a routing decision for a particular datagram,based on current routing information.15.An AS is a set of routers and networks managed by a single organization.An AS consistsof a group of routers exchanging information via a common routing protocol.16.Interior router protocol(IRP)is used to pass routing information between routerswithin an AS.Exterior router protocol(ERP)is used to pass routing information between routers in different Ass.17.Within an autonomous system,IGP software uses a routing metric to choose an optimalpath each destination.EGP software finds a path each destination,but cannot find an optimal path because it cannot compare routing metrics from multiple autonomous systems. 18.Internet routing protocols employ one of three approaches to gathering and using routinginformation:distance-vector routing,link-state routing,and path-vector routing.19.Distance-vector routing requires that each node(router or host that implements therouting protocol)exchange information with its neighboring nodes.Two nodes are said to be neighbors if they are both directly connected to the same network.The relatively simple Routing Information Protocol(RIP)uses this approach uses this approach.20.Path-vector routing,is to dispense with routing metrics and simply provide informationabout which networks can be reached by a given router and the ASs that must be crossed to get there.21.Link-state routing is designed to overcome the drawbacks of distance-vectorrouting.When a router is initialized,it determines the link cost on each of its network interfaces.The router then advertises this set of link costs to all other routers in the internet topology,not just neighboring routers.Because the router has a representation of the entire network,it does not use a distributed version of a routing algorithm,as is done in distance-vector routing.Rather,the router can use any routing algorithm to determine the shortest paths.In practice,Dijkstra’s algorithm is used.The Open Shortest Path First(OSPF)protocol is an example of a routing protocol that uses link-state routing.22.The Border Gateway Protocol(BGP)was developed for use in conjunction withinternets that employ the TCP/IP suite,although the concepts are applicable to any internet.BGP has become the preferred exterior router protocol for the Internet.。