Computer Network Topology Design in Limelight of Pascal Graph Property.pdf

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ! ? ? ? ? ? ? ? ? ? # ?# ? ? ? ? ? ? ? ? Sanjay Kumar Pal1 and Samar Sen Sarma2 1Department of Computer Science all Pascal Graph of higher order are non- planner. Vertex V1 is adjacent to all other vertices in the Pascal Graph. Vertex V1 is adjacent to Vi+1 in the Pascal graph for 1i. PG(n) contains a star tree 1 n. PG(n) contains a Hamiltonian circuit 1,2,3,n-1, n,1. PG(n) contains wn-x (wheel of order n minus an edge). If k=2n +1, n is a positive integer, then Vk is adjacent to all Vi. All Pascal Graph of order 3 are 2-connected. No two even no of vertices of a Pascal Graph are adjacent. There are at least two edge disjoint path of length 2 between any two distinct vertices in PG(n), n3. If Vi is adjacent to Vj , where j is even and |i-j|1, then I is odd and Vi is adjacent to Vj-1. Let det(PM(n) refer to the determinant of the Pascal matrix of order n. Then, det(PM(n) = 0, for all even 4n. Define e(PG(n) to be the number of edges in PG(n), ? 3log) 1()( 2 nnPGc. Det(PM(n) is even for all 3n. 2.4 Pascal Graph Generation Algorithm Step 1: Enter n number of vertices. Step 2: Initialized LTn,0 = 1; Step 3: From the lower left triangle LT(n,n) by adding the number directly above and to the left with the number directly above and to th right to find the new value. If either the number to the right or left is not present, substitute a zero to its place. Step 4: From the upper right triangle UT(n,n) using the same manner. Step 5: Convert the lower left triangle into binary values. Step 6: Convert the upper right triangle into binary values. Step 7: From the final adjacency matrix PM(n,n) of with LT(n,n) and UT(n,n). Step 8: Stop. V1 V2 V3 V4 V5 PM(5) V1 V2 V3 V4 V5 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 33 3. Connotation of Present Work It is better not to predestine any claim before underpinned with adequate reasoning. To bolster this, the basic requirement must be articulated and hence substantiated. Studying different graph with respect to their properties has been a basic research interest for a long time 6. It can be said without any ambiguity that there are certain criteria in any network topology that are given priorities to judge its credentials. Those criteria are, (i) degree of the network, (ii) diameter of the network, (iii) scalability of the network and (iv) reliability of the network 2. There is a tradeoff between degree related to hardware cost and diameter related to transmission time of messages within any Interconnection Network 2. Reliability is the quality to sustain faulty circumstances and scalability is the scope of up-gradation without much alteration. To prove its worth, Pascal; graph have been merged cogently with Hypercube graph to engender simple- (q,n)-graph 2. The destiny of the research is signified keeping this philosophy in mind. 4. Fascinating Characteristic of Pascal Graph In this work a new property of Pascal graph has been characterized that has increased the reliability of the graph without perturbing its degree, diameter as well as scalability as computer network topology. As we mentioned in property (iii) in properties of Pascal graph, vertex v1 of any Pascal graph is adjacent to all other vertices in that graph. It has been shown that if the index start from 0 instead of 1 then it can be proved that vertex v0 in any Pascal graph is adjacent to all other vertices in that graph. Vertex v1 is adjacent to v1+1 in the Pascal graph if 0i2. Extending the property (iii) in the properties of Pascal graph, it can be very well shown that there exist other node vi (0i) having the same property like v1. According to property (iv), this node will never have even number as its index. 4.1 Thought of Present Work If we consider a Pascal graph containing n nodes i.e. PG(n) then by default vi (1i) is adjacent to all other nodes 1. The exploration does not conclude with it. We have found and recommended other node similar to v1 in the PG(n) and termed it as Dependable Node of Pascal Graph (DNP); the special node, other than node v1, of Pascal graph PG(n) with same degree like v1. To satiate our claim and to rationalize the whole thing we have used very simplistic approach. The explanation with some suitable example is given below. Case 1: ()n n log 2= Case 2: ? n n log 2 Case N: ? 12 log += n n To establish the new property, we are supposed to generate the index I of DNP. Here, we provide formulae for each case including the case 3. For Case 1: () 1, 12 1log iwherei n += For Case 2: ? 112 log iwherei n += For Case N: ? 1, 1212 log1log iwhereiandi nn +=+= 4.2 Experimental Result The source code has been written in the C programming language to generate the different order Pascal matrix. The formulas were put into test for a meticulous checking of the existence of Dependable Node Pascal Graph (DNP) in different Pascal matrices generated by the program. Some instances of execution of the program are given in the table 1, for a better comprehension of the conjecture. Each instances given in the table 1, the Pascal matrix has been generated and printed along with the degree of the particular ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 34 node and its index. When case N occurs, the Pascal graph is at at a precise level of reliability. Unlike other cases, it has got three (one more than case 1 and case 2) nodes. Table 1: PG(n) Conjecture satisfied i DNP Degree 8 Case 1 5 V5 7 9 Case N 5, 9 V5 , V9 8 10 Case 1 9 V9 9 11 Case 2 9 V9 10 14 Case 1 9 V9 13 15 Case 2 9 V9 14 16 Case N 9 V9 15 17 Case N 9, 17 V9, V17 16 32 Case 1 19 V17 31 33 Case N 17, 33 V17, V33 32 34 Case 2 33 V33 33 40 Case 2 33 V33 39 5. Significance of the Work When Pascal graph merged with Hypercube to form Simple-(q,n)-graph 2; it showed great credentials to be exploited as a typical computer network topology. It alone can contribute substantially in this field of active research. This new discovery will earn Pascal graph high esteem through its reliability under erratic and exigent erroneous circumstances and make it sure that the situation does not exacerbate any more. As per property (iii) mentioned in some property of Pascal graph, it is very easy to access or traverse any node from v1 directly in a single hop. Every other node except v1 had to use either two hop (the two communicating nodes have even number indices) or single hop otherwise. Everything is fine till v1 is not perturbed. If, under any faulty circumstances, v1 gets disconnected then the above mentioned property no longer holds for Pascal graph and the reliability is seized with an increase in the minimum number of hops required by the message to travel from one node to another. In this paper we have reestablished its reliability under this circumstances by finding DNP that is similar to v1 in PG(n). by this work we have eradicated threat imposed upon Pascal graph by mollifying the faulty circumstances. The superiority of the graph is maintained very efficiently. As the whole work is not based on any convoluted formulae or theory, it is easy to exploit Pascal graphs high reliability, effective degree and diameter from computer network point of view. Now, it is a reliable choice for any network designer to opt the Pascal graph when reliability along with efficient degree and diameter are the key factors in designing. Since the new property is based on very simple logic it will be easier to incorporate the concept into the physical and logical layout of the computer network topology. 6. Scope of Future work Selecting various graph models to represent topologies of computer network had always been an active research area for network Scientists 5. The reasonable criteria behind this selection are very significant because this put long testing impact on the network. How to make a graph model an ideal choice to implement a specific topology would always impose a huge challenge to the upcoming Scientists. The chance of finding optimal, if not optimum, graph model with unparallel properties entirely depends on the institution of the Scientists, in-depth analysis of the graph and technical feasibility of implementing computer network using that graph. Finally, it can be said very intuitively that this field still holds immense scopes for Scientists for further research work. ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 35 7. Conclusion A source code has been written in C programming language to generate the Pascal Matrix of different order. The formulae were put into test for a meticulous checking of the existence of DNP in different Pascal Matrices generated by the program. From the case 3, the Pascal graph is at a precise level of reliability. The Pascal Matrix has been generated along with some extra details e.g. the degree of particular node and its index. Unlike other cases, it has got three nodes that are adjacent to all other nodes. References 1 N. Deo and Michael J. Quinn, “Pascal Graphs and their Properties”, Fibonacci Quarterly, vol. 21, pp. 203-214, 1983. 2 S. Chatterjee and S. S. Sarma, “In Search of a Versatile and Flexible Graph Model to Implement Computer Network”, Proceeding of International Conference on Communications, Devices and Intelligent Systems, pp. 635-638, 2004. 3 U. Bhattacharya and R. Chaki, “A New Scalable Topology for Multihop Optical Network” ASIAN, pp. 263- 272, 2000. 4 N. F. Mir, “Analysis of High Speed Interconnection Network”, Journal of Interconnection Networks, vol. 3, pp. 49-65, 2002. 5 E. L. Wilmer and M. D. Ernst, “Graphs induced by Gray Codes”, discrete Mathematics, vol. 257, pp. 585-598, November 2002. 6 S. S. Sarma and S. K. Bandyopadhyay, “Properties and Generation of Some special Graph”, AMSE Review, Vol. II, pp. 7-18, 1989. 7 H. K. Rosen, “Discrete Mathematics and its Applications”, TMH Edition, ISBN:0-07-053047-5. 8 A New Assignment Algorithm for Star Network Topology Design http:/kre.elf.stuba.sk/petrek/papers/dubrovnik.pdf 9 On Some Aspects of Design of Cheapest Survivable Networks, IJCSNS International Journal of Computer Science and Network Security, 210 VOL.7 No.11, November 2007. 10 Topological Design of Minimum Cost Survivable Computer Communication Networks: Bipartite Graph Method, International Journal of Computer Science and Information Security, Vol. 3, No. 1, 2009. 11 A Genetic Algorithm Approach to Optimal Topological Design of All Terminal Networks, http:/www.eng.auburn.edu/smithae/publications/refereed/berna.pdf. 12 Topological Design and Dimensioning of Agile All Photonic Networks, http:/www.tsp.ece.mcgill.ca/Networks/projects/pdf/mason_JournalCompComm06.pdf.