(PDF) النظم الوافرة جزئيا: أمثلتها ومعوليتها وأعمارها الجزئية

volume 1 number 1 december 2010 International Magazine on Advances in Computer Science and Telecommunications Editors in Chief Biljana Janeva Toni Stojanovski Contents Ali Muhammad Ali Rushdi, “Partially-Redundant Systems: Examples, Reliability, and Life Expectancy”, 1-13 Okuthe P. Kogeda and Johnson I. Agbinya, “Cellular Network Faults and Services Dependency Modeling”, 15-22 Ahmad A. Rushdi, “A Mathematical Model of the DNA Replication”, 23-30 Goetz Peter Gallert, “Mapping Network Protocols to Layers of the OSI Model”, 31-36 Edmar Mota-García and Rogelio Hasimoto-Beltran, “Fast Geographic Internet Mapping System for Location-Based Services”, 37-43 Rajesh Kumar Mishra and Sanjay Choudhary, “On Fixed Point Theorems in Fuzzy Metric Spaces”, 45-47 Association for Computer Science and Telecommunications AKOMNAT TEL DOO IMACST 1 (1) 1-47 (2010) ISSN 1857-7202 www.imacst.com International Magazine on Advances in Computer Science and Telecommunications VOLUME 1 NUMBER 1 DECEMBER 2010 Editors in Chief Professor Biljana Janeva, PhD Associate Professor Toni Stojanovski, PhD European University, R. Macedonia European University, R. Macedonia Associate Editors Professor Chung-Nan Lee, PhD Professor Ali Muhammad Ali Rushdi, PhD Department of Computer Science and Engineering, National Sun yat-sen King Abdulaziz University, Jeddah, Kingdom of Saudi Arabia University, Kaohsiung, Taiwan Professor Constantin Volosencu, PhD Professor Goce Arsov, PhD Faculty of Automatics and Computers, Politehnica University of Faculty of Electrical Engineering and Informatics, Sts Cyril and Methodius Timisoara, Romania University, Republic Of Macedonia Professor Gheorghe Duda, PhD Professor Gradimir V. Milovanović, PhD Faculty of Mathematics and Informatics, Spiru Haret University, Faculty of Computer Sciences, Megatrend University, Belgrade, Serbia Bucharest, Romania Associate Professor Hamidah Ibrahim, PhD Professor Hemant Kumar Pathak, PhD Faculty of Computer Science and Information Technology, School of Studies in Computer Science & IT, Pt. Ravishankar Shukla Universiti Putra Malaysia, Serdang, Selangor, Malaysia University, India Lecturer Hetalkumar J. Panchal, PhD Associate Professor Ion Cârstea, PhD G H Patel Post Graduate Department of Computer Science and Faculty of Automatics, Computers and Electronics, University of Craiova, Technology, India Romania Associate Professor Jasmina Novakovic, PhD Assistant Professor Jia-Ching Wang, PhD Faculty of Computer Sciences, Megatrend University, Belgrade, Department of Computer Science and Information Engineering, National Serbia Central University, Taiwan Associate Professor Kalinka Kaloyanova, PhD Professor Khurram Mustafa, PhD Department of Mathematics and Informatics, University of Sofia Department of Computer Science, Jamia Millia Islamia (Central "St. Kliment Ohridski", Bulgaria University), New Delhi, India Professor Manjaiah D.H, PhD Martin Takáč, PhD Department of Computer Science, Mangalore University, India Department of Computer Science, University of Otago, New Zealand Associate Professor Milan Sečujski, PhD Associate Professor Paresh Virparia, PhD Department of Telecommunications and Signal Processing, Department of Computer Science & Technology Sardar Patel University, University of Novi Sad, Serbia Gujarat, India Professor Petr Štěpánek, PhD Professor Po-Whei Huang, PhD Department of Theoretical Computer Science and Mathematical College of Science, National Chung Hsing University, Taiwan Logic, Charles University, Prague, Czech Republic Professor Priti Srinivas Sajja, PhD Professor Radu-Emil Precup Post Graduate Department of Computer Science, Sardar Patel Faculty of Automation and Computers, Politehnica University of University, India Timisoara, Timisoara, Romania Professor Rajesh Shrivastava, PhD Assistant Professor Risto Atanasov, PhD Department of Mathematics, Government Science and Commerce Western Carolina University, USA Benazeer College, Bhopal (MP), India Professor Sumam Mary Idicula, PhD Associate Professor Zsolt Polgar, PhD Department of Computer Science, Cochin University of Science Faculty of Electronics and Telecommunications, Technical University of and Technology, India Cluj Napoca, Romania International Magazine on Advances in Computer Science and Telecommunications VOLUME 1 NUMBER 1 DECEMBER 2010 CONTENTS ALI MUHAMMAD ALI RUSHDI Partially-Redundant Systems: Examples, Reliability, and Life Expectancy 1-13 OKUTHE P. KOGEDA AND JOHNSON I. AGBINYA Cellular Network Faults and Services Dependency Modeling 15-22 AHMAD A. RUSHDI A Mathematical Model of the DNA Replication 23-30 GOETZ PETER GALLERT Mapping Network Protocols to Layers of the OSI Model 31-36 EDMAR MOTA-GARCÍA AND ROGELIO HASIMOTO-BELTRAN Fast Geographic Internet Mapping System for Location-Based Services 37-43 RAJESH KUMAR MISHRA AND SANJAY CHOUDHARY On Fixed Point Theorems in Fuzzy Metric Spaces 45-47 IMACST is published by the Association for Computer Science and Telecommunications AKOMNAT TEL DOO. IMACST is an open access publication. IMACST 1 (1) 1-47 (2010) ISSN 1857-7202 www.imacst.com IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 1 Partially-Redundant Systems: Examples, Reliability, and Life Expectancy Ali Muhammad Ali Rushdi  components. At the core of this field is the concept of the k- Abstract— This paper is a brief tutorial exposition of some out-of-n:G(F) system (also called a partially-redundant recent developments in the evaluation of the reliability of system), which is a system of n components that functions partially-redundant (k-out-of-n) systems. A novel contribution of (fails) if at least k out of its components function (fail) [1-14]. the paper is that it identifies many practical examples of such systems, which are spread across a wide spectrum of engineering Typically, the k-out-of-n system (for 1  k < n) is intended to disciplines, including, in particular, the areas of computer and provide useful redundancy, i. e., to have a reliability better telecommunication engineering. Some formulas for the reliability than that of the simplex or single-component reliability. This and life expectancy of these systems are discussed in the case of necessitates that the simplex reliability itself be good enough equal-reliability components. Certain celebrated formulas are (based on the values of k and n). For the same simplex shown to be numerically unstable and totally useless in the case reliability, more useful redundancy is achieved the lower k is of large systems with high-reliability components. In fact, these formulas are highly susceptible to round-off errors and severely for a fixed n, and the higher n is for a fixed k. suffer from catastrophic cancellations. The paper also reviews how the Boole-Shannon expansion (or equivalently, the pivoting The k-out-of-n system has many attractive features. It has a or factoring technique) is used to derive pertinent recursive symmetric structure that has many convenient mathematical relations, leading to a highly efficient algorithm for k-out-of-n descriptions such as Boolean expressions, recursive equations, reliability evaluation. This algorithm has a nice interpretation in generating functions and so on. Nevertheless, for 1 < k < n, terms of a regular Mason signal flow graph, which turns out to be (a) a reduced ordered binary decision diagram representing a the k-out-of-n system lacks a graphical representation in the monotone symmetric switching function, and (b) analogous to the form of a network or a fault tree, unless replicated network minimal circuit realization of this function. In the worst case, the edges or fault tree inputs are allowed. The k-out-of-n system temporal and spatial complexities of this algorithm are shown to plays a central role for the general class of coherent systems, be quadratic and linear, respectively, in the number of system as it can be used to approximate the reliability of such systems components. The paper lists some extensions and applications of [15], and its reliability function is the steepest function among this algorithm and compares it with a few related algorithms. The paper concludes with a quick consideration of some all coherent reliability functions of order n [8]. While virtually important issues in the area of k-out-of-n system reliability, all nontrivial network reliability problems are known to be including the issues of useful redundancy, criticality measures, NP-hard for general networks [16], the regular structure of the and cost. k-out-of-n system allows the existence of simple efficient algorithms for its reliability analysis that are of quadratic-time Index Terms— Coherent system, k-out-of-n system, linear-space complexity in the worst case [2-4, 6]. Normalized life expectancy, Reliability, Catastrophic cancellation, ROBDD, Useful partial redundancy. The k-out-of-n system is being rediscovered in the literature from time to time without being identified as such (See, e.g., I. INTRODUCTION [17] and [18], where that system, as well as extensions and compositions thereof appear in disguise). We hope that the T HE reliability R(t) of a component or a system is the probability that it will adequately perform its specified purpose/job/function for a specified semi-closed period of present exposition may remedy this situation (at least partially), by familiarizing a large readership with an extensive number of examples of the k-out-of-n system. Though the time (0, t] under specified environmental conditions. Implicit results of this paper are relating system reliability to in this definition is the assumption or condition that the component reliabilities, these results are also applicable in the pertinent component or system is initially good (i. e., at t = 0, context of availability. R = 1.0). The field of system reliability deals with the relation between the reliability of a system and the reliabilities of its This paper is intended to be a review or a tutorial exposition, and we hope to make it of a significant pedagogical utility. We Manuscript received August 30, 2010. A. M. A. Rushdi is with the Department of Electrical and Computer strive strongly for simplicity and clarity to allow a non-expert Engineering, King Abdulaziz University, P. O. Box 80204, Jeddah 21589, reader to easily follow our discussion. Therefore, we Saudi Arabia. (Email:

) deliberately include certain details and explanations of 1857-7202/1008007 2 A.M.A. RUSHDI: Partially-Redundant Systems: Examples, Reliability and Life Expectancy terminology that experts might consider obvious or even Xi = failure of component i = indicator variable for trivial. The absence of such details in some papers has unsuccessful operation of component i, ( X i = 0 occasionally led to misunderstanding and pitfalls. Mostly, we iff component i is good, while Xi = 1 iff do not start our reliability analysis directly in the probability component i is failed). The success Xi and (algebraic) domain, but we initiate it in the switching failure X i are complementary variables. (Boolean) domain, and then transform our results to the algebraic domain. We try to fully utilize the wealth of X = a vector of n elements representing the knowledge available for switching (Boolean) algebra [19]. We component successes X = [ X1 X2 ... Xn ]T. adopt the special symbols representing the operators of this S(X) = indicator variable for the successful operation of the system, called system success. algebra instead of borrowing symbols from real algebra, which S(k, n, X) = success of a k-out-of-n:G system of component could be confusing and misleading [20]. In particular, we use successes X, 0  k  (n+1). the symbol () (rather than the symbol (+)) for the OR Sy(A, X) = a symmetric switching function of the switching operation. For convenience, we will use R(p) or switching variables X, where: R(p) to denote the system reliability for non-identical A = characteristic set = {a | 0  a  n, a is the component reliabilities p or a common component reliability number of 1's assignments of the Xi's for which p, i.e., we will make the time dependence of R implicit the symmetric function is 1}. through the time dependence of p or p. Pr[…] = probability of the event […]. E[...] = expectation of the random variable [...]. The organization of the remainder of this paper is as follows. pi, qi = reliability and unreliability of component i; Section II lists the assumptions, notation and nomenclature Both pi and qi are real values in the closed real employed throughout the rest of the paper. Section III interval [0.0,1.0]. identifies many reliability systems related to the k-out-of-n pi = Pr[ Xi = 1 ] = E[ Xi ] = 1.0 – qi. system, while Section IV lists many practical examples of that p = a vector of n elements representing the system, which are spread across a wide spectrum of component reliabilities, p = [p1 p2... pm-1 pm engineering disciplines, including, in particular, the areas of pm+1... pn]T. computer and telecommunication engineering. Closed-form q = a vector of n elements representing the formulas for k-out-of-n system reliability and life expectancy component unreliabilities = 1.0 – p, where 1.0 are given in Section V for the case of equal-reliability is an n-tuple of real 1’s. components. Section V also adds some pictorial insight to the p/pm = a vector of (n-1) elements obtained by omitting topic, and points out a pitfall that went practically unnoticed in the mth element of vector p. the reliability literature. Section VI discusses how the Boole- p|jm = a vector of n elements obtained by setting the Shannon expansion (or equivalently, the pivoting or factoring mth element of p to j which is either 0 or 1. R(p),U(p) = reliability and unreliability of the system. Both technique) is employed to derive binary-recursive relations as R(p) and U(p) are real values in the closed real well as an efficient iterative algorithm for computing the interval [0.0,1.0]. reliability of a k-out-of-n system with non-identical R(p) = Pr [ S(X) = 1 ] = E[ S(X )]. components. Section VII discusses complexity issues for this U(p) = 1.0 – R(p). algorithm and compares it with other notable algorithms. R(k, n, p) = reliability of a k-out-of-n:G system of Section VIII concludes the paper. component reliabilities p, 0  k  (n+1). R(k, n, p) = the value of R(k, n, p) when component reliabilities are all equal to a common value p. II. ASSUMPTIONS, NOTATION, AND NOMENCLATURE U(k, n, p) = unreliability of a k-out-of-n:G system of A. Assumptions component reliabilities p, 0  k  (n+1). U'(k, n, q) = unreliability of a k-out-of-n:F system of  Both the components and the system are of two states, component unreliabilities q, 0  k  (n+1). i.e., either good or failed. This is the complemented dual of R(k, n, p) in  Component states are statistically independent. the sense that the successes of the k-out-of-n:G  The system is a mission-type one, i. e., without repair. system and the k-out-of-n:F system are dual switching functions. B. Notation n = number of system components, n  0. U(k, n, p) = U'(n–k+1, n, q). (1) Xi = success of component i = indicator variable for successful operation of component i = a c(k, n) = the binomial (combinatorial) coefficient = the switching random variable that takes only one number of ways of choosing k objects from a of the two discrete values 0 and 1; (Xi = 1 iff set of n objects, when repetition is not allowed component i is good, while Xi = 0 iff component and order does not matter. Binomial i is failed). coefficients satisfy Pascal's identity IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 3 c(k, n) = c(k, n–1) + c(k–1, n–1), 0 < k < n, (2) Pivoting: by pivoting on component number m, the system reliability R(p) can be written as together with the boundary conditions R(p) = qm * R(p | 0m) + pm * R(p |1m), (5) c(k, n) = 1, (k = 0 or k = n) and n  0. (3) where R(p | 0m) and R(p | 1m) are the reliabilities of the minors or E/F = the set difference of sets E and F, subsystems of the original system with respect to component m. E/F = {j | j  E, j  F}. Pivoting is also called factoring and is equivalent to the total |Y| = cardinality of the finite set Y = the number of probability theorem [11] in the algebraic domain or to the Boole- elements in the set Y. Shannon expansion [19] in the Boolean domain. y = the ceiling of the real number y = the smallest integer greater than or equal to y. III. RELATED SYSTEMS The k-out-of-n:G system covers many interesting or limiting- C. Nomenclature case systems as special cases [6]. These include the fictitious Duality: strictly speaking, the dual of switching function is perfectly reliable system (k = 0), the parallel system (k = 1), the obtained by complementing the function and all its switching voting or N-modular redundancy (NMR) system (k = (n+1)/2), arguments (inverting both output and inputs) [6]. In the the fail-safe system (k = n – 1), the series system (k = n), and reliability literature, "duality" is sometimes freely and loosely the fictitious totally unreliable system (k = n+1). Note that as k used to indicate "similarity," "analogy," or "being mirror decreases (for a fixed n) from 0 to (n+1), the usefulness of the k- images." out-of-n:G system declines and finally diminishes. For 1 < k < n, the k-out-of-n system is sometimes called a partially-redundant Monotone: a monotone system is one whose reliability function system [6, 24], as it lies somewhere between the extreme cases of is a non-decreasing function in each component reliability, i.e., the (non-redundant) series system and the (fully-redundant) parallel system. In this paper, we will view these two extremes R(p | 1m) – R(p | 0m) = ∂R(p) / ∂pm  0.0, 1  m  n. (4) of zero and total redundancies as limiting cases of partial redundancy, and hence consider a k-out-of-n system as Relevant: component number m is relevant to the system if there synonymous to a partially-redundant system. The k-out-of-n:G exists a valid value for p such that ∂R(p) / ∂pm ≠ 0.0. system and the k-out-of-n:F system are dual or mirror images of Relevancy means that R(p )is not vacuous in (independent of) pm. one another; the k-out-of-n:G system being exactly equivalent to the (n–k+1)-out-of-n:F system (as formally indicated by equation Coherent: a coherent system is a monotone system whose (1) above). components are all relevant [21]. If the reliability function R(p) of a coherent system with equal-reliability components is plotted The k-out-of-n: G system is a subclass of some important versus p within the square 0.0  p  1.0, 0.0  R(p)  1.0, systems. Besides being a coherent system for the values 1  k  then it satisfies R(0.0) = 0.0, and R(1.0) = 1.0, and exhibits an S- n, it is s-p complex for 1 < k < n. It is also shape, i. e., the curve R(p) versus p is monotonically non- decreasing and if it crosses the diagonal (p versus p), it does so a) a special case {r = n} of the consecutive-(n–k+1)-out-of-r- only once and from below [8, 22]. from-n:F system [25], b) a limiting case { ℓ = n} of the generally non-coherent k- k-out-of-n:G system: a system that is good if and only if (iff) at to- ℓ-out-of-n system [10, 26-28], which is useful in least k out of its n components are good. approximating the class of non-coherent systems [15], but does not precisely exhaust or cover such a class k-out-of-n:F system: a system that is failed iff at least k out of (contrary to a claim made in [28]), its n components are failed. c) a binary-state limiting case of the multi-state k-out-of-n system model [29]. k-out-of-n (partially-redundant) system: a collective name for k-out-of-n:G and k-out-of-n:F systems; a k-out-of-n:F system is An important generalization of the k-out-of-n:G(F) system is the equivalent to an (n–k+1)-out-of-n:G system (as indicated by threshold system, which can be neither symmetric nor coherent. equation (1)). A k-out-of-n system is a coherent system in the A threshold system is a system whose success is a threshold practical case of 1  k  n, while it is only monotone for the (linearly-separable) switching function in the successes of its hypothetical or fictitious limiting cases of k = 0 and k = (n+1). components [30]. This system is successful if and only if the weighted arithmetic sum of its component successes is equal to s-p complex: a coherent system is series-parallel (s-p) complex or exceeds a certain threshold. Therefore, a threshold system is iff it has no components in series or in parallel [23]. A k-out-of-n characterized by (n+1) coefficients, namely, its threshold and the system is s-p complex for 1 < k < n, and hence cannot be treated set of its n component weights (which are not necessarily (even partially) by series-parallel reductions. unique). An important special case of the threshold system is the weighted k-out-of-n:G system, which is a coherent non- 1857-7202/1008007 4 A.M.A. RUSHDI: Partially-Redundant Systems: Examples, Reliability and Life Expectancy symmetric system of strictly positive weights and a threshold coherent or non-coherent, and asking for an example showing its equal to k [12, 31]. If further, all the weights are equal to 1, the utility as a model for a real-life system. Evans (then Editor of the weighted k-out-of-n:G system reduces to the ordinary k-out-of- IEEE Transactions on Reliability) [40] responded that "the n:G system. Therefore, the k-out-of-n:G system can be defined problem as originally (and implied) [37] is an example of a as a threshold system with a common positive weight for its collection of words that appears to make sense, but is actually components and a threshold equal to k multiplied by this self contradicting." Fortunately, the questions posed by Rushdi common weight [30]. [40] prevented the appearance of more algorithms that represent correct but irrelevant mathematics. These questions are hailed A system that is closely related to the k-out-of-n:G(F) system is by Hwang [41] as an example of a critical review of literature the consecutive k-out-of-n:G(F) system, which functions (fails) that prunes overgrown branches in order to keep the growth in if at least k consecutive components function (fail) [32, 33]. The control. Such a pruning is always necessary when enthusiasm of k-out-of-n:G(F) system and the consecutive k-out-of-n:G(F) expansion overextends its usefulness [41]. system are not generally comparable since neither of them is a subclass of the other (except when they overlap at their limiting cases k  1 and k  n). The k-out-of-n system is a threshold IV. EXAMPLES OF PARTIAL REDUNDANCY system, but generally the consecutive-k-out-of-n system is not. A model is a useful representation that captures the essence of a The k-out-of-n system is structurally symmetric, i.e., the order of real system and behaves sufficiently like it in such a way that its components is immaterial, while the set of components in a conclusions can be drawn from the model's behavior to aid in consecutive k-out-of-n system is an ordered one (either on a line making prudent decisions about the real system. Situations in or on a circle, corresponding to linear and circular versions of the which the k-out-of-n:G(F) system serves as a useful model are system). The failure switching function of the consecutive k-out- frequently encountered in engineering practice and include the of-n:F system implies that of the k-out-of-n:F system, and hence following examples: the reliability of the latter system is a lower bound of that of the former system. a. A piece of stranded wire with n strands in which at least k strands are necessary to pass the required current behaves Yet another system that is also closely related to the k-out-of- as a k-out-of-n:G system. The same concept generalizes to n:G(F) system is the (n, f, k) system. This system is defined in applications involving supply-type components with [34] (based on a proposal in [35]) to consist of n components identical fixed ratings for their capacity, flow, throughput, ordered in a line or a cycle, such that the system fails if, and strength or the like, such that system success is achieved only if, there exist at least f failed components or at least k when a minimum supply is met, or when a certain consecutive failed components. This system reduces to the k- threshold is exceeded (see, e.g., [24, 30]). out-of-n:F system for f  k. A generalization of the (n, f, k) system is one with weighted components [36]. b. A three-engine airplane which can stay in the air if and only if at least two of its three engines are functioning is a Occasionally, we might have a system consisting of certain 2-out-of-3:G (also called a 2-out-of-3:F system or a triple subsystems, which in turn consist of lower-level subsystems, and modular redundancy (TMR)) [13]. A space vehicle so on, till we reach some innermost subsystems that consist of requiring three out of its four main engines to operate in final components. If the relation between every sub(system) and order to achieve orbit is a 3-out-of-4:G and also a 2-out-of- its constituent components or subsystems is a k-out-of-n relation, 4:F system [9]. The common practice of having a spare tire the overall system is a k-out-of-n composition [8, 22]. Under in a 4-wheel car constitutes a 4-out-of-5:G and also a 2- appropriate conditions, the k-out-of-n composition can serve to out-of-5:F system. All these are examples of a fail-safe achieve a dramatic increase in reliability by constructing ultra- system, i. e., a system that tolerates the failure of one (and highly-reliable systems out of typical or ordinary but somewhat only one) component, since such a failure reduces the good components. In such a composition, it is preferable to system to a series system, which is still a working system locate the more useful redundancies in the lower or innermost (albeit with no more redundancy, and hence no capability levels of the composition. to withstand any further failure). The idea of a fail-safe system works well provided the assumption of statistical A system that would have been related to the k-out-of-n:G(F) independence among components holds. A car driver system is the so called strict consecutive-k-out-of-n:G(F) system cannot rely on a single spare tire on a rough unpaved road (or simply, strict system) proposed in [37]. The original that might result in a double flat tire (instantaneous or definition of this system suffered from ambiguity or common-cause failures). Thanks to a merciful Providence, inconsistency. Rushdi [38, 39] attempted to produce well- the fail-safe concept is entrenched in many biological defined versions of this system, either by accounting for systems. For example, a human being can survive the statistical dependencies among its components, or by employing failure of one of his two kidneys, which constitute a 1-out- conditional probabilities. However, these versions lacked the of-2:G system. claimed utility of the original system. Later, Rushdi [40] published his concerns about the strict system demanding a c. Reactor protection systems, sensor systems, alarm unique, precise, and consistent definition of it, enquiring about generation systems and other decision mechanisms usually the real nature of some of its states, questioning whether it is employ a k-out-of-n:G voting logic [42]. Voting is also IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 5 used in the realization of ultra-reliable systems that are of-6:F system is a lower bound for the reliability of this based on multichannel computations [43]. Likewise, voting structure. is commonly used in faulty distributed computing systems to achieve mutual exclusion among groups of isolated i. The k-out-of-n model is used in the petro-chemical nodes. industry in the evaluation of the life of furnace systems and in decision making on when to replace the furnaces d. A bridge with n main supports that can survive an [49, 50]. The furnaces are considered to be systems earthquake if and only if at least k supports remain intact is while the tubes in the furnaces are the components of the approximately modeled as a k-out-of-n:G system. Here, the corresponding systems. A tube is designed to provide an modeling is qualitative rather than quantitative, since a environment for methane, steam, and a catalyst to react bridge is usually not structurally symmetric with respect to at a high temperature to produce hydrogen. A tube is its supports, while a k-out-of-n system is structurally considered failed when it is unable to perform its symmetric with respect to its components. intended function any more (for example, when it is ruptured or is pinched). The function of a furnace is to e. In a binary communication channel, an error-correcting produce hydrogen at certain output, temperature, code might be employed in the transmission of n-bit code- pressure, and efficiency [49]. If too many tubes (k or words [44]. If the code is capable of correcting up to k bit more out of n) are failed, the furnace’s proper operation errors, word transmission becomes a (k+1)-out-of-n:F and is affected, and it is failed. This is a k-out-of-n:F system. also a (n-k)-out-of-n:G system. A code lacking any error- correcting capability (k = 0) {such as the BCD code j. In mining operations, a shovel-truck system in an open without any parity check} is a series system, while a code mine usually consists of a shovel and a fleet of n trucks of a Hamming distance 3 (k = 1) {such as the famous (say 20 trucks). The system functions properly if at least (7,4,1) Hamming code} is a fail-safe system. k trucks (say 15 trucks) and the shovel are good. This is a series system of 2 subsystems: the shovel and a 15-out- f. A bus-structured multiprocessor computer system consists of-20:G system. If the shovel is assumed to be perfectly of n processors sharing m memory units via b common reliable, the system becomes simply a 15-out-of-20:G buses. If this system is required to operate in MIMD mode system. In general, the k-out-of-n concept is useful in (i.e., with Multiple Instruction streams and Multiple Data modeling many types of fleets of vehicles, including streams), then it is logically equivalent to the series aircrafts, ships, buses, and trains. connection of a k1-out-of-n:G system, a k2-out-of-m:G system and a 1-out-of-b:G system, where k1  2 and k2  1 k. In a perfect secret sharing scheme (PSSS), a secret is to with the precise values of k1 and k2 being determined by be divided into shares, and distributed among members. system requirements [45]. The secret can be determined, i.e., the system works when k or more distinct members collaborate together, g. In the majority voting (MV) algorithm for managing but only k shares are required to reconstruct the secret. replicated data, out of n copies of an object (n+1)/2 In the context of perfect secret sharing, the secret can be copies must be up to form a quorum [18]. This is an reconstructed with any k or more members, but (k–1) or (n+1)/2-out-of-n:G system. A generalization of this fewer members cannot reveal anything about the secret algorithm, the hierarchical quorum consensus (HQC) [51]. The PSSS is nothing but a k-out-of-n:G system, in algorithm is a multilevel system in which the availability of the sense that the reliability of this system expresses the a group at level i expressed in terms of the availability of probability of constructing the secret as a function of the its subgroups at level (i+1) constitutes a ki-out-of-ni:G probabilities of member contributions to such a system. This means that HQC is nothing but an iterative or construction. repeated composition (See, e. g., [8, pp. 202-203] or [22, pp. 203-206]) of the MV structure. Such a composition improves availability (making HQC superior to MV) V. SYSTEMS WITH COMPONENTS OF EQUAL RELIABILITIES provided the basic component availability is higher than a A. Reliability certain value [8, 22, 46]. The reliability of a k-out-of-n:G system (with independent h. The k-out-of-n model is useful in the study of multistage components of identical reliabilities p) equals the probability interconnection networks [47]. For example, the terminal of at least k successes in n Bernoulli trials, and hence it is reliability of a Gamma network [48] is represented by a given by [6]: ladder network (of unreliable nodes and perfect links) n whose behavior can be approximated by that of a k-out-of- R(k, n, p) =  c(i, n) p i (1 – p) n – i, (6) n system. Specifically, the ladder network in [48, Fig. 5] i= k and in [47, Fig. 1] is logically equivalent to a series n connection of two components with a structure that has 8 cut sets of two components each. The reliability of a 2-out- =  (–1) m= k m–k c(k – 1, m – 1) c(m, n) pm. (7) 1857-7202/1008007 6 A.M.A. RUSHDI: Partially-Redundant Systems: Examples, Reliability and Life Expectancy 1018, drastically violating the restriction R  1.0). As a matter Formula (7) is considered more suitable than formula (6) for of fact, the two reliability equations start off identically equal hand calculation [11, 52], because (7) expresses R(k, n, p) as a or almost equal up to about n = 40 before the results produced polynomial of p only, while (6) involves powers of both p and by formula (7) start to deviate and overflow, as demonstrated (1.0 – p). In fact, formula (7) seems more convenient for in Fig. 1(c). To quantify the comparisons of (6) versus (7), symbolic differentiation needed to express the instantaneous numerical values of the computed reliability are summarized hazard rate (– (dR(t)/ dt) / R(t)), and for symbolic integration in Table I, for values on n between 20 and 80. required to find the life expectancy according to the (a) 17 (b) forthcoming equation (8). 1.5 15 x 10 1 Reliability: R Reliability: R B. Life Expectancy 10 0.5 The life expectancy or Mean Time To Failure (MTTF) of a 5 general non-repairable or mission-type system is given (under 0 appropriate assumptions on the behavior of R(t) as t tends to infinity) by -0.5 20 40 60 80 0 20 40 60 80 Number of system components: n Number of system components: n  (c) T  MTTF   R (t ) dt. 1.5 (8) 0 1 Reliability: R For a k-out-of-n:G system having components subject to a 0.5 common constant failure rate (CFR) λ, the component 0 reliability is Equation (6) Equation (7) p (t )  e   t , t ≥ 0, (9) -0.5 20 25 30 35 40 Number of system components: n so that the MTTF of a single component is (1/ λ), while the Figure 1. Reliability R(20, n, 0.9) versus the number of system MTTF of the system itself is obtained from equations (7)–(9) components n for a 20-out-of-n:G system, as computed via: (a) Equation as (6) for n between 20 and 80, (b) Equation (7) for n between 20 and 80, and (c) Equations (6) and (7) overlapped for n between 20 and 45.  n Similarly, Figure 2 illustrates the computational accuracy of T   (1)mk c (k 1, m 1) c (m, n)(et )m dt, formulas (11) and (10). In Figs. 2(a) and 2(b), the normalized 0 mk life expectancy (λT) is computed via formulas (11) and (10), n (1) m  k   mk m c ( k  1, m  1) c ( m, n). (10) respectively, for n varying from 20 to 80. Similarly to formula (7), formula (10) goes fast to very high erroneous values as n grows, while formula (11) continues to produce accurate values. Figure 2(c) verifies the fact that the results of the two We call the dimensionless product (λT) the normalized life life expectancy formulas stay almost equal up to about n = 40 expectancy of the system, since it is the quotient of the actual before the results produced by formula (7) start to deviate and life expectancy of the system by the life expectancy of a single overflow. To quantify the comparisons of (11) versus (10), component. A simpler expression for T, can be obtained from numerical values of the normalized life expectancy are the Markovian state diagram for a k-out-of-n:G system [53], summarized in Table I, for values on n between 20 and 80. namely n 1 1 T   m. mk (11) C. Computational Accuracy Figure 1 demonstrates our computational experience with formulas (6) and (7). Specifically, Fig. 1 presents the reliability R(k, n, p) versus n for a k-out-of-n:G system with k = 20 and a component reliability p = 0.9. In Figs. 1(a) and 1(b), the system reliability R(k, n, p) is computed via formulas (6) and (7), respectively, for n varying from 20 to 80. While formula (6) maintains its stability at values of R(20, n, 0.9) approximately equal to 1.0 as n grows, formula (7) produces results that grow to extremely high values (up to the order IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 7 (a) 18 (b) Certainly a value of R(20,45,0.9) expressed as (1.0 – 6 x 10 3.6637×10-15) is more informative and easier to grasp and 1.5 comprehend than when expressed as (0.999999999999996). Life Expectancy:  T Life Expectancy:  T 1 4 0.5 TABLE II. ACCURATE RELIABILITY AND UNRELIABILITY VALUES 2 0 Formula (6) Value of n -0.5 0 R(20, n, 0.9) 1.0 –- R(20, n, 0.9) 20 40 60 80 20 40 60 80 Number of system components: n Number of system components: n 20 0.121576654590569 8.7842×10-1 (c) 1.5 25 0.966600055388505 33.3999×10-3 Equation (11) Life Expectancy:  T 1 Equation (10) 30 0.999910922126177 8.9078×10-5 0.5 35 0.999999937506507 6.2493×10-8 40 0.999999999980403 1.9597×10-11 0 45 0.999999999999996 3.6637×10-15 -0.5 20 25 30 35 40 Number of system components: n Figure 2. Normalized life expectancy (λT) versus the number of system Despite the fact that formulas (7) and (10) are frequently cited components n for a 20-out-of-n:G system, as computed via: (a) Equation in the reliability literature, and despite their amicable (11) for n between 20 and 80, (b) Equation (10) for n between 20 and 80, suitability to hand calculations, they become totally worthless and (c) Equations (11) and (10) overlapped for n between 20 and 45. from the numerical point of view when dealing with large systems of high component reliabilities. These formulas are TABLE I. NUMERICAL RELIABILITY AND LIFE EXPECANCY VALUES highly susceptible to round-off errors and severely suffer from catastrophic cancellations, and therefore they produce the Value R(20, n, 0.9) λT highly erratic plots in Figures 1 (b), and 2(b). In retrospect, the of n Formula (6) Formula (7) Formula (11) Formula (10) undesirable behavior of formulas (7) and (10) should have 20 0.1216 0.1216 0.0500 0.0500 been anticipated since they are essentially outcomes of the numerically-notorious inclusion-exclusion principle [6]. By 30 0.9999 0.9999 0.4472 0.4472 contrast, formulas (6) and (11) are purely additive formulas 40 1.0000 1.0518 0.7308 0.6744 and are really minimally insensitive to round-off errors. 50 1.0000 1.5169×104 0.9515 3.4090×104 60 1.0000 5.3790×109 1.1321 8.6123×109 D. Pictorial Representation 70 1.0000 1.6780×1014 1.2851 3.7537×1014 The unreliability U(k, n, p) of a k-out-of-n:G system is the 80 1.0000 1.5833×1018 1.4177 6.1526×1018 probability of at most (k–1) successes in n Bernoulli trials, and hence it equals the Cumulative Distribution Function (CDF) B(k–1, n, p) of the binomial distribution. Figure 3 shows a In passing, we need to alert the reader to some smoothing very regular Mason signal flow graph (SFG) that illustrates effect exhibited in the small-size drawings of Figs. 1(a) and the computation of B(i, j, p) [6, 54, 55]. Note that each 2(a). Though these two figures represent numerically stable diagonal arrow has a transmission equal to p, while each computations, their initial values at n =20 are indistinguishable horizontal arrow carries a transmission equal to q = 1.0 – p. from zero though they are not zeroes (albeit somewhat small). There are two types of nodes: (a) Source nodes of known According to Table I, the value of R(20, 20, 0.9) is (0.9)20 = values which are either black or white. A black node has a 0.121576654 or approximately 0.1216, while the value of λT value of 1.0 while a white node has a value of 0.0, and (b) for n = 20 is (1.0/20) = 0.05. For n > 40, the graph of Fig. 1(a) Non-source nodes drawn as shaded ones, which include (at is not distinguishable from 1.0, which is typical for highly- or least) one sink node whose value is the final result sought. ultra-highly-reliable systems. Table I is not better than Fig. (1) Figure 3 is therefore a pictorial representation of the in this case, since it reports values of 1.0000 for R(20, n, 0.9) computation of U(i+1, j, p). It can be made to represent the and n > 40. Better accuracy or significance is attained for computation of R(i+1, j, p) by either interchanging the colors highly- or ultra-highly-reliable systems if we report their (and values) of the source nodes, or swapping the symbols p and unreliabilities in floating-point arithmetic instead of their q [6]. If further, algebraic multiplication and addition are reliabilities in fixed-point arithmetic. This point is clarified by replaced by their logical counterparts (ANDing and ORing), Fig. Table II, which present some k-out-of-n reliabilities in fixed- 3 can also be made to represent the computation of the success point arithmetic together with their complements or function S(i+1, j, X) [6], and can then be identified as a Reduced corresponding unreliabilities in floating-point arithmetic. Ordered Binary Decision Diagram (ROBDD), which is well 1857-7202/1008007 8 A.M.A. RUSHDI: Partially-Redundant Systems: Examples, Reliability and Life Expectancy known to be the state-of-the art data structure for encoding and PREs are algorithms based on the use of the Boole-Shannon manipulating switching functions [10, 56, 57]. Figure 3 is also expansion [61-63]. In the following subsections, we describe analogous to tank circuits, which are minimal pass-network how the Boole-Shannon expansion is used to derive pertinent realizations of symmetric switching functions [58]. Moreover, recursive relations, leading to a highly-efficient algorithm for k- Fig. 3 has certain similarities and minor dissimilarities with out-of-n reliability evaluation. Pascal's triangle that reflect the similarities and dissimilarities of the forthcoming recursive equations (15a) and the boundary conditions (15c&d) with their counterparts (2) and (3). Fig. 3 has also good similarities and minor dissimilarities with the signal flow graph that illustrates the computation of the probability mass function (pmf) of the generalized binomial distribution [54, 55]. VI. RELIABILITY ANALYSIS FOR K-OUT-OF-N SYSTEMS WITH NON-IDENTICAL COMPONENTS There are three general classes of methods for system reliability analysis, namely; (1) the inclusion-exclusion method, (2) the methods of disjoint products, and (3) the Boole-Shannon expansion or equivalently pivoting (pivotal decomposition or factoring) [6]. These classes of methods are applicable (and have been extensively applied) to the reliability analysis of k-out-of-n systems. The inclusion-exclusion principle was the readily- available tool from classical probability theory [11], and naturally became the basis of early attempts for evaluating the Figure 3. A Mason signal flow graph that illustrates the computation reliability of k-out-of-n systems with non-identical of the CDF B(i, j, p) of the binomial distribution. components (See, e. g., [6, 59]). Though the computational disadvantages of this principle are now well known [6], new A. Recursive Techniques methods are still being forwarded that are reproducing its results, sometimes without identifying them as such. For example, the recent direct method in [60] reproduces (in The Boole-Shannon's expansion [19] for a (totally) symmetric disguise) the improved inclusion-exclusion formula (5.29) of switching function of n variables X about one of these variables, [6] as its main result (1). The fact that these two formulas are namely, Xm, 1  m  n, can be stated as follows [3, 6] identical becomes clear if one identifies the tabulated coefficient bk(m) of [60] as a shifted binomial coefficient c(k–1, Sy(A, X) = X m Sy(B, X/Xm)  Xm Sy(C, X/Xm), (12) m+k–2). Nevertheless, [60] contributes a novel elegant proof via mathematical induction for the inclusion-exclusion result. where the characteristic set A is a subset of Zn+1 = {0,1, ...,n} and the sets B and C are subsets of Zn = {0, 1, ..., n–1}. Let A be The study of system reliability has been classically achieved in given by A = {a0, a1, ..., au}, u  n, then, we have terms of purely real-algebraic structure functions [8]. An equivalent approach is more insightful and less error-prone B = A Zn= A if au  n for the methods of disjoint products or the Boole-Shannon expansion. This approach is a logical formulation that utilizes = A/{n} if au = n , the isomorphism between the algebra of events (set algebra) and the bivalent or 2-valued Boolean algebra (switching A1 = { a0 - 1, a1 - 1, ... , a u - 1}, algebra). In this approach, one expresses the system success as a logical (switching or Boolean) function of the component successes. Next, one moves from the Boolean domain to the C = A1  Z n = A1 if a0  0 probability domain so as to obtain the system reliability as a = A1 /{-1} if a0 = 0. function of the component reliabilities. This is facilitated by converting the switching (Boolean) expression for the system Now, the success function of a k-out-of-n:G system is the success into a probability-ready expression (PRE), i.e., into an symmetric monotone switching function [3, 6] expression that is directly convertible, on a one-to-one basis, to a probability expression. Note that in a PRE: (a) all ORed S(k, n, X) = Sy({k, k+1, ..., n} , X). (13) terms (products) are disjoint, and (b) all ANDed alterms (sums) are statistically independent. The conversion from a For 1  k  n, S(k, n, X) can be expanded via Eq. (12) with PRE to a probability expression is trivially achieved by A = {k, k+1,..., n}, B = {k, k+1,..., n–1} and C = {k–1,k,...,n–1}, replacing Boolean variables by their expectations, AND which produces the recursive equation: operations by multiplications, and OR operations by additions [61-63]. The most powerful class of algorithms producing IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 9 S(k, n, X) = X S(k, n–1, X/Xm)  Nodes are visited column-wise, starting from the leftmost m Xm S(k–1, n–1, X/Xm), (14a) column (j = 1) and ending at the rightmost column (j = n). Within each column j, the bottom node (i = min(j, k)) is visited 1  k  n, first, and then followed by upper nodes till the top node (i = max(1, j–n+k)) is reached. while for the limiting cases k = 0 and k = (n+1), S(k, n, X) is given non-recursively by 2- The horizontal-sweep version: Nodes are visited row-wise, starting from the topmost row (i = S(k, n, X) = Sy(Zn+1, X) = 1, k = 0, n  0, (14b) 1) and ending at the bottom row (i= k). Within each row i, the S(k, n, X) = Sy(φ, X) = 0, k = (n+1), n  0, (14c) algorithm proceeds from left (j = i) to right (j = i+n–k). Since the right hand side of Eq. (14a) is a disjoint sum of 3- The diagonal-sweep version: products of statistically independent expressions, it is a PRE that Nodes are visited diagonal-wise, starting from the leftmost is readily convertible, on a one-to-one basis, into a probability diagonal (j–i = 0) and ending at the rightmost one (j–i = n–k). expression. Hence, the following recursive relation for the Within each diagonal, the algorithm proceeds downwards from reliability of a k-out-of-n:G system is obtained [3, 6] the top row (i = 1) to the bottom row (i = k). R(k, n, p) = qm * R(k, n–1, p/pm) Our efficient algorithm has a local memory requirement of (k+1) (15a) + pm * R(k–1, n–1,p/pm), 1  k  n, scalars. Its temporal complexity is measured by N = k(n–k+1) = R(k, n–1, p/pm) multiplications and 2N additions. In the worst case (k  (n+1)/2), + pm * (R(k–1, n–1, p/pm) – R(k, n–1, p/pm)), (15b) the algorithm has a linear spatial complexity of (n+3)/2 and a 1kn quadratic temporal complexity of (n+1)²/4. There exist "dual" versions of the algorithm that compute the unreliability U(k, n, p) The boundary conditions (14b) and (14c) also translate from the instead of the reliability R(k, n, p) with no change whatsoever in Boolean to the algebraic domain as complexity [3, 6]. The algorithm can be shown to be correct, since when it is given a valid input it produces the right output in R(k, n, p) = 1.0, k = 0, n  0, (15c) a finite amount of time, and also it passes the tests in [65]. To R(k, n, p) = 0.0, k = (n+1), n  0. (15d) date, this algorithm has the least temporal complexity within the class of algorithms that basically use real multiplications and It is possible (though less intuitive) to obtain (15b) directly in additions to compute R(k, n, p). It is believed [6] to be optimal in the probability domain through the application of the pivoting the worst case, in the sense that it is unlikely that there is an (pivotal decomposition or factoring) [64] which is simply a algorithm in the same class that performs fewer basic operations version of the well-known total probability theorem [11]. The in the worst case. unreliability U(k, n, p) satisfies recursive relations similar to (15a) or (15b) and boundary conditions complementary to those The Rushdi algorithm in [3, 4, 6] is the basis for efficient in (15c) and (15d). algorithms that compute the reliabilities of more general systems such as the k-to-ℓ-out-of-n system [26, 27], the threshold system B. An Iterative Algorithm Based on Binary Recursion [30], the combined k-out-of-n:F, consecutive-k-out-of-n:F, and linear Connected-(r; s)-out-of-(m; n):F System [66], and the multi-state k-out-of-n system [29]. The algorithm was Based upon the recursive relation (15b) and boundary conditions successfully applied in the analysis or design of some practical (15c) and (15d) an efficient non-recursive algorithm for real-life systems such as furnace systems [49, 50], and static computing R(k, n, p) and U(k, n, p) has been reported by Rushdi synchronous compensators (STATCOM) used in electric power [3, 4, 6]. This algorithm has a nice pictorial interpretation in systems [67]. It is also applicable in the analysis and design of terms of a SFG generalizing the one in Fig. 3. In fact, if we fleets of aircrafts [68] and systems of pervasive computing [69]. replace the graph transmissions p and q preceding column j by the subscripted symbols pj and qj, respectively, the node (i, j) The Rushdi algorithm in [3, 4, 6] and its extensions for the k-to- represents the unreliability U(i+1, j, p), and if we replace these ℓ -out-of-n system [26, 27] and the threshold system [30] have two graph transmissions by the swapped subscripted symbols qj been rediscovered repeatedly in the literature. The concept of a and pj, respectively, the node (i, j) represents the reliability weighted k-out-of-n:G system in [12, 31] is a special case of that R(i+1, j, p).. The algorithm constructs an array of values of a threshold system in [30]. The recursive relations and the inclusively bounded in the ij-plane by the four straight lines, i = algorithms in [12, 31] are also strongly similar to those in [30]. 1, i = k, i = j, i = (j–n+k), which are the edges of a parallelogram In another direction, Dutuit and Rauzy [10] paraphrased the with corners (i, j) at (1, 1), (k, k), (k, n) and (1,n–k+1). The Rushdi algorithm into an algorithm that they admitted is algorithm has three versions depending on the order of traversing "strongly similar" to the Rushdi algorithm in [3, 4]. They also or sweeping the aforementioned parallelogram elements, paraphrased the extension of the Rushdi algorithm for the k-to- ℓ namely: -out-of-n system [26, 27], and believed that the resulting algorithm is new, obviously unaware of the work in [26, 27]. 1- The vertical-sweep version: 1857-7202/1008007 10 A.M.A. RUSHDI: Partially-Redundant Systems: Examples, Reliability and Life Expectancy The above statements should never be understood to belittle the convolution of two sequences, and hence the evaluation of the visionary insights in [10], which significantly enhanced the product of two generating functions. It is not desirable to utility of switching (Boolean) algebra in reliability evaluations apply the FFT for smaller problems since large overheads are through the prudent use of the highly efficient and extremely involved [7]. The Belfore algorithm is faster than other popular ROBDD data structure [56, 57]. algorithms for n > 4000 [7]. It is very hard to use (compared to the Rushdi algorithm) in manual computations for small-size The Rushdi algorithm in [3, 4, 6] has an elegant technique of systems, and hence does not provide a similar pedagogical handling two-dimensional recursion, reminiscent of the use of insight. Pascal’s triangle in computing combinatorial (binomial) coefficients. This technique is very useful in tackling other Patel et al. [71] has a serious observation about numerical problems of two- or multi-dimensional recursion, such as the algorithms, which they emphasize by calling it a "folk computation of Stirling’s numbers, and the computation of theorem." This so called "theorem" states that "If an algorithm multinomial coefficients and probabilities. is amenable to 'easy' hand calculation, it is probably a poor method if implemented in the finite floating-point arithmetic of a digital computer." The "converse of the folk theorem" states VII. COMPLEXITY ISSUES that "Many algorithms that are now considered fairly reliable The k-out-of-n system has taken a considerably large share of the in the context of finite arithmetic are not amenable to hand reliability literature. Virtually all the major techniques of system calculation." Notable pertinent examples that fully support the reliability analysis have been applied to k-out-of-n systems. The "folk theorem" include formula (7) above for computing the outcome is a potpourri of algorithms that have been surveyed in reliability of a k-out-of-n:G system with equal-reliability [6], where careful attention has been paid to ensure a uniform components, and also formula (10) for computing its treatment of the various algorithms and to point out similarities, normalized life expectancy. Fortunately, the Rushdi algorithm differences and interrelations among them. Notable among these for computing the reliability of a k-out-of-n:G system with algorithms is an algorithm due to Barlow and Heidtmann [2], non-identical components can serve as a "concrete which uses the coefficients in a generating-function expansion to counterexample" for a stronger version of the folk theorem express the probabilities of exactly m successes in n Bernoulli that lacks the qualifying word "probably," and also for a trials, and then employ an efficient technique to obtain their stronger version of the converse theorem in which the qualifying word "Many" is omitted. The Rushdi algorithm is summation for k  m  n. This algorithm has a spatial very nice for hand calculations, and still it is one of the fastest complexity of (k+2) scalars, and a non-symmetric temporal and most reliable and robust methods for digital computations. complexity of ((k+1)*(n–k+1)–1) multiplications plus ((2k+1)*(n–k+1)–1) additions. In the worst case (k  (n+1)/2), VIII. CONCLUDING REMARKS these complexities reduce to (n+5)/2 memory cells and ((n+1)*(n+3)/4–1) multiplications, respectively. This means that the Rushdi algorithm [3, 4, 6] discussed herein has a slight trivial This paper presented a brief tutorial exposition of some recent advantage over the Barlow-Heidtmann algorithm. Both developments in the evaluation of the reliability of partially- algorithms are temporally O(n²/4). They are the best in temporal redundant (k-out-of-n) systems. A novel contribution of the terms (among algorithms using real operations), in addition to paper is that it identified many practical examples in which being good space economizers. The similarity between the two such systems serve as a useful model. Some formulas for the algorithms is so strong that they are sometimes mistaken to be reliability and life expectancy of these systems were discussed the same. To summarize the minor difference between the two in the case of equal-reliability components. Certain celebrated algorithms, we note that the Rushdi algorithm is based on formulas were shown to be numerically unstable and totally explicit recursion related to the Cumulative Distribution useless in the case of large systems with high-reliability Function (CDF) of the generalized binomial distribution. The components. The paper also reviewed how the Boole-Shannon Barlow-Heidtmann algorithm, however, does not use recursion expansion (or equivalently, the pivoting or factoring explicitly, but it has been shown by Rushdi [3, 6] to have technique) is used to derive pertinent recursive relations, implicit recursion, which turns out to be related to the probability leading to a highly efficient algorithm for k-out-of-n reliability mass function ( pmf ) of the same distribution [54, 55]. More evaluation. This algorithm has a nice interpretation in terms of detailed comparisons between these two algorithms are available a regular Mason signal flow graph, which turns out to be (a) a in Rushdi [6], and in Kuo and Zuo [12]. reduced ordered binary decision diagram representing a monotone symmetric switching function, and (b) analogous to In 1995, absolute optimality of the Rushdi algorithm and the the minimal circuit realization of this function. In the worst Barlow-Heidtmann algorithm was lost to a new algorithm by case, the temporal and spatial complexities of this algorithm Belfore [7] which has a temporal complexity O(n(log2n)2). This were shown to be quadratic and linear, respectively, in the algorithm combines the generating-function expansion concept number of system components. The paper listed some [2, 70] with a recursive application of the Fast Fourier extensions and applications of this algorithm and compared it Transform (FTT). The FTT uses complex arithmetic, and with a few related algorithms. In the following, a few involves multiplications by complex roots of unity, which are additional remarks are added. equidistant points on the unit circle in the complex plane. Recursively, the FTT facilitates the computation of the IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 11 For the parallel system, which is totally or fully redundant, [6] Rushdi, A. M., Reliability of k-out-of-n Systems, Chapter 5 in Misra, K. B. (Editor), New Trends in System Reliability Evaluation, Vol. 16, redundancy is always useful in the sense that using several Fundamental Studies in Engineering, Elsevier Science Publishers, components is always better than using a single component. This Amsterdam, The Netherlands, pp. 185-227, 1993. is not the case, however, when strict partial redundancy is used. [7] Belfore, II, L. A., An O(n(log2n)2) Algorithm for Computing the Rushdi and Al-Hindi [46] utilized the Rushdi algorithm in [3, 6] Reliability of k-out-of-n:G & k-to-1-out-of-n:G Systems, IEEE Transactions on Reliability, Vol. 44, No. 1, pp. 132-136, 1995. in computing and tabulating values for the lower boundary of the [8] Barlow, R. E.., and F. Proschan, Mathematical Theory of Reliability, region of useful redundancy for k-out-of-n systems, i.e., the SIAM, New York, NY, USA, 1996. region in which system reliability is better than that of a single [9] Ebeling, C. E., An Introduction to Reliability and Maintainability component. If the components have constant failure rates, their Engineering, McGraw-Hill, New York, NY, USA, 1997. [10] Dutuit, Y. and A. Rauzy, New Insight into the Assessment of k-out-of-n lifetimes are exponentially distributed, and this lower boundary and Related Systems, Reliability Engineering and System Safety, Vol. can be used to determine the point that divides the time axis into 72, No. 2, pp. 303-314, 2001. intervals of short and long missions, respectively [11]. In a [11] Trivedi, K. S. Probability & Statistics with Reliability, Queuing, and different direction, Rushdi and Al-Thubaity [72] modified the Computer Science Applications, 2nd Ed., Prentice-Hall, Englewood Cliffs, NJ, USA, 2002. Rushdi algorithm in [3, 6] to obtain efficient algorithms for [12] Kuo, W., and M. J. Zuo, The k-out-of-n System Model, Chapter 7 in computing the first-order sensitivity of k-out-of-n system Optimal Reliability Modelling: Principles and Applications, Wiley, reliability. These algorithms are useful in computing several New York, NY, USA, pp. 231-280, 2003. criticality or importance measures and in evaluating the [13] Rausand, M., and A. Hoyland, System Reliability Theory: Models, Statistical Methods, and Applications, 2nd Ed., Wiley, Hoboken, NJ, instantaneous failure rate of the system. USA, 2004. [14] Amari, S. V., M. J. Zuo, and G. Dill, O(kn) Algorithms for Analyzing An important problem of interest is to study the characteristics of Repairable and Non-repairable k-out-of-n:G Systems, Chapter 21 in k-out-of-n systems under a set of assumptions other than the one Misra, K. B. (Editor), Handbook of Performability Engineering, Springer, London, UK, pp. 309-320, 2008. employed throughout this paper. Examples of these include k- [15] Heidtmann, K. D., Bounds on Reliability of a Noncoherent System out-of-n systems with statistically dependent components, Using Its Length & Width, IEEE Transactions on Reliability, Vol. R- common-cause failures, two failure modes, repair, or spares. 31, No. 5, pp. 424-427, 1982. Typically, Markov-chain modeling is appropriate and effective [16] Agrawal, A., and R. E. Barlow, A Survey of Network Reliability and Domination Theory, Operations Research, Vol. 32, No. 3, pp. 478-492, in these cases [5, 11, 14, 73]. 1984. [17] Barbara, D. and H. Garcia-Molina, The Reliability of Voting While simple reliability-cost metrics (such as reliability per Mechanisms, IEEE Transactions on Computers, Vol. C-36, No. 10, pp. cost or life expectancy per cost) can be used to guide the 1197-1208, 1987. [18] Kumar, A., Hierarchical Quorum Consensus: A New Algorithm for selection of a system from among several systems that are Managing Replicated Data, IEEE Transactions on Computers, Vol. 40, candidates for providing the same performance in a given No. 9, pp. 996-1004, 1991. mission, other more elaborate metrics (such as the cost [19] Brown, F. M., Boolean Reasoning: The Logic of Boolean Equations, elasticity of reliability or cost elasticity of life expectancy) Kluwer Academic Publishers, Boston, MA, USA, 1990 (2nd Ed. by Dover Publications, Mineola, NY, USA, 2003). have been developed [53] for partially-redundant systems. [20] Wheeler, R. F., Rethinking Mathematical Concepts, Ellis These metrics can be used to assess the cost-benefit aspect of Horwood, Chichester, West Sussex, England, 1981. adding redundancy to a system with the purpose of enhancing [21] Bergman, B., On Reliability Theory and Its Applications (with its reliability. Discussion), Scandinavian Journal of Statistics, Vol. 12, No.1, pp. 1-41, 1985. [22] Kaufmann, A., D. Grouchko, and R. Cruon, Mathematical Methods for Since the tutorial exposition presented herein is somewhat the Study of the Reliability of Systems, Academic Press, New York, NY, brief, the interested reader is invited to pursue the topic further USA, 1977. in the more elaborate surveys available in the literature in the [23] Barlow, R. E., and S. Iyer, Computational Complexity of Systems and the Reliability Polynomial, Probability in Engineering & Information reviews of Rushdi [6], Amari, Zuo, and Dill [14], Kuo and Science, Vol. 2, pp. 461-469, 1988. Zuo [12], Dutuit and Rauzy [10], and Chao, Fu, and Koutras [24] Billinton, R. and Allan, R. N. Reliability Evaluation of Engineering [74]. Systems: Concepts and Techniques, 2nd Ed., Springer, New York, NY, USA, 2005. [25] Papastavridis, S. G., and M. E. Sfakianakis, Optimal-Arrangement & REFERENCES Importance of the Components in a Consecutive-k-out-of-r-from-n:F [1] Boland, P. J., and F. Proschan, The Reliability of k out of n Systems, system, IEEE Transactions on Reliability, Vol. 40, No. 3, pp. 277-279, The Annals of Probability, Vol. 11, No. 3, pp. 760-764, 1983. 1991. [2] Barlow, R. E., and K. D. Heidtmann, Computing k-out-of-n System [26] Rushdi, A. M., Efficient Computation of k-to-ℓ-out-of-n system Reliability, IEEE Transactions on Reliability, Vol. R-33, No. 4, pp. 322- reliability, Reliability Engineering, Vol. 17, pp. 157 -163, 1987, Erratum 323, 1984. : ibid, vol. 19, p. 321, 1987. [3] Rushdi, A. M., Utilization of Symmetric Switching Functions in the [27] Rushdi, A. M., and F. M.-A. Dehlawi, Optimal Computation of k-to-ℓ- Computation of k-out-of-n System Reliability, Microelectronics and out-of-n System Reliability, Microelectronics and Reliability, Vol. 27, Reliability, Vol. 26, No. 5, pp. 973-987, 1986. pp. 875-896, 1987, Erratum : ibid, Vol. 28, p. 671, 1988. [4] Rushdi, A. M. Comment on : An Efficient Non-recursive Algorithm for [28] Upadhyaya, S. J., and H. Pham, Analysis of Noncoherent Systems and Computing the Reliability of k-out-of-n Systems, IEEE Transactions on an Architecture for the Computation of the System Reliability, IEEE Reliability, Vol. 40, No. 1, pp. 60-61, 1991. Transactions on Computers, Vol. 42, No. 4, pp 484-493, 1993. [5] Misra, K. B., Reliability Analysis and Prediction: A Methodology [29] Tian, Z., M. J. Zuo, and R. C. M. Yam, Multi-State k-out-of-n Systems Oriented Treatment, Elsevier Science Publishers, Amsterdam, The and Their Performance Evaluation, IIE Transactions, Vol. 41, No. 1, pp. Netherlands, 1992. 32-44, 2009. 1857-7202/1008007 12 A.M.A. RUSHDI: Partially-Redundant Systems: Examples, Reliability and Life Expectancy [30] Rushdi, A. M., Threshold Systems and Their Reliability, [57] Rauzy, A., Binary Decision Diagrams for Reliability Studies, Chapter 25 Microelectronics and Reliability, vol. 30, No. 2, pp. 299-312, 1990. in Misra, K. B. (Editor), Handbook of Performability Engineering, [31] Wu, J.-S., and R.-J. Chen, An Algorithm for Computing the Reliability Springer, London, UK, pp. 381-396, 2008. of Weighted-k-out-of-n Systems, IEEE Transactions on Reliability, [58] Unger, S. H., The Essence of Logic Circuits, 2nd Ed., IEEE Press, New Vol. 43, No. 2, pp. 327-328, 1994. York, NY, USA, 1997. [32] Rushdi, A. M., A Switching-Algebraic Analysis of Consecutive-k- [59] Heidtmann, K. D., Improved Method of Inclusion-Exclusion Applied to out-of-n:F systems, Microelectronics and Reliability, Vol. 27, pp. 171- k-out-of-n Systems, IEEE Transactions on Reliability, Vol. R-31, No. 1, 174, 1987. pp. 36-40, 1982. [33] Rushdi, A. M., A Switching-Algebraic Analysis of Circular [60] Arulmozhi, G., Direct Method for Reliability Computation of k-out-of-n Consecutive-k-out-of-n:F Systems, Reliability Engineering and System Systems, Applied Mathematics and Computation, Vol. 143, pp. 421-429, Safety, Vol. 21, , pp. 119-127, 1988. 2003. [34] Chang G. J., L. Cui, and F. K. Hwang, Reliabilities for (n, f, k) Systems, [61] Rushdi, A. M., and A. A. Abdul-Ghani, A Comparison Between Statistics & Probability Letters, Vol. 43, pp.237-242, 1999. Reliability Analyses Based Primarily on Disjointness or Statistical [35] Tung, S.S., Combinatorial Analysis in Determining Reliability, Independence, Microelectronics and Reliability, Vol. 33, pp. 965-978, Proceedings of the Annual Reliability and Maintainability Symposium, 1993. pp. 262-266, 1982. [62] Rushdi, A. M., and O. M. Ba-Rukab, A Doubly-Stochastic Fault-Tree [36] Eryilmaz, S., and T. Aksoy, Reliability of Linear (n, f, k) Systems with Assessment of the Probabilities of Security Breaches in Computer Weighted Components, Journal of Systems Science and Systems Systems, Proceedings of the Second Saudi Science Conference, Part Engineering, Vol. 19, No. 3, pp.277-284, 2010. Four: Computer, Mathematics, and Statistics, Jeddah, Saudi Arabia, pp. [37] Bollinger, R. C., Strict Consecutive-k-out-of-n:F Systems, IEEE 1-17, 2004. Transactions on Reliability, Vol. R-34, No. 1, pp. 50-52, 1985. [63] Rushdi, A. M., and O. M. Ba-Rukab, Fault-Tree Modeling of Computer [38] Rushdi, A. M., Effect of Statistical Dependencies in Strict Consecutive- System Security, International Journal of Computer Mathematics, Vol. k-out-of-n:F Systems, Microelectronics and Reliability, Vol. 28, No. 2, 82, No. 7, pp. 805-819, 2005. pp. 309-318, 1988. [64] Page, L. B., and J. E. Perry, Reliability of Directed Networks Using the [39] Rushdi, A. M., A Conditional Probability Treatment of Strict Factoring Theorem, IEEE Transactions on Reliability, Vol. R-38, pp. Consecutive-k-out-of-n:F Systems Microelectronics and Reliability, 556-562, 1989. Vol. 29, No. 3, pp. 581-586, 1989. [65] Rushdi, A. M., How to Hand-Check a Symbolic Reliability [40] Rushdi, A. M., S. G. Papastavridis., R. A. Evans, Some Open Questions Expression, IEEE Transactions on Reliability, Vol. R-32, No. 5, pp. (and Replies) on: Strict Consecutive-k-out-of-n:F Systems, IEEE 402-408, 1983. Transactions on Reliability, Vol. 39, No. 3, pp. 380-381, 1990. [66] Zuo, M. J., D. Lin, and Y. Wu, Reliability Evaluation of Combined k- [41] Hwang, F. K., Comment on Strict Consecutive-k-out-of-n:F Systems, out-of-n:F, Consecutive-k-out-of-n:F, and Linear Connected-(r; s)-out- IEEE Transactions on Reliability, Vol. 40, No. 3, pp. 264, 270, 1991. of-(m; n):F System Structures, IEEE Transactions on Reliability, Vol. [42] Henley, E. J., and H. Kumamoto, Designing for Reliability and Safety 49, No. 1, pp. 99-104. 2000. Control, Prentice-Hall, Englewood Cliffs, NJ, USA, 1985. [67] Lu, Z., and W. Liu, Reliability Evaluation of STATCOM Based on the [43] Parhami, B., Voting Networks, IEEE Transactions on Reliability, Vol. k-out-of-n: G Model, 2006 International Conference on Power System 40, No. 3, pp. 380-394, 1991. Technology (PowerCon 2006), pp. 1-6, 2006. [44] Lin, S., and D. J. Costello, Jr., Error Control Coding: Fundamentals and [68] Cochran, J. K., and T. P. Lewis, Computing Small-Fleet Aircraft Applications, 2nd Ed., Pearson Prentice-Hall, Upper Saddle River, NJ, Availabilities Including Redundancy and Spares, Computers & USA, 2004. Operations Research, Vol. 29, pp. 529-540, 2002. [45] Hwang, K., and T.-P. Chang, Combinatorial Reliability Analysis of [69] Hansen, K. M., and J. Brønsted, Modeling Service Composition Multiprocessor Computers, IEEE Transactions on Reliability, Vol. R- Reliability in Pervasive Computing, Science Institute, University of 31, No. 5, pp. 469-473, 1982. Iceland, Reykjavík, Iceland, Technical report RH-02-2010, 2010. [46] Rushdi, A. M., and K. A. Al-Hindi, A Table for the Lower Boundary of [70] Levitin, G., Universal Generating Function and Its Applications. the Region of Useful Redundancy for k-out-of-n Systems, Springer-Verlag, Berlin, Germany, 2005. Microelectronics and Reliability, Vol. 33, pp. 979-992, 1993. [71] Patel, R. V., A. J. Laub, and P. M. Van Doreen. (Editors), Numerical [47] Rai, S., A. K. Sarje, E. V. Prasad, and A. Kumar, Two Recursive Linear Algebra Techniques for Systems and Control, IEEE Press, New Algorithms for Computing the Reliability of k-out-of-n Systems, IEEE York, NY, USA, 1994. Transactions on Reliability, Vol. R-36, No. 2, pp. 261-265, 1987. [72] Rushdi, A. M. and A. O. Al-Thubaity, Efficient Computation of the [48] Parker, D. S., and C. S. Raghavendra, The Gamma Network, IEEE Sensitivity of k-out-of-n System Reliability, Microelectronics and Transactions On Computers., Vol. C-33, No. 4, pp. 367-372, 1984. Reliability, Vol. 33, pp. 1963-1979, 1993. [49] Zuo, M., S. Chiovellib, and J. Huang, Reliability Evaluation of Furnace [73] Allen, A. O. Probability, Statistics, and Queueing Theory with Systems, Reliability Engineering and System Safety, Vol. 65, pp. 283– Computer Science Applications, 2nd Ed., Academic Press, San Diego, 287, 1999. CA, USA, 1990. [50] Zuo, M.-J., and Y. Wu, Reliability Evaluation of a Furnace System [74] Chao, M.-T., J. C. Fu, and M. V. Koutras, Survey of Reliability Studies Using the k-out-of-n and the consecutive k-out-of-n Reliability Models, of Consecutive-k-out-of-n:F Systems & Related Systems, IEEE Proceedings of the IEEE Conference on Systems, Man, and Transactions on Reliability, Vol. 44, No. 1, pp. 120-127, 1995. Cybernetics,, Vol. 4, pp. 3119-3123, 1996. [51] Shamir, A., How to Share a Secret, Communications of the Association of Computing Machinery, Vol. 22, pp. 612–613, 1979. Ali Muhammad Ali Rushdi was born in Port Said, [52] Smotherman, M., R. M. Geist and K. S. Trivedi, Provably Conservative Egypt, on May 24, 1951. He received the B.Sc. degree Approximations to Complex Reliability Models, IEEE Transactions On (Honors) in Electrical Engineering (Electronics and Computers, Vol. C-35, No. 4, pp. 333-338, 1986. Communications) from Cairo University, Cairo, Egypt, [53] Rushdi, A. M., and A. E. Alsolami, Cost Elasticities of Reliability and in 1974, and the M.S. and Ph.D. degrees in Electrical MTTF for k-out-of-n Systems, Journal of Mathematics and Statistics, Engineering from the University of Illinois at Urbana- Vol. 3, No. 3, pp. 122-128, 2007. Champaign, USA in 1977 and 1980, respectively. He [54] Rushdi, A. M. and Al-Qasimi, A. M., Efficient Computation of the PMF maintained a perfect GPA of 5.0/5.0 throughout his and the CDF of the Generalized Binomial Distribution, Microelectronics study. and Reliability, Vol. 34, pp. 1489-1499, 1994. [55] Al-Qasimi, A. M., and A. M. Rushdi, A Tutorial on How to Efficiently In 1974 he was appointed Demonstrator and Instructor in the Department of Calculate and Format Tables of the Binomial Distribution, Journal of Electronics and Electrical Communications Engineering of Cairo University. King Abdul-Aziz University: Engineering Sciences, Vol. 19, No. 1, pp. From 1976 to 1980 he was Research Assistant in the Electrical Engineering 3-17, 2008. Department of the University of Illinois at Urbana-Champaign. Since 1980 he [56] Bryant, R., Graph-Based Algorithms for Boolean Function has been with King Abdul-Aziz University in Jeddah, Saudi Arabia, where he Manipulation, IEEE Transactions on Computers, Vol. 35, No. 8, pp. is now Professor of Electrical and Computer Engineering as well as Head and 677-691, 1986. Coordinator of the Computer Engineering Group. At King Abdul-Aziz IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 13 University he has structured and taught a variety of graduate and undergraduate courses, supervised master theses and senior projects, and contributed significantly to accreditation activities. He served as a member of the Editorial Board of the IEEE Transactions on Instrumentation and Measurements (1986-1994), and was a frequent reviewer for the IEEE Transactions on Reliability (1983-1998). He is currently a member of the Editorial Board of the Journal of King Abdul-Aziz University: Engineering Sciences, and is an Associate Editor of Reliability and Computer Engineering for the International Magazine on Advances in Computer Science and Telecommunications (IMACST). His Research Interests and publications over the past four decades spanned the areas of Electromagnetic Communications Engineering, Computer Engineering, Reliability Engineering, Digital Design, Engineering Education, Neural and Switching Networks, Advanced Mathematics, Boolean Algebra and Logic, Engineering Design, Inferential Thinking, and Problem Solving. Prof. Rushdi is an initiated member of the Honorary Societies: Eta Kappa Nu and Phi kappa Phi. He is a Senior Member of the Institute of Electrical and Electronics Engineers (IEEE). 1857-7202/1008007 IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 15 Cellular Network Faults and Services Dependency Modeling Okuthe P. Kogeda and Johnson I. Agbinya  B. Definition of Services and Applications Abstract— Cellular network services depend on one or more resources and a resource can be used by one or more services. The ITU-T defines telecommunication services as follows Network faults can affect these resources and hinder them from [1]: A service represents telecommunication capabilities that supporting services that depend on them. It is therefore necessary the customer buys or leases from a service provider. A service to react accurately to faults occurring in one or more components is an abstraction of the network-element-oriented or that provide such resources to ensure high quality of service equipment-oriented view. Identical services can be provided provision. This can be achieved by determining the dependencies by different network elements, and different services can be between different services, dependencies between services and provided by the same network element. A set of functions and resources and dependencies on the resource level. In this paper, we present the basics, types, benefits, life cycle of service facilities offered to a user by a provider is known as service. dependency. We also present service dependency models in a One service can serve several consumers and a server is dynamically changing environment like cellular networks. The always its execution environment. simulation results showing 99.95% dependency are presented in An application on the other hand is used as the generic term this paper. that represents a set of features, combining communication Index Terms— Network services, Operations Support System, and document processing, on which end users may perform Network service dependency, Network faults, Dependency types, operations. Applications may depend on working methods, Simulation, Dependency dynamics, Dependency life cycle, and on allowed processing of documents. Open interchange of Dependency binding, Availability. process-able documents and co-operative working are examples of applications [1]. An application is a program that a user directly interacts with. An application utilizes services I. INTRODUCTION and might incorporate modules to fulfill its tasks. The application is not restricted to a special environment to run in. I nternet explosion, increasing number of services on offer and subscribers has put a lot of pressure on the cellular network service providers. The networks are loaded with C. Characteristics of Cellular Network Services Cellular network services are tricky entities that do not have different kinds of subscribers having different tastes and specific characteristics that apply to all of them. Different needs. This requires that the operation of the network be at its cellular network services possess different features that best all the times not only to keep the subscribers happy but preserve the identity of each cellular network service. also to retain them and attract new ones. This can be achieved However, there are a few features that most cellular network with proper maintenance of the network itself. services have in common. These include: services can use one or more media of transmission; most services being offered by A. Network Services cellular service providers are easily programmable and Network service is a crucial and very important resource in flexible to the needs of customers; most services are easily a cellular network system. For any cellular network service accessible with cost and legal permission to use them; cellular provider to retain and acquire new subscribers, services on network services are randomly initiated and executed. offer must be general, cost effective, fair robust, reliable and have high performance connectivity among a large number of D. Classification of Network Services communication devices (i.e., computers, wireless terminals, A set of applications with similar or common set of etc), for the highest customer satisfaction. characteristics (cf. Section I C) can be classified as a service. Generally cellular network services can be classified into data, voice and multimedia according to ITU-T I.211 [1]. Network services in digital form are called data. Network services in ‘vocal chord’ form are called voice and are regarded as the Manuscript received September 1, 2010. This work was supported in part oldest cluster of network services. However, the latest type of by the National Research Foundation (NRF), South Africa. Okuthe P. Kogeda is currently working in Computer Science Department network services, which are normally composed of pictures, as Senior Lecturer, University of Fort Hare, Private Bag X1314, Alice 5700, videos, text and/or sound are called multimedia. Multimedia Republic of South Africa. (Email :

) services consume a lot of bandwidth and require powerful Johnson I. Agbinya, is working at Center for Real-time Information devices to process (receive and send) them. Fig. 1 shows Networks (CRIN), Faculty of Engineering, University of Technology, Sydney, NSW 2007, Australia. (Email:

). classes of network services with examples. 1857-7202/1008012 16 O.P.Kogeda, J.I.Agbinya: Cellular Network Faults and Services Dependency Modeling tracked using building, service and/or geographical location. Then offer new services to increase sales and profitability. Maintain - Property managers are notified of lease, insurance expiry dates, up to date contact information, site documentation, Service Level Agreement (SLA) details and payment schedule. Then ensure that emergency contacts are up-to-date and readily available to Operations Support System (OSS) group. F. Network Resource “A network resource is any physical or virtual component of limited availability within a networked computer system. Every device connected to a computer system is a resource. Every internal system component is a resource. Virtual system resources include files, network connections and memory areas.” [2] Fig. 1. Classes of Cellular Network Services Network resources can also be referred to as various parts of the network (hardware and software) which support each E. Service Life-cycle other by combining or individually to provide specific Network services go through various defined stages, which functions within the network environment. Network service is start with planning, signing (analyse) before one can start the created by these functions. provision of the service, which may encounter errors during Network resources are network elements that support this period and such errors must be corrected. The service can services. A network resource can be basic or elementary. A be maintained till it requires a major improvement. Then the basic network resource is the smallest element that supports a process starts again from plan, sign, provision and network service. It is scalar in nature and cannot be split maintenance, hence network service life cycle as shown in further down. It supports the service with all its parts as a Fig. 2 below. whole. A combination of two or more basic network resources to offer a function to a service is called elementary network resource. An elementary network resource cannot be used without any of the basic element parts. This paper is organised as follows: In Section II, we give a brief overview of Cellular network service dependency and related work. We present types of network service dependencies in Section III. In Section IV, benefits of network service dependency modelling is discussed. Dynamics and network dependency life-cycle is presented in Section V. In Section VI, cellular network service dependency models are presented. In Section VII, simulation results are provided and then we draw conclusion in the subsequent section. II. CELLULAR NETWORK SERVICE DEPENDENCY Fig. 2. Cellular Network Service Life-cycle Dependency provides a very interesting relationship The stages of service life cycle are: between two or more components or services in cellular network environment. The consumer/provider relationship Plan - This is the first stage and this is where the target sites between different entities in a cellular network system is are identified in market penetration plan with the actual versus called dependency. When one component requires a service planned implementation success being measured. Then the performed by another component in order for it to execute its results are reported, which can be according to region, city or functions, this relationship between the two components is sales representatives. called a dependency. For example, a voice service depends on Sign - The rent rates are analyzed by geographic region to a cell where it is located for network signal and the database establish pricing benchmarks before negotiating site for billing purposes before a call is initiated. In turn these arrangements with landlords and property managers. Then the services depend on availability of power supply. In this case a agreement is signed with track of all information about leases, voice service is the dependent and cell and database are the buildings, facilities and contacts. antecedent. Consequently, cell and database are the dependents and power is the antecedent. This relationship is Provision - Network services are built and implemented into shown in Fig. 3. Services cannot be considered isolated tasks. signed buildings. Construction can be managed and status Services largely depend on other services or sub-services, IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 17 lower level network elements, operating systems, physical III. TYPES OF SERVICE DEPENDENCY components and communication infrastructure to be able to The main types of service dependency include [3], [6], [10]: function. Execution dependency – This dependency relates directly to an Network service dependency has attracted several application server process being executed on a host machine. researchers with different viewpoints. Ensel [3] presents a The performance of an application server process depends on scalable service dependency. The author used neural networks the status of the host machine. The types of application for dependency detection modeling. Cervantes et al [4] present servers that are executed on host machines include web, email, a mechanism to automate service dependency management in news, DNS, and NFS. a service-oriented component model. The mechanism they used eliminates complex and error-prone code from Link dependency – performance of a service depends on the component-based applications dynamically. link status. For example, communication between two nodes, A and B, may solely depend on the link between them AB. Gruschke [5] proposed dependency graph for event correlation where dependency was described as a relationship Component dependency – in case of a web service that is between different entities. A generic approach proposed here provided on different front-end servers, which are selected by could be used for different abstraction levels (i.e., system a round-robin DNS scheduling of performance, depends on the level, network level, service level). Caswell et al [6] describe currently selected server. A component dependency occurs in dependencies for services with specific reference to Internet order to ensure scalability and redundancy of a service. ISPs Service Providers. They went further by defining five types of often replicate web, email, and news content across a number dependencies (c.f. Section III). Gupta et al [7] present analysis of servers. The round robin scheduling balances the load of temporal relationships of interactions to derive among the servers. The servers are grouped together and dependencies. assigned a single domain name in the DNS database. When Natu et al [8] proposed a fault diagnosis architecture and the DNS server receives a request for the domain name, the IP algorithm that capture the dynamically changing dependencies address of one of the servers is acquired in the round-robin in mobile ad-hoc networks. They introduced a temporal scheme. correlation algorithm that performs fault diagnosis with Inter-service dependency – It occurs when one service dynamically changing dependency information. Bahl et al [9] accesses another service for its proper operation. This occurs present localization of the sources of performance problems in between services, i.e., e-mail service depends on an large enterprise networks using Inference Graph model. They authentication service and on an NFS service; a web service developed Sherlock system to discover Inference Graphs in depends on DNS service to allow the subscriber to connect the the operational enterprise, infer critical attributes, and then web server host using its IP address, and an NFS service is leverage the result to automatically detect and localize used to access the web content. problems. Organizational dependency – This dependency occurs when there are different ISP operations personnel (e.g., experts) who are responsible for different services and service components. For example, an ISP may have a first supervisor managing the web service, a second supervisor managing DNS, and a third supervisor managing NFS. Operational responsibilities may also be delegated based upon the geographical location of the service components. The first three dependencies are grouped and referred to as resource dependency. In this case the service being offered depends on the resources (i.e., execution, link, component, and/or another service) available at the time. These resources in turn are affected by the cellular network faults, i.e., faults may degrade, reduce or totally take away the resources available to a service. Fig. 3. Examples of (Voice) Service Dependency IV. BENEFITS OF SERVICE DEPENDENCY However, the approaches presented by various authors as discussed above may not predict which service would be The main benefits of dependency modeling include [3]: affected by a fault in dynamically changing networks. In this Root cause analysis – it helps to find a common (root) cause work, an approach of dynamic dependency is used to pre-empt of faults detected at different places within the cellular the likely services that a likely fault would affect at a network environment. This can be used on network particular time. While some of the approaches above cannot components reporting error conditions as well as to services, be implemented, the approach adopted in this work can be where end users detect problems. The faults that are normally implemented backed with mathematical support. reported to the management systems are descriptions of the 1857-7202/1008012 18 O.P.Kogeda, J.I.Agbinya: Cellular Network Faults and Services Dependency Modeling symptoms. Therefore further knowledge about dependencies V. DYNAMICS AND DEPENDENCY LIFE-CYCLE among the faults is necessary to derive their root cause. A. Cellular Network Service Dependency Dynamics Determination of availability requirements on services. To Cellular network service dependency changes as variables minimize the time for resolving network faults. within the cellular network setup changes. The changes are Prediction of the impacts on other services due to normally caused by resources (network components, services, management operations. This is of particular interest when a power, etc) becoming unavailable due to network faults, resource goes down (i.e., due to planned downtime for repairs) resources may migrate, or may be upgraded. In a cellular then it can be determined in real-time which services and network, the components and/or managed objects that represent the resources may be many. The change of customers would be affected. dependency that may occur as a result of fault in a cellular It can be the basis of scheduling tasks and transactions. The network is termed as cellular network dependency dynamics. service dependency provides a detailed task structures, which Cellular network services can be modeled as node, enables better coordination of services. It can be used to communication and precedence constraints between services recognize service misuse and for intrusion detection. as directed edge and the model can be expressed as a Directed Acyclic Graph (DAG). Let the service be S, S  {s1 , s 2 , s 3 ,..., s N } . A complex cellular network system may offer N number of services. A service depends on resource(s) R, where R  {r1 , r2 , r3 ,..., r j } . A resource can be network link, component, or other services. An edge between two services, S a and S b is given by S ab , which expresses the dependent relation between S a and S b . Given service S N the set of parent services is denoted as pred ( S N ) , and the set of children services is denoted as succ( S N ) . A service S N is called entry service if Fig. 4. Model of Network Environment Showing dependency | pred ( S N ) | 0 and an exit service if | succ( S N ) | 0 . In order to drive the problem solving process, that is, Therefore N services depend on R heterogeneous resources. It cellular network faults prediction, a model of cellular network is essential to map the set of N services in the DAG into R faults, or a concept of services and dependencies between heterogeneous available resources in order to avoid the faulty them is required. A cellular network service can be defined as components supporting the resources required by the services. a set of functionalities, which are offered by a cellular network In explaining the cellular network dependency dynamics, service provider to a customer at a customer provider interface the dependency relation between S a and S b may change, for (i.e., mobile handset) with an agreed quality of service. A service can depend on one or more resources and a resource example, if S b malfunctions then S a (will also fail in normal can be used by one or more services. To ensure that high circumstances) but in this case S a may use another service quality of services is provided, it is necessary to react accurately to faults occurring in one or more components that say S k , which offers the same resources for its operation. provide such resources. This can be achieved by determining Also if S a depends on a particular route (link) Rl then with the dependencies between different services, dependencies between services and resources and dependencies on the the failure of Rl , S a is also expected to fail. But this may not resource level. It will be better also to bring to clarity what an be the case because S a may use another route to complete the interface and a component stand for. A component is a non- execution. trivial, nearly independent, and replaceable part of a cellular network system that fulfils a clear function in the context of a The system implementation takes into consideration this well-defined architecture. A component conforms to and dependency dynamics with the cellular network system. It provides the physical realization of a set of interfaces. An therefore means that the dependency models presented in this interface is a collection of operations that are used to specify a paper are dynamic in nature and robust. For a system to fail, it service of a component. It focuses upon the behaviour, not the means all the alternative dependencies are exhausted. The structure of a given service. Fig. 4 shows a model of cellular main causes of dependency dynamics include: cellular network environment showing dependency. network faults, which may cause the cellular network resources to appear and disappear during the system lifetime; deployment of new sub-systems; change of resource availability; re-negotiation of new service level agreements, etc. IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 19 However, it is worth noting that most of the dependencies Table I: Different Types of Dependency Binding are fairly permanent and only change when there is deemed Binding Type Semantics of the dependency type fault with one of the main antecedent. This is the main interest in studying how cellular network faults may change the One-to-One, A service is bound to one resource, any dependency and its subsequent effects on the reliability of the static change invalidates the service. cellular network services. B. Cellular Network Dependency Binding One-to-One, A service is bound to one resource; In exploring network dependency binding, we define the three dynamic changes do not invalidate the service as main variables used. These variables are: long as it can be bound to another resource.  faults, F where F  { f 1 , f 2 , f 3 ,..., f i } , One-to-Many, A service is bound to at least one  resources, R, where R  {r1 , r2 , r3 ,..., r j } , and static resource, any change invalidates the service.  services, S, where S  {s1 , s 2 , s 3 ,..., s N } . One-to-Many, A service is bound to at least one The variables relate to each other depicting the relationship dynamic resource; changes do not invalidate the between them, which can be one-to-one, one-to-many and service as long as the binding count is many-to-many. The dependency only exists when cardinality not zero. between dependent and antecedent is exactly one. The maximum cardinality between the objects is infinity. The Many-to-Many, A set of services are bound to a set of relationship between the variables can take either of the static available resources at the time of following two sets: binding, changes invalidates the (a) The network faults relates to resources directly as follows: services. (i) A set of faults can affect a set of resources in the network, F  R Many-to-Many, A set of services are bound to a set of all dynamic available resources at the time of (ii) A set of faults can affect one or a particular resource binding, as resources become in the network, F  r j available/unavailable they are (iii) One or a particular fault can affect a set of resources bound/unbound to/from the services, the in the network, f i  R services never becomes invalid. (iv) One or a particular fault can affect one or a particular C. Cellular Network Service Dependency Life-Cycle resource in the network, f i  r j Cellular network environment is very dynamic in nature and (b) The network services depend on network resources so the dependency evolving through five phases, referred to as directly as follows: dependency lifecycle. The phases include: (i) A set of services depend on a set of resources in the 1) Initiate: This is the initial phase where the network, R  S dependency is initiated when service consumption is (ii) A set of services depend on one or a particular resource signaled. The initial parameter values are received at in the network, r j  S this stage. For example, when you initiate a call, first (iii) One or a particular service depends on a set of the signal is acquired to have connection to the MSC, and then database connection is initiated to establish resources in the network, R  s N whether you have enough units to continue with the (iv) One or a particular service depends on one or a service consumption. particular resource in the network, r j  s N 2) Acquire: existing services, resources, and common (known) faults are acquired by the dependency for A binding which can be static or dynamic would occur with mapping purposes at this stage. New and old the knowledge of cardinality. A static binding is where the dependencies are ascertained mainly for consumption dependency bindings cannot change at run time and the dependent service is guaranteed to be present the entire time purposes, i.e., after service, S a signaled the resource is available, whereas dynamic binding is where service, S k for dependency and received positive the dependency bindings can change at run time and service availability cannot be guaranteed. Network services would be answer, then it acquires the resources in readiness for affected differently by different types of bindings as the dependency mapping to complete the service summarized in Table I: consumption through S ak . 3) Start Map: This stage triggers the start of dependency mapping. 1857-7202/1008012 20 O.P.Kogeda, J.I.Agbinya: Cellular Network Faults and Services Dependency Modeling 4) Map: new resources may be added to the dependency Table II: Summary of faults, resources, and services correspondingly pool during this phase. Existing resources and Faults Resources Common Services dependency parameters may be removed or updated to ensure the dependency dynamics are maintained. Multiplexer Link (lines), electrical Voice, VoIP, Dependency mapping can be affected by these power, Multiplexer Videoconferencing, etc changes, and so must be resolved continuously for a adaptor, External Bus Interface (EBI) cable, robust cellular network system. conversion kit, port 5) Stop: The dependency is terminated at this stage. module, etc The dependency life cycle continues by initiating another dependency. The semantics of the dependency are Power Generator, Electrical SMS, MMS, Voice, implemented in the system, which correlates the services to power sources, VoIP, Email, etc. Electrical switches, Virtually all services are faults. The service dependency life cycle is shown in Fig. 5. transmission lines, etc affected. Transmission Link, cables, Affect real-time services multiplexer, network name resolution, ISDN Affects services in a switches, ISDN lines, serial connection Gateways, etc May delay services such Fig. 5. Dependency Life-cycle as SMSs, etc VI. CELLULAR NETWORK DEPENDENCY MODELS Cell Link, Electrical power, VoIP, SMS, MMS, A cellular network environment can be logically modeled as cables, multiplexer, etc Email, Internet, Video layers of resources (i.e., services, applications and other conferencing, etc software and hardware components) that cooperate to deliver an end-to-end service. Services or components in one layer Time Out Link, RAM, SMS, MMS, Email, multiplexer, etc VoIP, Video depend on functions provided by components in a lower- conferencing, etc supporting layer. Failures occurring in one layer affect the functioning of dependent components in another layer. The Run Time Error RAM, Link, Switches, VoIP, voice, Video dynamics of service dependency are considered for cellular etc conferencing, etc network faults prediction purposes, because significant changes in the overall system behaviour are detected through Out of Range Signals, wireless Voice, VoIP, email, emerging or disappearing dependencies. In addition to the access point, Internet, SMS, MMS, etc etc discussion in Section I F above, network resources are important components in service dependency modeling. The combined availability is a product of the availability of Network elements (resources) support services through all the network parts involved. This can be defined as: Service Access Points (SAP) and port accesses. The services dependency is modeled keeping in mind the current changes SA  S ( s ) * N ( s ) * L( s ) * Sw( s) * D( s) (1) happening to the network environment to proactively detect faults before they impact end users. A ontology is Where SA – Service Availability implemented in the system which facilitates the mapping of faults and services to list faults that are likely to cause services S (s) – Availability of service source failure. Table II below summarizes the list of faults, resources and services correspondingly. N (s ) – Availability of network A. Network service availability models L(s ) – Availability of link One of the main aims of this work is to develop a reliable service based Operations Support System (OSS) where Sw(s) – Availability of software services would be available to users whenever they want to consume them. Availability of network services depends on D(s ) – Availability of destination device availability of network resources to support them to carry out Equation (1) also means that the combined availability of the their functions. For example, an end-to-end service availability network is always lower than the availability of its individual would depend on availability of service source, network, link, components (resources). It is important to note that when and availability of the destination device. Network service network is available, the services being offered will also be availability is a combined availability of the network parts available and vice-versa. Therefore, network availability (elements) supporting the service(s). directly impacts on service availability. Simply put, NA  RA  SA where p( F )  0 (2) Where NA – Network Availability IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 21 RA – Resource availability any r  R , the equation r   ( x ) has a solution x  R . The SA – Service availability affects on network resources are transferred to network services with the function: p( F )  0 - is a probability of fault occurrence is 0 w: R  S (9) indicating fault-free network The composition of  and w is the function The network availability at time, t for network service, s may be defined in terms of several parameters that includes  w: F  S (10) network reliability R (t , s ) , network maintainability Equation (10) is defined by M (t ) and fault effects F (t ) where, (  w)( f )   ( w( f )) for all f F (11) NA(t , s )  R(t , s )  F (t , s ) * M (t , s ) (3) VII. SIMULATION RESULTS Where F (t , s)  1  R(t , s) (4) In this Section, we use a case study of network voice However, the network reliability depends upon the reliability service with a number of assumptions made during of many components that make up the network; i.e., network computation. Software availability was assumed to be 100%, link, power, software, switches, and services. These set of other network faults were not considered except power fault, components (resources) can be represented etc. Source availability, network availability, link availability, by R  (r1 , r2 , r3 ,..., r j ) . Rewriting Equation (4) to know software availability, and destination device availability are 0.9958, 0.2343, 0.7737, 1.0, and 0.9958 respectively. We used faults effects at time t, for service s, is Equation 1 to compute Service Availability (SA) and obtained 17.982%. Network availability (NA) was computed using F (t , s )  1  ( R(t , s )) j (5) Equation 3 and a value of 70.62% was obtained. A given set of resources consisting of R members can be However, according to Equation (2), service availability is constructed with R (  1,2,3,..., j ) homogenous sub- supposed to be equals to network availability. This is not the case here and it can be attributed to assumptions made, populations. network fault’s impact and other factors which are beyond the j scope of this work.   R 1 R (6) Network faults effects on network services at time t is given by Equation (5). The value of 99.95% shows that network A homogenous sub-population R is defined by the verifiable faults directly affect network services. The margin of 0.05% can be attributed to noise. assumption that its members exhibit the same probabilistic decision behaviour. However, these set of resources are The utility of network service (in this case voice) improves affected by faults. Network faults are errors that occur with the reduction of network fault (in this case power) frequently within the network elements impairing their occurrence. Network faults occurrence [11, 12, 13] and operations. They may render the network elements unusable or network service utility matched at the 100th iteration. This partially working thereby diminishing partly or wholly the point is called acceptance point as shown in Fig. 6. resources ability to carry out its functions depending on the faults impact. A set of network faults F  ( f 1 , f 2 , f 3 ,..., f i ) , can affect the network resources, R:  :F R (7) Where the domain  is the set F, the target of  is the set R The range or image of  , written rng  , is rng  {r  R | ( f , r )   for some f  F}  {r  R | r   ( f ) for some f  F } (8) Therefore the function has its range of resources as the target of network faults given by rng  R; that is every r  R is Fig. 6. Network service vs Network faults dependency of the form r   ( f ) for some r  R . Equivalently for 1857-7202/1008012 22 O.P.Kogeda, J.I.Agbinya: Cellular Network Faults and Services Dependency Modeling VIII. CONCLUSION Dr. Okuthe P. Kogeda was The basics of network services delving on characteristics, born in Kisumu, Kenya. He classification and life cycle are provided in this paper. In our obtained a doctorate degree in previous publication, we provided the classification and Computer Science from University of the Western Cape models of network faults prediction using Mobile Intelligent in Cape Town, South Africa in Agents (MIA) [11], [12], [13], which are used to derive the 2009. He obtained Master of dependency presented in the paper. The basics, types and Computer Application from Dr. benefits of network service dependency were presented. The Babasaheb Ambedkar Marathwada University in dynamics and dependency life cycle were presented. Network Aurangabad, India in 1999. His service dependency models are presented with simulation main areas of interest include: results showing network services dependent on network faults. Biologically inspired modelling The value of 99.95% dependability of network services on & simulation, Bayesian networks, Cellular networks & OSS, Mobile Intelligent Agents and Data mining. He is currently a Senior Lecturer in the network faults. The paper gave an insight on the relationship Computer Science Department at University of Fort Hare, South Africa. He between network faults and network services. was Lecturer in the Computer Science Department at University of the Western Cape in Cape Town, South Africa from 2004 to 2009. He was a Lecturer at University of Nairobi in Nairobi, Kenya from 1999 to 2000. He REFERENCES has published over 15 internationally refereed conference and journal papers [1] ITU-T Recommendation I.211, “B-ISDN Services Aspects,” Geneva, and author of a book Chapter in Cellular Networks book. Switzerland, 1993. [2] S.V. Kartalopoulos, “A Global Multi-Satellite Network for Multi-Media Dr Johnson I Agbinya holds a doctorate degree from La Trobe University in and PCS Service with Fault and Disaster Avoidance Characteristics, ICC Melbourne, Australia. He is an Adjunct Professor of Computer Science at the (2), pp.694-698, 1997. University of the Western [3] Christian Ensel, “A Scalable Approach to Automated Service Cape, Cape Town, South Dependency Modeling in Heterogeneous Environments”, Proc. 5th Africa and a Senior Lecturer International Enterprise Distributed Object Computing Conference, at the University of pp.128, September 04-07, 2001. Technology Sydney. He was [4] Humberto Cervantes and Richard S. Hall, “Autonomous Adaptation to a Principal Engineer at Dynamic Availability Using a Service-Oriented Component Model”, Vodafone Australia from ICSE, pp.614-623, 2004. 2000 to 2003 and a Senior [5] B. Gruschke, “Integrated event management: Event correlation using Research Scientist at CSIRO dependency graphs” Proc. 9th IFIP/IEEE International Workshop on from 1993 to 2000. His areas Distributed Systems: Operations & Management (DSOM 98), pp.130- of research interests are 141, October 1998. personal area networks, [6] D. Caswell and S. Ramanathan, “Using service models for management networks on mobile of Internet Services”, In HP Technical Report HPL-1999-43, HP platforms and in uncovered Laboratories, Palo Alto, California, USA, March 1999. areas, ultra wideband [7] M. Gupta, A. Neogi, M. Agarwal, and G. Kar, “Discovering Dynamic communication, wireless communication networks, mobile network design, Dependencies in Enterprise Environments for Problem Determination” wireless access methods, air interface, planning, mobility and moving wireless Lecture Notes in Computer Science, Vol. 2867, Springer Berlin, pp.125- networks. He also has extensive experience in DSP, signal processing and 166, 2003. biometrics. He has published over 80 internationally refereed conference and [8] Maitreya Natu and Adarshpal S. Sethi, "Using temporal correlation for journal publications, numerous confidentially research reports (CSIRO) and fault localization in dynamically changing networks", International author of a couple of internetworking books. Journal of Network Management, Volume 18 , Issue 4 (August 2008), Pages: 301-314, ISSN:1099-1190. [9] Paramvir Bahl, Ranveer Chandra, Albert Greenberg, Srikanth Kandula, David A. Maltz and Ming Zhang, "Towards highly reliable enterprise network services via inference of multi-level dependencies" Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, Kyoto, Japan, Pages: 13 - 24, ISBN:978-1-59593-713-1. [10] Andreas Hanemann, David Schmitz, Martin Sailer, “A Framework for Failure Impact Analysis and Recovery with Respect to Service Level Agreements”, Proc. of IEEE International Conference on Services Computing, Vol.2, pp.49-58, 2005. [11] Okuthe P. Kogeda, Johnson I Agbinya, and Christian W. Omlin, "A Probabilistic Approach To Faults Prediction in Cellular Networks", In the Proceedings of the 5th International Conference on Networking (ICN2006), Mauritius, April 23 - 28, 2006, ISBN: 0-7695-2570-9. [12] Okuthe P. Kogeda and Johnson I. Agbinya, “Proactive Cellular Network Faults Prediction Through Mobile Intelligent Agent Technology”, In the Proceedings of the 2nd International Conference on Wireless Broadband and Ultra Wideband Communications (AusWireless 2007), Sydney, Australia, 27-30 August 2007. ISBN: 978-0-7695-2846-5. [13] Okuthe P. Kogeda and Simbarashe Nyika, “Automating Cellular Network Faults Prediction Using Mobile Intelligent Agents”, In the proceedings of IEEE 5th International joint conference on INC, IMS and IDC, August 25-27 2009, Soul, South Korea, pp. 1804 -1810, ISBN: 978-0-7695-3769-6. IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 23 A Mathematical Model of DNA Replication Ahmad A. Rushdi Abstract—DNA replication is a fundamental process for cell Information Information Transmitter Destination Receiver proliferation in humans and other living organisms. It involves Source transfer of genetic information from the original DNA molecule Channel into two copies. Understanding this process is of great importance towards unveiling the underlying mechanisms that control genetic information transfer between generations. In this interdisci- plinary work, we address this process by modeling it as a data Data Transmitted Received Recovered communication channel, denoted: the genetic replication channel. Stream Signal Signal Stream A novel formula for the capacity of this channel is derived, and an Noise example of a symmetric replication channel is studied. Rigorous Source deduction of the channel flow capacity in DNA replication secures more accurate understanding of the behavior of different DNA segments from various organisms, and opens for new horizons Fig. 1. Block diagram of a basic communication system. of engineering applications in genetics and bioinformatics. Index Terms—Communication Channels, Communication Sys- tems, DNA Replication, Mathematical Modeling. the receiver’s function is to reverse every process the original data stream had to go through, either intentionally by the transmitter, or unintentionally due to the channel I. I NTRODUCTION conditions. Finally, the receiver delivers the recovered stream NE of the most important questions which arises in to the information destination which is the intended target O the design process of an information transmission link or processing system is: what is the capacity of this by the data transaction process. Figure 1 summarizes the aforementioned steps. link or system? In other words, in a given time frame, how much information can this link or system carry or Shannon has also introduced a number of new concepts process efficiently? In specific, this question is of great through his proposed model that we define briefly as follows. importance in modern digital communication systems and The first concept is the entropy; which is a measure of has been addressed by several researchers over the past the amount of uncertainty regarding the value of a random few decades. In fact, a mathematical model that tackled variable. For transmitted information message, entropy would this question successfully was first proposed in 1948 by be an indicator of how uncertain the receiver was about C. E. Shannon [1]. In his work, Shannon introduced an the contents of that message, or alternatively, how much operational framework to establish a well defined model information was carried by that message. Hence, entropy is for wireless communication channels. This generic model typically measured in units of information (e.g. bits). The starts with an information source that produces a data stream second concept is the mutual information; which is a measure composed of elements picked from a fixed alphabet. The of the mutual dependence between two random variables, most simple stream is the binary stream composed of bits measured in units of information (e.g. bits). For the context of that belong to the mathematical group F = {0, 1}, which information communications, the mutual information between is the basis for modern digital communication systems. a transmitted signal and a received one measures how much The data stream then passes through a transmitter that knowing what the received signal is reduces our uncertainty subsequently modulates it and encodes it to form the about the transmitted version. The last and probably most transmitted signal. The transmitted signal, in turn, propagates crucial concept in Shannon’s work is the channel capacity; through a communication channel until it is delivered to the defined to be the tightest upper bound on the amount of target receiver. The modulation and coding schemes are to be information that can be reliably transferred through the chosen carefully to secure the transmitted signal’s propagation channel, and is typically measured in units of information per capability and overcome the channel distortion effects. Many unit time (e.g. bits/sec). noise sources can impact the transmitted signal including additive white Gaussian noise (AWGN) and multipath fading. From an application point of view, Shannon’s model first Upon receiving the transmitted signal, mixed with noise, came in service to represent communication channels. the receiver is responsible for several procedures including However, it was easily extended to other communication noise cancellation, decoding, and demodulation. Basically, related procedures and systems including cryptography, Manuscript received August 31, 2010. coding, information security, and encryption [2]. Furthermore, Accepted November 02, 2010. it was applied to the analysis of non-electrical communication A. A. Rushdi can be reached at P.O. Box 5542, Santa Clara CA, 95056 systems such as human communications [3]–[9] and USA, (e-mail:

). even animal communications [10]. Due to the simplicity 1857-7202/1008011 24 A.A. RUSHD,: A mathematical model of DNA replication and mathematical rigorousness of this model, it grew Noisy vigorously into new areas that are not directly related Transmitter Receiver Channel to data communications, including the fields of finance and investment [11]–[14], gambling [15]–[18], seismic exploration [19], the study of black holes [20], and most Transmitted signal X Received Signal Y recently, Genetics. On the last front, many signal processing algorithms were proposed to break down and model Fig. 2. A simplified version of the block diagram in figure 1. complex genetic interactions. These contributions paved the road for new interdisciplinary scientific fields such as bioinformatics, molecular information theory, and genomic procedures to secure a safe trip for the message through signal processing [21]–[25]. noisy channel conditions. These procedures include amplitude, phase, or frequency modulation and source/channel coding. The Deoxyribonucleic acid (DNA) molecules are simply The receiver collects the received signal and reverses the long-term memory storage cells that contain all genetic transmitter’s known effects as well as the channel’s unknown information and replication instructions needed for human effects, in order to recover the original information message. proliferation [26]. Finding the amount of information In the following discussions, we refer to the communication embedded or encoded in DNA molecules, the coding system system model of figure 2 which is a simplified version of used, and the natural mechanism of data replication and figure 1, where the transmitted signal is denoted X and the transmission into new generations, are all interesting problems received copy is denoted Y . from a data communication point of view. Several researchers have shown interest in unveiling the genetic code [27], [28] A. Channel Capacity in order to address such problems and consequently find out In order to quantitatively analyze transmission through a chan- how the complex genetic system is structured. nel, Shannon [1] also introduced an important measure of the amount of information embedded in a message that could be In this work, we study the application of Shannon’s model transmitted reliably through this channel: the channel capacity. to the DNA replication process, which is the process of The ”amount of information” in this definition is a measure of copying a DNA chain of nucleotides into two new chains. uncertainty about the values carried by the message. Based on This process is the basis for biological inheritance for all this concept, a message would be very informative if we have living organisms. In order to tackle this problem, we start high levels of uncertainty about its contents. In contrast, if we by changing the way of conceiving DNA from a ”chain of can predict a message with a sufficient level of certainty, then molecules” into a ”sequence of information elements” that it does not add much information. belong to the nucleotide bases set, or the so-called genetic alphabet F = {A, C, G, T }. With this perception in mind, the original DNA copy is considered the data source and the B. A Framework to Find the Channel Capacity two copies are two targeted data destinations. This process is In this section, we build a mathematical framework not error-free as might seem obvious, and therefore can be for deducting the channel capacity of a communication modeled as a noisy channel using Shannon’s model. channel. Obviously, the amount of uncertainty regarding a message received after going through a communication The rest of this paper is organized as follows. In section II, we channel depends on the nature of the original message derive the necessary mathematical and statistical definitions and the channel effects. Hence, we first define probability comprised by Shannon’s model. For illustration, we further matrices representing the transmitter, the channel, and the provide a simple example for a binary symmetric channel. receiver. Consider a general alphabet F of N elements. If Section III, on the other hand, covers the DNA structure, and F = {s0 , s1 , ..., sN }, then we can define the three following its replication process. Then, we study the replication process matrices [29]–[32]: after characterizing it as a communication model in section IV, which concludes with a simple symmetric replication • The source probability vector Ps , of dimensions N × 1. channel analysis. Finally, our concluding remarks are located This vector given in (1) defines the occurrence probability in section V. For notation consistency over the paper, symbols distribution of the elements of F, where p(si ) ≡ p(X = for matrices and vectors are shown in bold letters, while scalar si ). variables are shown in italic letters.   p(s0 ) Ps =   ..  (1) II. S HANNON M ODEL FOR C OMMUNICATION C HANNELS .  p(sN −1 ) As introduced in section I, Shannon model starts with a data source that produces information messages to be sent to one or more destinations. The sent message is typically • The channel transition matrix Pt , of dimensions N ×N . composed of blocks that belong to a specific alphabet that This matrix defines the transition conditional probability is known to the receiver. The transmitter applies different distribution over the channel. An element in this matrix IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 25 p(sj |si ) ≡ p(Y = sj |X = si ) represents the conditional alternatively is a measure of the amount of uncertainty probability that an alphabet element with the row index regarding the value of Y as stated in (5): is received if the element with the column index was N transmitted, as in (2). X   H(Y ) = E{I(Y )} = − p(yj ) log2 p(yj ) (5) p(s0 |s0 ) ··· p(s0 |sN −1 ) j=1 Pt =  .. .. .. (2) where I(Y ) is a random variable recording the   . . .  p(sN −1 |s0 ) · · · p(sN −1 |sN −1 ) information content of Y , and the set of values {yj ; j = 1, 2, . . . , N } are the possible values for the random variable Y and {p(yj ); j = 1, 2, . . . , N } are • The reveiver probability vector Pr , of dimensions their corresponding probabilities. N × 1. This vector defines the probability distribution of receiving different elements of the alphabet as given • Conditional entropy; H(Y |X), is the entropy of the by (3), where p(sj ) ≡ p(Y = sj ). random variable Y upon learning the value of another   random variable X, given by (6): p(s0 ) Pr =   ..  (3) N X N . X H(Y |X) = − p(xi , yj ) log2 p(yj |xi ) (6)  p(sN −1 ) i=1 j=1 Figure 3 shows a directed graph combining Ps , Pt , and Pr in where the set of values {xi ; i = 1, 2, . . . , N } are the form of a signal flow graph (SFG). This SFG consists of the possible values for the random variable X and nodes and branches, where: {p(xi ); i = 1, 2, . . . , N } are their corresponding • A node denoted p(X = si ) indicates the probability of probabilities. Intuitively, if X and Y are independent transmitting data element si , i = 0, 1, . . . , N − 1. random variables, then H(Y |X) = H(Y ) since there • A branch denoted p(Y = sj |X = si ) indicates the is no added knowledge upon gaining knowledge of the probability of receiving data element sj given that data value X. element si was transmitted ∀ i, j = 1, 2, . . . , N − 1. • A node denoted p(Y = sj ) indicates the probability of • Mutual information; I(X, Y ), between the two random receiving data element sj , j = 0, 1, . . . , N − 1. variables X, and Y , is a measure of the impact of The SFG of Figure 3 is a graphical expression of the total knowing Y on the knowledge of X. This measure is probability theorem. It is usually named a ”channel diagram”. simply the difference between the uncertainty about the Using the source probability vector and the channel transition value of X and the remaining uncertainty upon acquiring matrix, we further define the joint probability distribution of knowledge about the value of Y as in (7) the two random variables X and Y as in (4). I(X, Y ) = I(Y, X) p(X = si , Y = sj ) = p(Y = sj |X = si )p(X = si ) = H(Y ) − H(Y |X) (7) ≡ p(sj |si )p(si ) (4) Based on the probability definitions above, we define a few important quantities pertaining to Shannon model, leading to • Channel capacity; C, is the max value of the mutual the definition of the channel capacity: information between the transmitted signal X and the recieved one Y , over the source probabilities p(X), as • Entropy; H(Y ), of a random variable Y , is the statistical in (8) expected value of the information content stored in Y , or C = max I(X, Y ) = max[H(Y ) − H(Y |X)] (8) p(X) p(X) p(Y = s0 | X = s0) p(X = s0) p(Y = s0) The operational meaning of C is the maximum data rate that can be transferred over the channel reliably. Maximization here takes place over the source probability p(X = s1) p(Y = s1) distribution. C. A Binary Symmetric Communication Channel p( For illustration, we derive the capacity of a simple binary Y = sN p(Y symmetric channel, with only two information elements. That -1 =s |X N- |X = 1 = is X ∈ F = {0, 1}, where the two elements are equiprobable. s0 s1 ) ) p(X = sN–1) p(Y = sN–1) The symmetricity characteristic of the channel indicates equal p(Y = sN-1 | X = sN-1 ) error probabilities for either element. This error probability Fig. 3. A signal flow graph representation of a communication channel. is a key factor in the computation of the channel capacity, and is denoted the crossover error probability: ρ. The source 1857-7202/1008011 26 A.A. RUSHD,: A mathematical model of DNA replication p(0|0) = 1 – ρ Sugar-Phosphate backbone p(X=0) = 1/2 p(Y=0) 5' 3' A T G G T C T A A | 1) =ρ p( 1 |0) =ρ Hydrogen Bonds T A C C A G A T T } Base Pairs p( 0 3' 5' p(X=1) = 1/2 p(Y=1) p(1|1) = 1 – ρ Fig. 6. A DNA double helix composed of two complimentary strands. Fig. 4. An SFG represntation of a binary symmetric channel. reduces into an indentity matrix of rank 2 (Pt = I2 ). The same 1 happens when ρ = 1, since an always erroneous transmission could be addressed and fixed by reversing every received data bit to recover the correct transmitted signal. When ρ = 1/2, 0.8 uncertainty is at its maximum, and the capacity goes to a minimum of 0. 0.6 III. T HE D EOXYRIBONUCLEIC ACID C The deoxyribonucleic acid (DNA) is a long polymer of 0.4 nucleotides that encodes the sequence of the amino acid residues in proteins using the genetic code [33]–[35]. It is a 0.2 large, double-stranded, helical molecule that contains genetic instructions for growth, development, and replication after being coded into proteins. A single DNA strand is represented 0 0 0.2 0.4 0.6 0.8 1 as a sequence of letters that belong to the alphabet F = ρ {A, C, G, T }. The letters are the standard symbols given to the four nucleotides in the DNA, namely the two purines: Adenine Fig. 5. Channel capacity of a symmetric binary communication channel as a function of the crossover probability ρ. (A) and Guanine (G) and the two pyrimidines: Thymine (T ) and Cytosine (C). A typical DNA double helix is shown in Figure 6. The 50 and 30 are labels for the two ends of the strand. Each strand reads from the 50 end to the 30 end. probability vector and the channel transition matrix can be simplified into (9) and are summarized by the signal flow graph in Figure 4. A. DNA Replication Process DNA replication is a fundamental process for the inheritance 1/2 1−ρ ρ Ps = , Pt = (9) and proliferation of all living organisms. It is a core stage in 1/2 ρ 1−ρ the central Dogma of molcular biology which refers to the Using (8), the capacity of the binary symmetric channel can flow of genetic information in biological systems. As shown be manipulated into (10) which is a closed form expression in Figure 7, genetic information flows from DNA to messenger RNA (ribonucleic acid) to proteins. DNA carries the encoded C = 1 + ρ log2 ρ + (1 − ρ) log2 (1 − ρ) (10) genetic information for most species. In order to use this The derivation of (10) is given in Appendix A. Figure 5 shows information to produce proteins, DNA is first replicated into the capacity of the binary symmetric channel as a function of two copies. Each copy gets converted to a messenger RNA the crossover probability ρ. The value of ρ apparently controls through a process called transcription. Translation is the last the channel transition matrix, which in turn controls the stage applied to the information carried by the mRNA in order capacity level. It could be seen from Figure 5 that the capacity to construct a specific protein (or polypeptide) that performs function has two maxima (ρ = 0, 1) and one minimum a specific function in the cell. The enzyme; DNA polymerase (ρ = 21 ). The formulas in (11) show numeric values of the is the major player in the process of DNA replication. It is probability transition matrix Pt at the maxima and minimum responsible for recognizing one strand of the parent DNA extremes. double helix as a template strand. It then makes a compliment 1 0 0 1 Pt |ρ=0 = , Pt |ρ=1 = , 0 1 1 0 Two identical DNA copies 1 1 DNA Replication Pt |ρ= 12 = 2 2 (11) 1 1 2 2 mRNA In light of Shannon’s model, (11) could be explained as Protein Translation Transcription follows. At ρ = 0, no transmission errors occur and the uncertainty vanishes. Therefore, C reaches its maximum value Fig. 7. Central dogma of molecular biology. which is equal to unity, and the channel transition matrix IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 27 py model, including error detection and correction mechanisms as Co a nd Str A mentioned in section III. In fact, the DNA nucleotide alphabet ng adi T Original DNA molecule Le could be perceived as a modulated constellation, analogous C 5' T to the quadrature phase shift keying (QPSK) modulation A T G G scheme as illustrated in Figure 9. Finally, copying the original T A C C ... Replication Fork sequence into two identical chains is analogous to multiple- A T input multiple-output (MIMO) communication systems [40], 3' G A La gg ing Str A T ... [41] where more than one antenna could be used in the transmitter or the receiver for bit error rate (BER) reduction and Co py purposes. In our case, the replication channel is a 1×2 MIMO communication system. Fig. 8. The DNA replication process. 01 00 A C copy of that template. To do this, DNA polymerase starts by reading the nucleotides on a template strand, finds the complementary nucleotides, adds nucleotides in the 50 to 30 direction, and finally links those nucleotides into a new DNA strand which will ultimately form a new double helix with the 11 10 G T parental template strand. (a) (b) B. Error Detection and Correction in the Replication Process Fig. 9. Analogy between QPSK and DNA encoding systems: (a)QPSK signal The new DNA molecule is supposed to be an identical copy of constellation, (b) DNA nucleotide constellation the original molecule. However, events can occur before and during the process of replication that can lead to deletions, insertions, substitutions and mismatched base pairs. Upon adding the complementary base to the new DNA strand, DNA B. Capacity of the Genetic Replication Channel polymerase proofreads the output to detect and potentially fix To completely define the DNA replication channel model, we errors before moving on to the next base on the template. Once need to find its capacity. Following similar steps to those in an error is detected, the damaged molecule could be repaired section II, we start by establishing expressions for the source using one of the following natural approaches: mismatch probability vector Ps and the channel transition matrix Pt . repair, base-excision repair and nucleotide-excision repair. In Substituting the DNA alphabet F = {A, C, G, T } into (1) the following section, we consider the replication process a and (2), we get: basic data transmission process. A study of the error correction   mechanisms is outside the scope of this work. p(A)  p(C)  Ps =  p(G)  ,  (12) IV. DNA R EPLICATION P ROCESS M ODELED AS A C OMMUNICATION C HANNEL p(T ) Several genetic processes have been addressed and modeled   using mathematical models by the bioinformatics research p(A|A) p(A|C) p(A|G) p(A|T )  p(C|A) p(C|C) p(C|G) p(C|T )  community [36]–[39]. In this section, we analyze the DNA Pt =   (13) replication process after modeling it as a communication  p(G|A) p(G|C) p(G|G) p(G|T )  channel. This process involves steps that could be easily p(T |A) p(T |C) p(T |G) p(T |T ) mapped to the communication channel model of section II. Using the general graph of figure 3, we can deduce a signal flow graph to represent the source and channel probabilities A. DNA Replication Channel of (13) as shown in Figure 10. Now, we can define the entropy As covered in section III, the DNA replication process starts of a replicated DNA copy. If the new copy is denoted Y , then with the original DNA sequence, which is mapped to the trans- H(Y ) is a measure of the amount of uncertainty regarding mitted signal X in the communication channel model. The the value of Y which indicates the accuracy of the replication collective mechanisms of the DNA polymerase are mapped to process and is given by (14): the distortion effects resulting from going through the channel. X H(Y ) = − p(y) log2 p(y) (14) Finally, writing copies of the original sequence is mapped to y∈F={A,C,G,T } the reception stage, and each DNA copy is mapped to the received signal Y . where the set of values {y; y ∈ F} are the possible values Interestingly enough, several advanced blocks in the commu- for the random variable Y and {p(y)} are their corresponding nication system model seem to appear in the DNA replication probabilities. Acquiring knowledge about the original DNA 1857-7202/1008011 28 A.A. RUSHD,: A mathematical model of DNA replication molecule X makes it possible to find the conditional entropy Figure 11 shows the capacity of the DNA replication channel of Y given X as follows: of (17) as a function of the crossover probability ρ. Similar to XX the binary symmetric channel case, the value of the crossover H(Y |X) = − p(x, y) log2 p(y|x) (15) error probability ρ apparently controls the channel transition y∈F x∈F matrix, which in turn controls the capacity level. It could be where the set of values {x; x ∈ F} in (15) are the possible seen from Figure 11 that the capacity function has two maxima values for the random variable X and {p(x)} are their cor- (ρ = 0, 1) and one minimum (ρ = 43 ). In (18), numeric responding probabilities. The mutual information between X values of the probability transition matrix Pt are deduced at and Y could therefore be stated as H(Y )−H(Y |X) and hence the maxima and minimum extremes. a general expression for the capacity of the DNA replication   channel could be deduced using (8). To put this conclusion into 1 0 0 0 perspective, we investigate the case of a symmetric channel  0 1 0 0  Pt |ρ=0 =   0 0 , where the crossover error probability is the same for each 1 0  DNA base and the bases are equiprobable. 0 0 0 1   0 1/3 1/3 1/3  1/3 0 1/3 1/3  C. A Symmetric DNA Replication Channel Pt |ρ=1 =  ,  1/3 1/3 0 1/3  In the following discussion, we consider a symmetric DNA 1/3 1/3 1/3 0 replication channel. The nucleotide random variable X takes   1/4 1/4 1/4 1/4 values from the genetic alphabet F = {A, C, G, T }, where  1/4 1/4 1/4 1/4  the four elements are equiprobable. The symmetricity charac- Pt |ρ= 43 =   1/4  (18) 1/4 1/4 1/4  teristic of the channel implies the same error probability for 1/4 1/4 1/4 1/4 each DNA base, denoted ρ. Furthermore, the value of ρ is split equally towards the other three bases. That is the probability of error from one base to any of the other three bases is ρ/3. The At ρ = 0, no replication error occurs and the uncertainty source probability vector and the channel transition matrix of vanishes. Therefore, C reaches its global maximum value this channel can be manipulated into (16) given the previous which is equal to 2, and Pt = I4 . At ρ = 1, the system assumptions. approaches an always erroneous transmission case and the   capacity goes only to a local maximum value of 2 + log2 31 . 1/4 Note that in the replication channel case, ρ = 1 does not  1/4  Ps =  specify which one of the other three nucleotides was supposed  1/4  ,  to be copied. Therefore, we can not easily fix the error as was 1/4 the case for the binary symmetric channel with only two data   1 − ρ ρ/3 ρ/3 ρ/3 elements. Finally, at ρ = 3/4, all transition probabilities go to  ρ/3 1 − ρ ρ/3 ρ/3  1/4, including erroneous and correct transmission. Uncertainty Pt =   ρ/3  (16) ρ/3 1 − ρ ρ/3  is at its maximum in this case, and the capacity goes to a ρ/3 ρ/3 ρ/3 1 − ρ minimum of 0. The capacity of this system is therefore given by (17) which is derived in Appendix B. ρ C = 2 + ρ log2 + (1 − ρ) log2 (1 − ρ) (17) 3 1.5 p(Y = A | X = A) p(X = A) p(Y = A) ) =T X A| 1 Y= C p( p(X = C) p(Y = C) 0.5 p(X = G) p(Y = G) p( Y = T| X 0 = A) 0 0.2 0.4 0.6 0.8 1 p(X = T) p(Y = T) ρ p(Y = T | X = T) Fig. 10. A signal flow graph representation of a symmetric DNA replication Fig. 11. Channel capacity of a symmetric genetic replication channel as a channel. function of the crossover probability ρ. IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 29 V. C ONCLUDING R EMARKS Consequently, the mutual information is I(X, Y ) = H(Y ) − H(Y |X) In this work, we have introduced a simple model for the analysis of the DNA replication process as a communication = H(Y ) + (p(0) + p(1)) channel based on Shannon’s model for communication ? (ρ log2 ρ + (1 − ρ) log2 (1 − ρ)) channels. We have derived a systematic methodology to find ≤ 1 + (p(0) + p(1)) the capacity of this channel and found its value for the case ? (ρ log2 ρ + (1 − ρ) log2 (1 − ρ)) of a symmetric channel. Several remarks are to be observed at this point. First, replication channels are not necessarily Therefore, the channel capacity could be manipulated into symmetric and are different for various DNA segments over C = max I(X, Y ) different organisms [42]–[44]. p(X) = 1 + ρ log2 ρ + (1 − ρ) log2 (1 − ρ) Second, using the proposed mathematical framework, we where the max capacity could be achieved at the optimal can distinguish between different molecules in terms of their solution point of the maximization problem could be easily capacity deviation from the symmetric capacity case, or found to be: p(0) = p(1) = 21 . alternatively, the deviation of the channel transition matrix Pt from the identity matrix. This approach could help solve A PPENDIX B classical molecular biology problems such as the identification P ROOF OF E QUATION (17) of the protein coding regions or the exon-intron classification. Using the source probability vector and the channel transition matrix given by (9), the conditional entropy of Y given X for Third, modern pattern recognition algorithms such as neural the binary symmetric channel could be found to be networks, fuzzy logic, and genetic algorithms, could be XX used to solve the classification problem of DNA segments H(Y |X) = − p(x, y) log2 p(y|x) into categories based on how close their transition matrices x∈F y∈F are to the symmetric case or even to other values of Pt . = − XX p(y|x)p(x) log2 p(y|x) The neural network algorithm for example is composed x∈F y∈F of a learning phase where known data are used to ”train” = −[p(A){p(A|A) log2 p(A|A) the classifier, followed by a testing phase where DNA segments under test are classified into categories based on + p(C|A) log2 p(C|A) + p(G|A) log2 p(G|A) how close they are to the chosen reference value of Pt , which + p(T |A) log2 p(T |A)} is used as prior information for the training or learning phases. + p(C){p(A|C) log2 p(A|C) + p(C|C) log2 p(C|C) + p(G|C) log2 p(G|C) Finally, it is important to point out the low computation cost + p(T |C) log2 p(T |C)} of this algorithm. Computationally efficient techniques are essential when large size DNA databases need to be processed. + p(G){p(A|G) log2 p(A|G) + p(C|G) log2 p(C|G) + p(G|G) log2 p(G|G) + p(T |G) log2 p(T |G)} A PPENDIX A + p(T ){p(A|T ) log2 p(A|T ) P ROOF OF E QUATION (10) + p(C|T ) log2 p(C|T ) + p(G|T ) log2 p(G|T ) This proof could be found in most references on information + p(T |T ) log2 p(T |T )}] theory (e.g. [31]). It is reproduced here for convenience in = −(p(A) + p(C) + p(G) + p(T )) order to facilitate the comparison with its peer proof in ρ ρ ? (3 log2 + (1 − ρ) log2 (1 − ρ)) Appendix B. 3 3 Using the source probability vector and the channel transition Consequently, the mutual information between X and Y is matrix given by (9), the conditional entropy of Y given X for I(X, Y ) = H(Y ) − H(Y |X) the binary symmetric channel could be found to be = H(Y ) + (p(A) + p(C) + p(G) + p(T )) N X N ρ X ? (ρ log2 + (1 − ρ) log2 (1 − ρ)) H(Y |X) = − p(xi , yj ) log2 p(yj |xi ) 3 i=1 j=1 ≤ 2 + (p(A) + p(C) + p(G) + p(T )) N X N ρ ? (ρ log2 + (1 − ρ) log2 (1 − ρ)) 3 X = − p(yj |xi )p(xi ) log2 p(yj |xi ) i=1 j=1 Therefore, the channel capacity could be manipulated into = −p(0){p(0|0) log2 p(0|0) + p(1|0) log2 p(1|0)} C = max I(X, Y ) p(X) − p(1){p(0|1) log2 p(0|1) + p(1|1) log2 p(1|1)} ρ = −(p(0) + p(1))(ρ log2 ρ + (1 − ρ) log2 (1 − ρ)) = 2 + ρ log2 + (1 − ρ) log2 (1 − ρ) 3 1857-7202/1008011 30 A.A. RUSHD,: A mathematical model of DNA replication where the max capacity could be achieved at the optimal [24] R. Hilleke D. Hutchison T. Alvager, G. Graham and J. Westgard, “A solution point of the maximization problem found at: p(A) = generalized information function applied to the genetic code,” Biosys- tems, vol. 24, pp. 239–244, 1990. p(C) = p(G) = p(T ) = 41 . [25] J. Hagenauer C. Andreoli T. Meitinger Z. Dawy, B. Goebel and J. C. Mueller, “Gene mapping and marker clustering using shannon’s mutual information,” IEEE/ACM Transactions on Computational Biology and R EFERENCES Bioinformatics, vol. 3, pp. 47–56, 2006. [1] C.E. Shannon, “A mathematical theory of communication,” Bell System [26] F. H. C. Crick J. D. Watson, “Molecular structure of nucleic acids,” Technical Journal, vol. 27, pp. 379–423, 1948. Nature, vol. 171, pp. 737–738, 1953. [2] D. Stinson, Cryptography Theory and Practice, CRC Press, 2005. [27] B. Hayes, “The invention of the genetic code,” American Scientist, vol. [3] E. Katz, “The twostep flow of communication,” Public Opinion 86, 1998. Quarterly, vol. 21, pp. 61–78, 1957. [28] B. R. Frieden R. A. Gatenby, “Information theory in living systems, [4] C. R. Berger and S. H. Chaffee, “On bridging the communication gap,” methods, applications, and challenges,” Bulletin of Mathematical Biol- Human Communication Research, vol. 15, no. 2, pp. 311–318, 1988. ogy, vol. 69, pp. 635–657, 2007. [5] C. R. Berger and S. H. Chaffee, “Communication theory as a field,” [29] A. Y. Khinchin, Mathematical Foundations of Information Theory, Communication Theory, vol. 9, pp. 119–161, 1999. Dover Publications, 1957. [6] A. Chapanis, “Men, machines, and models,” American Psychologist, [30] J. R. Pierce, An Introduction to Information Theory, Dover Publications, vol. 16, pp. 113–131, 1961. 1980. [7] K. Deutsch, “On communication models in the social sciences,” Public [31] J. A. Thomas T. M. Cover, Elements of Information Theory, Wiley- Opinion Quarterly, vol. 16, pp. 356–380, 1952. Interscience, 2006. [8] D. C. Barnlund, Interpersonal Communication: Survey and Studies, [32] S. Kullback, Information Theory and Statistics, Dover Publications, Boston Houghton Mifflin, 1968. 1997. [9] G. Gerbner, “Toward a general model of communication,” Audio-Visual [33] A. Berry J. D. Watson, DNA: The Secret of Life, Alfred A. Knopf, Communication Review, vol. 4, pp. 171–199, 1956. 2003. [10] Z. Reznikova, “Dialog with black box: using information theory to study [34] L. A. Allison, Fundamental Molecular Biology, Wiley-Blackwell, 2007. animal language behaviour,” Acta Ethologica, vol. 10, no. 1, pp. 1–12, [35] R. Weaver, Molecular Biology, McGraw-Hill Sci- April 2007. ence/Engineering/Math, 2007. [11] E. Maasoumi, “A compendium to information theory in economics and [36] D. Posada, Bioinformatics for DNA Sequence Analysis, Humana Press, econometrics,” Econometric Reviews, vol. 12, pp. 137–181, 1993. 2009. [12] H. H. Permuter Y. H. Kim and T. Weissman, “Directed information [37] B. F. F. Ouellette A. D. Baxevanis, Bioinformatics: A Practical Guide and causal estimation in continuous time,” in Proceedings of the IEEE to the Analysis of Genes and Proteins, Wiley-Interscience, 2004. International Symposium on Information Theory ISIT, 2009, pp. 819– [38] G. R. Grant W. J. Ewens, Statistical Methods in Bioinformatics: An 823. Introduction, Springer, 2004. [13] T. M. Cover, “Universal portfolios,” Mathematical Finance, vol. 1, pp. [39] D. W. Mount, Bioinformatics: Sequence and Genome Analysis, Cold 1–29, 1991. Spring Harbor Laboratory Press, 2004. [14] T. M. Cover and E. Ordentlich, “Universal portfolios with side [40] P. Stoica E. G. Larsson, Space-Time Block Coding for Wireless information,” IEEE Transactions on Information Theory, vol. 42, pp. Communications, Cambridge University Press, 2004. 348–363, 1996. [41] D. Gore A. Paulraj, R. Nabar, Introduction to Space-Time Wireless [15] R. Bell and T. M. Cover, “Game-theoretic optimal portfolios,” Man- Communications, Cambridge University Press, 2008. agement Science, vol. 34, pp. 724–733, 1988. [42] D. Charlesworth J. W. Drake, B. Charlesworth and J. F. Crow, “Rates [16] H. H. Permuter Y. H. Kim and T. Weissman, “On directed information of spontaneous mutation,” Genetics, vol. 148, pp. 1667–1686, 1998. and gambling,” in Proceedings of the IEEE International Symposium [43] S. L. Crowell N. W. Nachman, “Estimate of the mutation rate per on Information Theory ISIT, 2008, pp. 1403–1407. nucleotide in humans,” Genetics, vol. 156, pp. 297–304, 2000. [17] T. M. Cover and R. King, “A convergent gambling estimate of the [44] D. N. Cooper and M. Krawczak, Human Gene Mutation, Bios Scientific entropy of english,” IEEE Transactions on Information Theory, vol. 24, Publishers, Oxford, 1993. no. 4, pp. 413–421, 1978. [18] L. Breiman, “Optimal gambling systems for favourable games,” in Berkeley Symposium on Mathematical Statistics and Probability, 1961, pp. 65–78. [19] P. Haggerty, “Seismic signal processinga new millennium perspective,” Ahmad A. Rushdi received the B.Sc. and M.Sc. de- Geophysics, vol. 66, no. 1, pp. 18–20, 2001. grees in Electronics and Electrical Communications [20] S. Chandrasekhar, The Mathematical Theory of Black Holes, Oxford Engineering from Cairo University, Cairo, Egypt, in University Press, 1998. 2002 and 2004 respectively, and the Ph.D. degree [21] J. H. Moore, “Bases, bits and disease: a mathematical theory of human in Electrical and Computer Engineering from the genetics,” European Journal of Human Genetics, vol. 16, pp. 143–144, University of Califiornia, Davis in 2008. Since 2008, 2008. he has been with Cisco Systems, Inc., San Jose CA. [22] A. Figureau, “Information theory and the genetic code,” Origins of Life His current work with Cisco Systems involves signal and Evolution of the Biosphere, vol. 17, pp. 439–449, 2006. and power integrity for hardware design. [23] R. Sanchez and R. Grau, “A genetic code boolean structure. ii. the Dr. Rushdi is the recipient of several teaching genetic information system as a boolean information system,” Bulletin and research awards, and an active member within of Mathematical Biology, vol. 67, pp. 1017–1029, 2005. the engineering and scientific research communities. His research interests include statistical and multirate signal processing with applications in wireless communications and bioinformatics. IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 31 Mapping Network Protocols to Layers of the OSI Model Götz Peter Gallert Abstract–The 7-layer OSI architecture is the most The seven layers of the OSI model describe the tasks important model for teaching computer network- to be solved to build a functional internetwork in a ing. However, the various computer networking modular way [14]. Much similar, although not OSI- teaching sources contain much disagreement, if not based, is the practical implementation of computer net- outright argument, about which OSI layer describes working today: Several protocols together provide the the respective protocols used in today’s networks. functionality of “the network”, each being responsible If the academic claim is true that the OSI model for a restricted number of tasks. completely describes computer networking, a con- sensus should be possible on where any network Consequently, if ISO’s OSI reference framework re- protocol is located in this model. Such consensus has not been achieved – Is there something wrong ally is a model of computer networks it should be able with the procedure of mapping network protocols to describe the interdependence of prevailing protocols to layers of the OSI model? within its seven layers. But while there is agreement This paper attempts to shed light on the issue by that every network protocol fits somewhere into the claiming that there are indeed three different sets OSI model it is sometimes not clear exactly where it of criteria for deciding which OSI layer governs fits. what protocol. It describes them, shows how their amalgamation leads to consistency problems, and The reason for the difficulty populating the OSI offers an outline of what OSI layer placement of model with today’s common-use network protocols em- common protocols they suggest if they are being anates mainly from the situation that most of them are followed consistently. It further considers the part of, or related to, the protocol stack of TCP/IP. distinction between network protocols and network From the standards formulation in the respective Re- management protocols, refuting its ability to quest for Comment (RfC) it is sometimes made explicit solve the problem. It concludes by recommending which TCP/IP layer is responsible for a given protocol to consistently stick to one set of placement criteria. [2] [3], but layering with respect to the OSI model often remains unclear. Index terms–layering, network modeling, OSI, TCP/IP Furthermore, IETF protocol designers are least con- cerned about allocation to OSI layers and indeed do not intend to follow the principles of OSI layering, i.e. 1 Introduction the complete independence of lower layers from upper layers and the concept of the sole reason for the ex- The International Standards Organisation’s (ISO) istence of layer n − 1 being support for layer n, c.f. Open Systems Interconnection (OSI) model today is [9]. the single most important model for teaching computer networking. It is both universal and clearly defined, Possibly as a result of this uncertainty, computer net- two properties that, academically, give it a clear advan- working text books seldom explicitly thematize this is- tage over the more scetchily laid down and protocol- sue. Instead, the claim that a certain protocol is on a specific TCP/IP counterpart. particular layer of either model is often hidden in the It structures the process of information exchange general structure of the text (the table of contents) and over computer networks and, in its role as a model does not receive further coverage [cf. e.g. 12]. Various of the real process, simpifies discourse about design, sites on the World Wide Web however do discuss the implementation and deployment of complex internet- topic. As those sources (this paper uses [13] and [1] working solutions. as two examples of thousands of pages in this area) are much easier available than printed material, the neces- Manuscript received October 4, 2010. sity arises to discuss the merits of their claims because G P Gallert is with the Polytechnic of Namibia, Private Bag 13388, Windhoek, Namibia (phone: +264-61-207-2268, fax: tertiary education in computer networking is heavily +264-61-2072051, email:

). affected by web sites explaining “how it really works”. 1857-7202/1010001 0DSSLQJ1HWZRUN3URWRFROVWR/D\HUVRIWKH26,0RGHO 1.1 Some contested protocols 7 Application Layer Wikipedia1 discussion pages2 on the subject area pro- 6 Presentation Layer Application Layer 4 vide some insight into the thoughts of contributors with different professional and educational background, all 5 Session Layer of whom claim to have some authority on the matter. These discussions [13] reveal the following main points 4 Transport Layer Transport Layer 3 of disagreement: 3 Network Layer Internet Layer 2 1. Whether routing protocols should be on OSI layer 2 Data Link Layer 3 because they facilitate end-to-end IP delivery, or Link Layer 1 on other layers depending on what functionalities 1 Physical Layer they use, 2. Whether protocols should be placed on the highest Fig. 1: A juxtaposition of the OSI model (left) and the OSI layer they contribute to, or on the lowest (e.g. TCP/IP model (right) as suggested e.g. in [6] in the cases of DHCP and HTTP), and [12] 3. Whether the exercise of OSI-layering protocols that have been designed independent of OSI has any merit at all. This relationship can be criticised. While a detailed reasoning in this regard is beyond the scope of this Also on more formal platforms authors disagree article [see 8, for a thorough discussion], one example about certain protocols. A Cisco white paper on shall be given to pinpoint the problem: For the OSI TCP/IP technology places Address Resolution Proto- model, the responsibility of the Network Layer lies in col (ARP) on OSI layer 2 [10, p.2], Forouzan on layer 3 the provision of end-to-end delivery of datagrams, in [6, p.43]. Even its location in the TCP/IP model seems contrast to next-hop delivery which is the responsibility not to be entirely obvious; the Cisco CCNA Discov- of the Data Link layer [14, p.430]. On the other hand, ery curriculum (version 4.0, module 2, chapter 7.2.1.2) the TCP/IP model sees its Internet layer as the vir- stacks it between Internet and Link layer.3 tual network interface [7, p.8], something that clearly includes next-hop delivery. (The disagreement about ARP is based on this difference). 1.2 Relationship of the TCP/IP and OSI The relation between the two reference models is Reference Models therefore not a function at all, and figure 1 is an over- As with the layer placement of particular protocols, simplification. the relationship between TCP/IP and OSI reference models is not often made explicit in standard network- 1.3 Layering Considered Harmful? ing texts. Few of them go as far as suggesting certain TCP/IP protocols to belong to a particular OSI layer RfC 3439 [9] contains a section titled “Layering Con- as in [11, chapter 1]. Most do, however, offer a model sidered Harmful”, a paragraph sometimes quoted to comparison that is often depicted as in figure 1: This scetch the seemingly ultimate impossibility to decide graphic suggests protocol location to be a surjective on OSI layers for common protocols [1] [13]. function from OSI onto the TCP/IP model. It partic- Claims like these stem from a misunderstanding ularly: about the purpose of RfC 3439: It uses a completely different definition of layering and does not say any- • restricts the placement of Link-layer TCP/IP pro- thing at all about network models as such. It partic- tocols to OSI layers 1 and 2, ularly does not reference RfC 1122 nor RfC 1123, the two documents defining the TCP/IP layers. What has • maps Transport-layer TCP/IP protocols to OSI indeed been considered harmful by the authors is the layer 4, and Internet-layer TCP/IP protocols to over-diversification of the protocol landscape. OSI layer 3, and To a certain degree RfC 3439 repudiates the neces- • restricts the placement of Application-layer sity to design IEEE protocols in a way reconcilable with TCP/IP protocols to OSI layers 5 to 7. the OSI framework: Artificial separation of responsibil- ities by layers – OSI or TCP/IP – is to be avoided if it 1 http://en.wikipedia.org 2 It should be emphasized that the reference here is to the dis- does nothing to improve implementation. This obser- cussion pages of the articles, typically batches of comments vation ought to be kept in mind when performing any that as a matter of netiquêtte are not extensively edited. This TCP/IP-to-OSI mapping but it should never be used is in contrast to the articles themselves that might change to as a critique of the IEEE standardisation process. It is better or worse within a matter of minutes. 3 For consistency in this paper the OSI layers 2 and 3 are called the obligation of the scientists to prove that a model “Data Link” and “Network” layer while the TCP/IP layers is a useful abstraction of the real-life process; to argue 1 and 2 are called “Link” and “Internet” layer, respectively. the other way round is unrealistic. IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 33 1.4 Network Protocols vs Network 2. Operational approach: On what functionality does Management Protocols this protocol rely? Place the protocol dependent on the services it uses. To avoid some of the issues regarding layer mapping it has been suggested to distinguish network protocols 3. Conceptual approach: What is the responsibility from network management protocols [13] or core proto- of this protocol? Decide the placement of the pro- cols from supporting protocols, [6, p.43], arguing that tocol by determining its contribution to network the management protocols do not carry user data and connectivity. are therefore to be regarded as necessary overhead to “real” networking communication. The rationale be- Of course these different approaches can lead to dif- hind this suggestion might have been that it is fore- ferent results, and mixing them to populate one and most the management protocols that seem to evade the same network model leads to the described diffi- OSI classification, and not so much the protocols that culties. But just as mixing the three strategies yields actually transfer user data. undesired, even haphazard, results, the effect of con- With this distinction one can apply different strate- sistently using one method for layering might equally gies of OSI-layering, one for the “genuine” and one for surprise. The following sections describe the three no- the management protocols, e.g. by basing the clas- tions in detail. sification of “normal” protocols on functionality but placing the management protocols into the layer they 2.1 The Functional Approach actually manage. However, difficulties seem to begin, rather than end, at this classification: The functional approach makes the assertion that for any PDU, if the payload is on layer n of the TCP/IP 1. The distinction itself is not easy to do: Whether model, the PDU itself belongs to layer n − 1. TCP transmits user data or not depends on its cur- rent payload: if it is an HTTP request it does, if it “From the IETF perspective, the payload is a BGP update it doesn’t. defines layering.” [13] 2. The term “user data” lacks satisfactory precision: Howard C. Berkowitz, IETF engineer and author Is there any user data transmitted by Samba? Does a user-initiated traceroute constitute user The appeal of this principle is that it directly follows data or not? the TCP/IP design approach with regards to encapsu- lation by arguing e.g that any PDU that has a TCP 3. The distinction fails for multi-layer protocol stacks segment as payload must be on the Internet layer. like VoIP or ATM, as they will typically contain For the core TCP/IP protocols this is entirely cor- both management and user data protocols. rect: The payload of any transport layer segment is application data, the payload of a packet is a segment, 4. The layering instructions for management proto- the payload of a frame is a packet. But two questions cols is just as opaque as before: for instance, which remain unanswered by the functional approach: layer is managed by DHCP? By NTP? 1. How can this principle be applied to layers of the In conclusion, the following picture develops: Ap- OSI model ? As outlined in section 1.2 the map- plying a narrow definition of “user data”, the genuine ping between OSI and TCP/IP is not entirely triv- protocols in IP networks are simply the core protocols ial. from the TCP/IP protocol stack: TCP, UDP, IP, and some clear cases on link and application layer. All other 2. What should be done with protocols that do not protocols are management protocols. The instruction encapsulate any upper-layer PDU (the manage- to sort them into layers “by what they manage” there- ment protocols as characterised in section 1.4)? fore simply reverts to the layering instruction that will below be called the conceptual approach, to matching There is no satisfying answer to question 1. If the net- the protocol’s and the layer’s responsibilities. work is operated by the TCP/IP protocol stack, peer- to-peer information that would belong to OSI layers 1, 5, and 6 is included in the encapsulation process on lay- 2 Three General Approaches ers 2 and 7, respectively. As such the layers under the functional approach would be defined by the encapsu- Investigating the reasons given for particular place- lation process. This happens only four times, and OSI ments of protocols into layers of the OSI model, at layers 1, 5, and 6 would necessarily remain empty. least three major classes of arguments seem to prevail: There are two possible solutions to the problem in question 2. One is to place all management protocols 1. Functional approach: What data does this proto- on the highest layer because they do not fulfill the re- col send? Conclude the placement of the protocol quirements to be placed anywhere else. This mapping from the payload of its data units. would lead to a layer mapping as shown in figure 2. 1857-7202/1010001 0DSSLQJ1HWZRUN3URWRFROVWR/D\HUVRIWKH26,0RGHO DHCP BGP IS- 7 7 DHCP BGP IS OSPF ARP 6 6 5 5 4 TCP UDP 4 TCP UDP 3 IP 3 IP OSPF 2 2 IS-IS ARP 1 1 Fig. 2: OSI placement under the functional approach Fig. 3: OSI placement under the operational approach Another attempt would be to investigate those man- all have more or less the same functionality but differ agement protocols separately and not to decide their widely in implementation, and therefore in their usage placement at this stage. of network functionality. Both these possible solutions have disadvantages. There is a further problem with this strategy: To de- The first possibility leads to a counter-intuitive pro- cide whether a certain protocol relies on another one is tocol placement where most functionalities are concen- not entirely straight-forward. For instance, both DHCP trated on OSI layer 7, the second one reduces the entire and BGP are assigned well-known ports. Still DHCP does approach to a solution dependent on other approaches not rely on IP and UDP functionality in the same way to answer “the interesting” questions. Indeed, answer that BGP relies on IP and TCP because DHCP often is 2 would decide layer placement only for all trivial cases. implemented within the same broadcast domain. 2.2 The Operational Approach 2.3 The Conceptual Approach There are several versions of this approach. In its most general form, the operational approach makes the as- The conceptual approach makes the assertion that each sertion that no protocol x may be placed below a pro- protocol belongs to the OSI layer that matches its re- tocol y, if x relies on y to operate. More restrictive sponsibility. characterisations are: The appeal of this approach is that it best maps the design intentions of the OSI model: to assemble a 1. If a protocol uses functionality on layers framework of responsibilities that together define and accomplish a general, common functionality. It also fits n1 , n2 , . . . , nm ∈ N best into the model character of OSI as it offers some explanation behind layer placement as opposed to just it belongs to layer k = max{N }. a technical criterion. Furthermore it does not reqire 2. If a protocol uses functionality on layers the additional bypass of refering to TCP/IP layering first, and OSI layering second. It thus is not susceptible n1 , n2 , . . . , nm ∈ N to the problems outlined in section 1.2. This approach is the hardest to follow as the high- it belongs to a layer k > max{N }. level purpose of networking protocols is rarely well doc- umented, and if it is it often happens years after the This is the opposite of the functional approach – it protocols have been standardized.4 Furthermore, as concentrates not on the payload but the encapsulation protocol designers are not bound by the OSI layer def- of a PDU. The operational approach enforces a layer initions, not every protocol might strictly fit one layer mapping as outlined in figure 3. The appeal of this – as RfC 1925 humorously puts it: approach is that it formalises the constitutional princi- ple of the OSI model: that the sole raison d’être of the “It is always possible to aglutenate [sic] lower layers be to support the higher layers [as outlined multiple separate problems into a single in 14, p.430]. Furthermore it avoids the potential am- complex interdependent solution.” [4] biguity of placing protocols that span multiple layers of either model. R. Callon, RfC 1925, Fundamental Networking Truth Unilateral use of the operational approach leads to #5 the situation that functionally similar protocols might be scattered all over the place. This becomes partic- 4 For the Internet protocol suite see e.g [5] which was published ularly visible in the case of routing protocols which 15 years after the first protocol proposals. IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 35 7 in turn invokes the conceptual approach (cf. 2.3). The functional approach therefore must be rejected as a 6 strategy to map TCP/IP protocols to layers of the OSI model. 5 What remains are the two independent strategies, 4 TCP UDP the operational approach (layer to reliance) and the conceptual approach (layer to responsibility). Al- IP BGP IS-IS 3 though the assumption underlying current OSI layering OSPF DHCP practice – that the TCP/IP layer predetermines the 2 ARP OSI layer – lacks foundation, both have their merits 1 and lead to an acceptable layer population that avoids ambiguity in the variable of interest. Problems arise when both methods are combined: Fig. 4: OSI placement under the conceptual approach To argue that BGP must be above OSI layer 4 for its re- liance on TCP (operational approach) and then to place it on layer 7 because it has no responsibilities on lay- The conceptual aproach leads to certain uncomfort- ers 5 and 6 (conceptual approach) lacks rigor because able situations with protocols that have responsibilities the conceptual approach would place any routing pro- on multiple layers. DHCP for instance provides IP ad- tocol on OSI layer 3, not 7, in the first place. Alterna- dresses (OSI layer 3), gateway information (a layer 2 tively, to place ARP and DHCP both on layer 3 because of OSI function), and domain information (layer 7). ARP’s implementation over the link layer (operational While this is in itself not a problem – many protocols approach) and DHCP’s main role (provide IP addresses, are actually protocol stacks and cover multiple layers – conceptual approach) is methodologically inferior. it might still seem strange that certain layers are com- The operational approach leads to uncommon and pletely left out. This defies the OSI layering principles counter-intuitive protocol placement (cf. 2.2). The as laid out in [14]; DHCP certainly has no responsibility conceptual approach differs slightly from common whatsoever on OSI layers 4 to 6, and DHCP is clearly a practice and is the hardest to apply because its crite- singular protocol and not a stack. rion is harder to formalise. Using this approach, place- It must be reiterated that the IETF refutes these ment of every networking protocol on one singular OSI principles (cf. section 1.3). The perceived conceptual layer is hardly possible, given the design goals of IETF weakness therefore is inherent to the IETF protocols, [9]. It has two advantages, though: it is the closest to not to their mapping to the OSI model. Still the ques- the definition of the OSI model, and the one generally tion remains where to place protocols whose functional- applicable throughout the protocol landscape. ities span multiple OSI layers, an exhaustive discussion From a teaching perspective a method that under- of which is considered beyond the scope of this article. scores the model properties (simplification, structur- The rigorous attempt to solve this challenge might ing, and explanation) of OSI could be suited best, be to put them to every layer they contribute to in and the conceptual approach could therefore be pref- terms of functionality, because the solution that may ered over other attempts. Other standpoints might of seem obvious and desirable: to place protocols on their course merit a different choice. main layer of contribution, will necessarily introduce new ambiguity. The pragmatic attempt might be to place such proto- References cols into a layer of choice depending on the main focus [1] 4engr. Internet Protocol Suite. 4engr. All of the point to be made. OSI layering is, as stated be- Your Engineering Information, August 2009. fore, mainly an academic exercise. If for example the http://www.4engr.com/dictionary/catalog/ aim is to explain how Data Link Layer connectivity is 3693/index.html. Last accessed 25 August 2009. “lifted” to the Network Layer with automatic address allocation it makes sense to place DHCP on OSI layer 3 [2] R. Braden, editor. RfC 1123. Requirements for (as done in figure 4). If on the other hand the automa- Internet Hosts – Application and Support. IEEE tion of network configuration tasks is focused on, DHCP RfC, 1989. Definition of Application Layer of the acts much like an application providing the necessary TCP/IP model. parameters, and could be placed on OSI layer 7. [3] R. Braden, editor. RfC1122. Requirements for In- 2.4 Evaluation and Conclusion ternet Hosts – Communication Layers. IEEE RfC, 1989. Definition of Link Layer, Internet Layer and The functional approach is either not an independent Transport Layer of the TCP/IP model. solution to the problem, or it decides only trivial cases and enforces a distinction into network protocols and [4] R. Callon. RfC 1925. The Twelve Networking management protocols (cf. section 1.4), a strategy that Truths. IEEE RfC, 1996. April 1st RfC. 1857-7202/1010001 0DSSLQJ1HWZRUN3URWRFROVWR/D\HUVRIWKH26,0RGHO [5] David D Clark. The Design Philosophy of the DARPA Internet Protocols. Proceedings of Peter Gallert (born 1971) SIGCOMM. Computer Communication Review, holds a Magister degree in 18:106–114, August 1988. Re-published 1995. logic, theory of science, com- munication studies and me- [6] Behrouz A Forouzan. Data Communications and dia science from University of Networking. McGraw Hill, 4th edition, 2007. Leipzig, Germany. [7] Lydia Parziale et al. TCP/IP Tutorial and Techni- cal Overview. IBM RedBook series. IBM Interna- He has been working as Senior Lecturer: Informa- tional Technical Support Organisation, New York tion Technology at Polytechnic of Namibia in Wind- City, 8th edition, 2006. hoek since his emigration to Namibia in 2000. He is currently working on a quality of service implementa- [8] D M Piscitello and A L Chapin. Open Systems tion for meshed overlay networks in cooperation with Networking: TCP/IP and OSI. Addison-Wesley, the University of Cape Town. 1993. [9] D. Meyer R. Bush. Some Internet Architectural Guidelines and Philosophy. IEEE RfC, 2002. Sec- tion 3 L̈ayering Considered Harmful.̈ [10] Cisco Systems. TCP/IP Technology. Cisco Systems Technology White Paper. Cisco Systems, 2005. http://www.cisco.com/en/US/docs/ internetworking/technology/handbook/ito_ doc.html. Last accessed 14 August 2009. [11] Cisco Systems. Internet Technologies Handbook. 2008. http://www.cisco.com/en/US/docs/ internetworking/technology/handbook/ito_ doc.html. Last accessed 7 July 2009. (Series of chapters without author information; not published as entire book). [12] Andrew S. Tanenbaum. Computer Networks. Pearson Education International, 4 edition, 2003. [13] Wikipedia Talk. Wikipedia Talk: OSI model. English Wikipedia, August 2009. http://en. wikipedia.org/wiki/Talk:OSI_model. Last ac- cessed 25 August 2009. [14] Hubert Zimmermann. OSI Reference Model – The ISO Model of Architecture for Open Systems In- terconnection. IEEE Transactions on Communi- cations, COM-28:pp. 425 – 432, 1980. Definition of the OSI Model. IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 37 Fast Geographic Internet Mapping System for Location-Based Services Edmar Mota-García† and Rogelio Hasimoto-Beltran‡  Abstract— We propose an Internet (IP) mapping system for discovering network topology and geographic location of hosts (routers/end-nodes) based on four main steps: a) domain name based mapping, b) host IP clustering, c) clustering refinement via host delay location, and d) IP distance similarity using IP differences. Unlike previous schemes that use large databases and intensive route probing systems over different Internet Service Providers (ISPs), our scheme makes use of small but reliable where a fast and efficient IP2Loc service is more important database tables spread across the region of interest (no probing is needed over different IPSs), Border Gateway Protocol (BGP) Fig. 1. IP address to geographic location. tables, and scalable traceroute information (that includes delay and connection information) for a fast and effective IP to location than location precision. This type of service could enable an mapping (no ISP probing is needed). We concentrate on interesting class of location-aware services in media delivery providing fast node location information for Location-Base Services (LBS) to support multimedia delivery architecture applications for Internet hosts [1] (we will use host and routers design (previous schemes focus on accurate geographic location interchangeably throughout the rest of the paper). Under this of nodes). As a study case we analyzed the router-level topology panorama, the closest server can be in charge of serving of the Internet in México and built an IP address to location clients requests for improving delivery delays; additionally, mapping table. The order of magnitude of the complete analysis servers can use more than one path (known as path diversity) over the region of interest is in the order of minutes to hours, to deliver information to clients for a more effective use of whereas previous schemes order of magnitude can go from days to weeks. Our approach can be successfully applied anywhere in bandwidth as shown in [2]. Location-aware applications can the world with the corresponding initial database table. track network properties more easily and use them as Quality of Service (QoS) measure for the next data delivery. Index Terms— Geographic Mapping, Traceroute, One-way Discovering network topology and geographic location of Transit Time, Content Delivery Network. routers and end-nodes (extreme nodes in a communication process) is not an easy task. Internet Service Providers (ISP) keep their router-level topology confidential, and when trying I. INTRODUCTION to infer it by software tools such as traceroute, routers may not B UILDING an IP address to location mapping (IP2loc) service is an interesting problem that has received a lot of attention during the last years. The aim of an IP2loc service is reply to ICMP packages or may reply with different misnamed domain names [15]. At the end, only an approximation of the real IP topology can be obtained. to find the probable geographic location of a node or router in Current schemes in the literature use tremendous amount of a predefined area of interest based on its IP only, as depicted time and probes to infer the IP topology in detail (which can in Figure 1. Depending on the complexity of the scheme, take days to weeks to converge to the specified topology), in probing duration and size/density of the initial database table, addition to require large databases with sometimes unreliable the certainty of the assigned location can be as high as mapping list (applied to a particular ISP at a time). This huge hundreds of meters around the real node location. Our aim is effort in providing a high detailed mapping could be useless practical scenarios of Content Delivery Networks (CDN) [14], due to the unceasing growth and dynamic nature of the network (host mapping could be degraded up to a 70% in a period of a month) [3]. Our goal in designing a new Internet router level mapping scheme is to obtain an acceptable level Manuscript received October 20, 2010. This work was supported in part by the State Council of Science and Technology of Guanajuato-México of topological detail for CDNs with less effort and resources (CONCYTEG) under grant number 07-02-K662-044-A01. (in minutes to hours), and without depending on third-party ‡ R. Hasimoto-Beltran is with the Department of Computer Science at the generated information (ISP probing). We prove that a small Center for Research in Mathematics (CIMAT), Guanajuato, México (corresponding author e-mail:

). and independent of any ISP database of homogeneously † Edmar Mota-García is with the National Institute of Public Education, in spread nodes over the region of interest provides the same Sinaloa, México (

). 1857-7202/1010006 38 E. Mota-Garcia, R. Hasimoto-Beltran: Fast Geographic Internet Mapping System For Location-Based Services backbone than the one obtained by intensive probing over multiple ISPs. The level of detail or resolution in our scheme is flexible depending on the initial input data density. To validate our proposed scheme, we present a study-case to infer the Mexican Internet topology and compare our results against one of the state of the art tools named RocketFuel [5]. The paper is organized as follows. In the next section we discuss current methods for Internet mapping. Section 3 and 4 describe the proposed approach and results respectively. Future work and concluding remarks are presented in section 5. II. RELATED WORK Several research efforts have been performed to infer the Internet routing topology (backbone) and geographic location of routers through different approaches. The Mercator tool [4] Fig. 2. Diagram of the proposed scheme. is used to create maps of Internet hosts without considering their geographic location. Mercator uses traceroute like probes In this work, we propose a new system for IP address to obtain host connectivity and iteratively improves the geographic location, where an acceptable level of topological mapping process (address-to-location) using heuristics for the detail can be accomplished using a simpler scheme. Our exploration of the IP space called informed random address proposed scheme do not probe any ISP in particular, instead it probing. This probing scheme is aimed at minimizing the uses a small and reliable database homogeneously spread number of probes sent to the network using a subset of the across the region of interest (initial IP-to-location list), along address space. In [1], authors present an IP2Geo scheme for with restricted probing and hosts delay from different determining the geographic location of Internet hosts. IP2Geo landmarks nodes to discern from hosts having the same name consists of three techniques: GeoTrack to infer location from or address prefix, but located in far apart regions (which DNS names, GeoPing for location interpolation using ping makes our scheme robust against misnamed DNS [15]). Our delay measurements, and GeoCluster to create host clusters aim is to provide a rapid node geolocation system in a based on BGP tables and an initial IP2loc list. They report a particular region of interest for real-time content delivery 30% localization error (compared to the correct ISP topology). services (video, audio, web content, etc.). The outcome of our Rocketfuel [5] was developed to map the topology inside system includes the connection topology in the region plus an the Internet Service Provider (ISP). It is composed of a series IP2Loc list for use with newly incoming clients. of techniques similar to those found in IP2Geo tool [1], which interact each other to build the topology for a given ISP. One III. PROPOSED SCHEME problem with RocketFuel is that the level of complexity grows Our approach attempts to infer the connection topology and with the size of the ISP. Each ISP has to be probed and geographic location of hosts with a specified level of detail analyzed separately, so that the time to completely map a (depending on the initial database node density), by combining region of interest grows with the number of ISP present in the 4 main algorithms (Figure 2): area. In [6], authors explore the use of Rocketfuel for path a) Initial Name-Location Mapping (INLM). It makes use diversity discovery, proposing minor changes to maximize the of domain name information in order to obtain an initial guess probability to correctly infer the inner topology of the targeted on the location of the hosts. This algorithm is affected by DNS ISP. Despite of the great level of detail obtained by misnaming, which accur in the 0.5% of the IP addresses [15]. Rocketfuel, the modified scheme presents higher rate of false b) Host clustering (HC). A clustering algorithm is applied and missed links. Their conclusion is that, increasing the level to the initial localization of hosts to find groups of IP prefixes of detail or increasing the probing time does not necessarily that share a common location. For this step, a predefined change the minimal average error (reported to be 15% of the IP2loc prefix list is used to refine the host localization process address space probed). in previous phase (a). Using delay and topology information can be helpful in c) Topology and Delay Location (IPDelay). We use the providing better geographic location as proved in [7], the topology and delay information returned by traceroute to infer Vivaldi protocol [8]), and more recently in [9, 10]. In [9], the location of unclassified hosts in the initial phases (a and b). authors claim that the utilization of delay-based geolocation is A new host clustering phase takes place to refine the preferable since eliminates the need to solely rely on data that localization process. This algorithm makes the scheme robust could be incomplete, inaccurate or misleading like DNS to DNS misnaming [15]. registers. Furthermore, they report that a simple ping-like d) IP distance similarity (IPDS). As a final step in our probing (like the ones returned by traceroute output) is approach we use a simple IP number distance based metric to sufficient to be used as a host geolocator. locate isolated and not recognized addresses. IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 39 These four algorithms work together to provide an IP2Loc mapping and to construct a connection topology of a particular region in the Internet. An additional level of detail can be provided by augmenting the information provided in the probing phase (algorithm a). A detail explanation of each algorithm is described next. 3.1 Initial Name-Location mapping (INLM) In order to minimize the probing phase in our scheme, we propose the use of a small Host Probing List (HPL) dispersed over the region of interest. The HPL (provided by the Institute of Educational Technology of the Department of Public Education and Culture of the state of Sinaloa, México–IET- DPEC), consists of web portals of local governments, educational institutes, companies, etc. for which their physical locations and IP addresses are known. In general, the HPL takes one host per city in the region of interest, but is flexible enough to allow finer (coarser) resolution to the system by adding (eliminating) elements to the list. The HPL is complemented with selected hosts called landmarks. Landmarks help in the probing process by gathering delay and connection information (from different perspectives) when a host does not fit in any particular IP group. A restriction on the selection of the landmarks is that they must not be behind a firewall, in order to receive ICMP and/or UDP packets. The process starts by running traceroute or tracert from each landmark to each host in the HPL to obtain router-level connection and domain name information. This is what we call an Initial Restricted Probing phase, which differs from other schemes that use of random probing instead [4]. Fig. 3. Pseudocode of the HC algorithm. The domain name information of intermediate routers is Once we have mapped the set of intermediate routers by using compared with the ISPs naming convention in the area of their domain name only, the next step is a clustering process interest [1, 5]. Unfortunately, this information is not publicly based on a verified host IP list to further refine this first available, but it is possible to infer some patterns after approximation in the case of errors. The HC refinement is analyzing the current structure of the ISPs domain names. important to further partition those groups of routers with the Specific extensions or codes used by the DNS may be helpful same domain name but physically far apart, or with different to separate those hosts located in the analyzed country from domain name (belonging to another location) but located in the rest (for example mx for México, se for Sweden, jp for the same region. HC uses a verified address-location list, Japan and so on), and within the country itself at a finer named vIP2Loc list, which is the HPL list with additional end- resolution (at state and/or city resolution). We found that the nodes (clients) IP addresses and location information (it is a domain naming convention used by the main ISPs in México superset of HPL containing a verified mapping of IP addresses includes city and state acronyms in their clients, routers and to locations). backbone routers in most of the cases. We additionally created The clustering algorithm takes as input the Address Prefix a database containing airport codes, strings bb and core for (AP) information contained in the BGP tables and the vIP2Loc backbone routers, and other synonyms that give a glimpse of list to map intermediate routers (obtained by INLM) to the nature of the host in their domain name. locations. An AP is an aggregate of IP addresses that belong to The INLM algorithm filters out any private IP address an autonomous system, and is recognized by a starting IP denoting an erroneous behavior of the routers, as for example address and a number denoting the range of numbers from it. 10.xx.xx.xx prefixes. This is the minimal information from For example the address prefix 4.0.0.0/16 denotes the 65536 which any name-location mapping process can be carried out IP numbers starting from 4.0.0.0 and ending on 4.0.255.255. ([4, 5]), but not necessarily sufficient. Some hosts cannot be The knowledge of APs enables us to identify clusters; which located or their advertised location in the DNS registers could with high probability constitute geographic clusters, as be wrong [see Zhang]. The next algorithms were devised to observed in [1]. Different than current schemes, we refine and correct the initial DNS-based mapping using a additionally partition each AP (since APs can be widespread verified IP address to location list. over the region of interest) for a more detailed host-location analysis as much as the gathered information permits. 3.2 Host Clustering (HC) 1857-7202/1010006 40 E. Mota-Garcia, R. Hasimoto-Beltran: Fast Geographic Internet Mapping System For Location-Based Services The pseudocode of the HC algorithm is presented in Figure 3. It includes a subroutine called MainBlock responsible for partitioning and locating the AP blocks (main task of HC). MainBlock is divided into two steps. In the first step (lines 18- 21), an Address Prefix to Location list is created by simply analysing the IP addresses in the IP2Loc list using a Consensus Parameter CP (third argument of MainBlock). CP represents the minimum cardinality (in terms of IPs probed) an AP must have to be partitioned. This value is proportional to the total number of IPs to be processed. In the second step (starting at line 23), every single AP found in step one is partitioned (if greater than its corresponding CP value) into m regions with different estimated locations (that is, IP addresses with the same AP can be located in different regions). The borderlines of the m partitions are obtained by taking the average between those IPs producing the minimum magnitude distance between the regions. For example, consider a two- region AP with corresponding values region1 ={ Fig. 4. Representation of the IPDelay scheme. The unlocated node v2 is xxx.xxx.xxx.7, xxx.xxx.xxx.14} and region2 = assigned to the localization of the closest node with respect to the minimum {xxx.xxx.xxx.20, xxx.xxx.xxx.24, xxx.xxx.xxx.28}; the temporal distance between e1, e2 and e3 edges. borderline between these regions becomes xxx.xxx.xxx.17. A node with IP address xxx.xxx.xxx.15 is set to region1. is the set of edges eij ϵ E connecting the nodes vi and vj. This If a single IP address is the only reference for a given AP graph G is constructed using a new topology connection from then the location of this address is directly assigned to the AP. traceroute paths reported from each landmark. MainBlock returns an AP to location list (AP2LocList), which Each edge eij ϵ E has a weight w(i,j) associated with the represents a list of clusters of IPs that may share a common mean RTT reported by traceroute measurements. Let F  E location. be the subset of edges connecting a fixed given unlocated Initially the HC algorithm uses the verified IP to location node vi. Then, list (vIP2loc) in the first call to MainBlock to do an initial vi .Loc  vk .Loc selection of APs, and then uses vIP2Loc plus the INML output with list in the second call to make the partitions. Each call uses different CP values CP1 and CP2 for the initial processing of eik  min {(eij  e ji )  F } w(i , j ) the vIP2loc list and for the processing of the rest of the IPs probed respectively. Given that our confidence in the vIP2loc If we assume the relationship between delay and distance as list is strong (because is a verified mapping list), the value of proportional (at some degree), then a previously not located CP1 must be small in order to maximize the number of node vi has more probability to be located near or in the region segments in the AP. We propose any positive value of CP1 in represented by the node vj. An example of IPDelay is shown in the range [2, CP2 = 5]. If the cardinality of the resulted AP in Figure 4, where v2 represents the unlocated node after steps the second call to MainBlock (after partitioning) is ≥CP2, then INML and HC. After the landmark probing, v2 is assigned to we have enough number of hosts which agree on the same that location with the minimum edge magnitude e; if the location, so it is more likely that all the addresses in the AP arrows are proportional to the magnitude, v2 will be assigned share a common location. to the same location of node v1). Of course, the RTT values The final step in the HC algorithm (lines 8-14) is the between v2 to v1-v3 are affected by the amount of traffic mapping of unlocated IPs in the AP2Loc list by using the new present on each link (the probing phase must avoid peak partitions of the APs. The location given by the HC algorithm traffic hours). is not final, i.e., it can be refined by using delay values as Other schemes in the literature using delay information [1, shown in the next section. 4, and 10] make complete correspondence between delay and geographic distance, assigning geographic location between 3.3 Topology and Delay Location (IPDelay) nodes by road map information. The proposed scheme does For those hosts whose location is still unknown after the not imply any correspondence in this sense, so it does not infer INLM and HC steps, we gather additional host information non-useful information to users (i.e.,”20.1Km from B city”, such as Round-Trip Time (RTT) and host connectivity instead we conclude “in the zone of B city”). After the host (topology) from each landmark. Each unlocated IP address is localization delay refinement, HC is again executed in order to mapped to the closest location reported by the landmarks, in refine the APs partitions and location of the IPs. This is terms of their RTT and topological information. needed because new located IPs are aggregated to the IP2Loc Mathematically, this can be expressed in the following way. list. HC and IPDelay can be iterated until all IPs’ location Let G = (V,E) be a graph where V is the set of nodes vi and E remains unmodified. IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 41 3.3 IP Distance Similarity Location (IPDS) An IP node serving as a router may have an alias or may share two different interfaces. This can be detected using a simple similarity algorithm. In our scheme, an IP address is said to be similar to another if the difference between them is less than 5 units. The addresses 200.52.176.30 and 200.52.176.35 had a similarity index of 5 (the difference between these two IPs is 5 address units); therefore the probability to be in the same geographic location (even in the same building) is high. The similarity value of 5 is chosen following [1] and [6], where they report that there are a high number of virtual router addresses with a mean distance of 3 to 4 units. Another reason is that, in general ISPs assign numerically close IPs to the access points or gateways. Fig. 5. IP topology for the Mexican Territory. We make a single pass of this simple IPDS algorithm to the geographical location of the nodes found during the probing entire IP2Loc list in order to locate those unclassified routers phase (first part). The first part of the execution time lasted 2 from previous steps. hrs for our chosen level of detail, and can be executed once every 15-30 days. The second part is much faster; it takes up IV. DATA SET AND RESULTS to 10 sec to geolocate the complete set of nodes (2 sec on a 4.1 Data Set 2.4Ghz Xeon processor PC with 1GB of RAM). Once the The approach described in previous section is applied for topology has been defined, it takes the order of milliseconds the discovering the Mexican IP topology. Four traceroute (1-10) to geolocate a new input node. With this fast response landmarks and a 64-node HPL table with known IP address to time (1-10 ms), a Content Delivery Network (CDN) can select geographic location mapping were used in the defined region in real-time the closest server to the client’s geographic of interest (at least one node was chosen to be present in each location to be in charge of delivering the requested multimedia Mexican state). As previously stated, the probing landmarks content. do not necessarily need to be spread all over the target region. Figure 5, shows the resulting topology of the proposed In our case, we located two landmarks in the same city. scheme for the Mexican territory. The big dots correspond to The IP addresses in the HPL table were chosen from the inferred backbone nodes, while the small dots correspond to IET-DPEC database system to cover the entire region of cities with an assigned node(s). The upper right dot interest. The IET-DPEC database provides information (up to corresponds to the IP addresses located outside the country, the year 2006) of public schools enrolled in national and the lower left dot corresponds to unlocated IP addresses educational projects. The information is organized by school after processing the entire dataset. For the 4 landmark nodes name, address, teachers information, number of students and the 64 end-nodes used in the test, we found 228 different enrolled in the project and host information (IP address and routes, 589 total routers (after removing duplicates and private domain name). From the verified IP list, 38 IPs (60%) were addresses), from which 430 routers are in the Mexican used in the mapping process (to form the vIP2loc list in the territory, and 118 are located outside the country, but used for HC scheme), and the rest of the IPs were used in the regional traffic. We found 139 routers (out of the 589) verification process (IPDelay scheme). We also use publicly advertised as backbones. 1 summarizes the results of the available Mexican airport codes and well-known state and city mapping process. The error percentage, which represents the acronyms information for the initial phase (INLM step). fraction of addresses incorrectly located, is less than 1%. The For the BGP tables we use the snapshot from Routeviews, unlocated hosts dropped ~10% when using the complete set of which is publicly available [13]. Routeviews is an initiative to algorithms, which is quite good giving that we have such a provide the research community with weekly or monthly small set of addresses. For the mapping of new hosts, the error snapshots of the complete BGP tables shared by AP frontier percentage is around 30% with 4 landmarks (same percentage routers. The BGP tables are filtered out to keep only the than more complex schemes), and decreases as low as 20% available and valid prefixes. when 5 landmarks are used. The error percentage for geolocating new hosts may appear to be high at first sight, but 4.2 Results in fact it is not. We consider an error, when a host A is The proposed system was implemented in C/C++ reported to be in city or state X when actually it is in city or programming language, on a 750Mhz Pentium III class state Y (for X and Y contiguous cities or states), even though processor with 256MB in RAM running Linux 2.6.18- the real geographic position of node A is too close of the 53.1.13.el5 operating system. The execution time of the reported location (we do not set a geographical radius for experiment was divided into 2 parts: a) the time spent on the which our mapping report must fall in or out, in order to be Restricted Probing (traceroute probing and BGP tables considered right or wrong respectively). For the kind of parsing, described in section 3.1), and the time needed for the 1857-7202/1010006 42 E. Mota-Garcia, R. Hasimoto-Beltran: Fast Geographic Internet Mapping System For Location-Based Services applications our scheme is aimed to (efficient delivery of [8] F. Dabek, R. Cox, F. Kaashoek, R. Morris “Vivaldi: a decentralized network coordinate system,” in SIGCOMM ’04: Proceedings of the multimedia content in Content Delivery Networks--CDN), the 2004 Conference on Applications, technologies, architectures, and localization error among contiguous states is not important protocols for Computer Communications. ACM Press, New York, NY, since they may be only few seconds apart in delay units. We USA, pp. 15–26. [9] E. Katz-Bassett, J.P. John, A. Krishnamurthy, D. Wetherall, T. obtained an average distance error between wrong located Anderson, Y. Chawathe, “Towards ip geolocation using delay and nodes <15ms, which is minuscule. topology measurements,” in IMC ’06: Proceedings of the 6th ACM The topology drawn by our scheme was compared with the SIGCOMM on Internet measurement. ACM Press, New York, NY, one obtained in [11]. Our scheme correctly found the USA, 2006, pp. 71–84. [10] B. Gueye, A. Ziviani, M. Crovella, S. Fdida, “Constraint-based backbone location. For a final and more critical evaluation, we geolocation of internet hosts,” in IEEE/ACM Transactions on ran the publicly available reverse tree routine called Networking, 14 (6), 2006, pp.1219–1232. Scriptroute based on Rocketfuel [12], in order to compare the [11] J. Tomasson,, W. Foster, L. Press, “The diffusion of the internet in México,” Tech. Report., in Latin American Network Information Center, location of the connections between hosts in México and hosts University of Texas, 2002. in the United States. Rocketfuel is an ISP topology mapping [12] D. Meyer (2004), Routeviews project. Available: engine, which takes into account around 10 ISPs, in Europe, http://www.routeviews.org. [13] University of Washington (2005), “Rocketfuel maps and data”. Australia, and the United States using around 300 traceroute Avalilable: web servers. A database is then constructed of over 50 http://www.cs.washington.edu/research/networking/rocketfuel. thousand IP addresses representing 45 thousand routers in 537 [14] A-M. Khan-Pathan, Utility-Oriented Internetworking of Content Delivery Networks. Department of Computer Science and Software POPs connected by 80 thousand links. Our scheme, with only Engineering, The University of Melbourne, Australia. Ph.D Thesis, 38 nodes in the area of interest correctly located the backbone 2009. http://www.cloudbus.org/students/MukaddimPhDThesis2009.pdf connection points reported by Scriptroute in about 2 hrs [15] M. Zhang, Y. Ruan, V. Pia, J. Rexford, How DNS Misnaming Distorts Internet Topology Mapping. Proceedings of the annual conference on without going through any ISP analysis. A valuable asset of USENIX '06 Annual Technical Conference, 2006. our scheme, in addition to its fast response and accuracy is its independency of any ISP topological analysis in the region of interest. We would like to point out as well, that despite of the TABLE I. Percentage results obtained by the application of the different algorithms. Basic implies the use of INLM and HC phases only. small database use in our experiment, our error is equivalent to Scriptroute using thousand of hosts. Basic Basic + Basic + Full (%) IPDelay IPDS Scheme V. CONCLUSIONS (%) (%) (%) This paper is a first attempt to provide fast, simple, Located 65.42 65.57 70.4 71.65 effective, and ISP independent scheme for solving the IP to In Region location problem over the public Internet. We proved that with Located a simple scheme and a small input dataset (38 distinct IP Out of 16.97 18.32 21.65 21.5 addresses) it is possible to get a very good approximation of Region the Internet topology in a specified region of interest, for the Unlocated 17.6 16.04 7.94 6.85 mapping of new hosts. Our scheme is independent of any ISP Wrongly 0.5 0.5 0.6 0.7 topological analysis, and its mapping accuracy is scalable Located according to the number of nodes in the initial database table. REFERENCES M.C. Edmar Mota- Garcia received his [1] V. N. Padmanabhan, L. Subramanian, “An investigation of geographic mapping techniques for internet hosts,” in SIGCOMM ’01: Proceedings bachelor degree in Civil of the 2001 Conference on Applications, technologies, architectures, and Engineering from the protocols for computer communications. ACM Press, New York, NY, Department of USA, pp. 173–185. Engineering-Autonomous [2] J. Apostolopoulos, “Reliable video communication over lossy packet networks using multiple state encoding and path diversity,” in University of Sinaloa, Proceedings of the Visual Communication and Image Processing, VCIP México in 1999 and the 2001, pp. 392–409. M.S. in computer science [3] Inc., M. (January 2008), Geoip. Available: www.maxmind.com. and industrial mathematics from the Center for Research in [4] R. Govindan, H. Tangmunarunki, “Heuristics for internet map discovery,” in IEEE INFOCOM 2000. Mathematics (CIMAT) in Guanajuato, México in 2002. He is [5] N. Spring, Mahajan, R., D. Wetherall, T. Anderson, “Measuring ISP Ph.D. candidate from CIMAT. topologies with rocketfuel,” in IEEE/ACM Transactions on Networking He joined the Department of Education Technology of the 2004, 12 (1), pp.2–16. Education and Culture Ministry of Sinaloa, México (SEPyC), [6] R. Teixeira, K. Marzullo, S. Savage, G. M. Voelker, “In search of path diversity in isp networks,” in Proceedings of the 3rd ACM SIGCOMM where he leads the applications of Robotics in Middle conference on Internet measurement IMC ’2003. ACM Press, New Education Programs and the Local State wide Internet York, NY, USA, pp. 313–318. platform of Digital Abilities for Everyone (HDT). He is part [7] P. Francis, S. Jamin, C. Jin, Y. Jin, D. Raz, Y. Shavitt, L. Zhang, of Sinaloa State Council for Research and Technology “Idmaps: a global internet host distance estimation service,” in IEEE/ACM Transactions on Networking, 2001 9 (5), 525–540. (CECyT), which provides master degree courses on Multimedia, Technology in Education and Problem Solving. IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 43 Rogelio Hasimoto-Beltran received his M.S. in Computer Science from the Scientific Research Center and Higher Education of Ensenada (CICESE), México, in 1990, and Ph.D. from the University of Delaware, USA, in 2001. After his Ph.D., he spent two years as a Senior Software Engineer in the Streaming Group at Akamai Technologies in San Mateo, CA, USA. Since 2003 he serves as a Research Fellow in the Department of Computer Science at the Center for Research in Mathematics (CIMAT), México, conducting research on image/video processing and compression, robust multimedia transmission, biometric systems and multimedia encryption based on chaos. During August/2009-July/2010 he was Visiting Associate Professor in the Department of electrical and Computer Engineering at University of Illinois in Chicago (UIC). Dr. Hasimoto is member of the IEEE association. 1857-7202/1010006 IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 45 On Fixed Point Theorems in Fuzzy Metric Spaces Rajesh Kumar Mishra†, Sanjay Choudhary‡ Abstract: This paper presents some common fixed point following conditions, for all x, y, z  X, such that t is in theorems for occasionally weakly compatible mappings in [0, ] fuzzy metric spaces under various conditions. (f1) M(x, y, t) > 0; Index Terms: Occasionally weakly compatible mappings, fuzzy metric space. (f2) M(x, y, t) = 1 if and only if x = y (f3) M(x, y, t) = M(y, x, t); I. INTRODUCTION (f4) M(x, y, t) *M(y, z, s) M(x, z, t + s); Fuzzy set was defined by Zadeh [24]. Kramosil and (f5) M(x, y, * ) : (0,)  (0, 1] is continuous. Michalek [12] introduced fuzzy metric space, George and Then M is called a fuzzy metric on X. Then Veermani [4] modified the notion of fuzzy metric spaces M(x, y, t) denotes the degree of nearness between x and y with the help of continuous t-norms. Many researchers have with respect to t. obtained common fixed point theorems for mappings Definition 1.4 [4]: Let (X,M, *) be a fuzzy metric space. satisfying different types of commutativity conditions. Then Vasuki [23] proved fixed point theorems for R weakly (a) a sequence {xn} in X is said to converges to x in X if for commutating mappings. Pant [16, 17,18] introduced the each  > 0 and each t > 0, there exists n0 N such that new concept reciprocally continuous mappings and M(xn, x, t) > 1 − for all n ≥ n0. established some common fixed point theorems. (b) a sequence {xn} in X is said to be Cauchy if for each  > Balasubramaniam et al.[2], have shown that Rhoades [20] 0 and each t > 0,there exists n0  N such that M(xn, xm, t) > open problem on the existence of contractive definition 1 −  ,  n, m ≥ n0. which generates a fixed point but does not force the (c) A fuzzy metric space in which every Cauchy sequence mappings to be continuous at the fixed point, posses an is convergent is said to be complete. affirmative answer. Pant and Jha [18] obtained some Definition 1.5 [23] A pair of self-mappings (f, g) of a fuzzy analogous results proved by Balasubramaniam et al. Recent metric space (X,M, *) is said to be literature on fixed point in fuzzy metric space can be (i) weakly commuting if viewed in [7, 14, 22]. This paper presents some common M(fgx, gfx, t) ≥ M(fx, gx, t)  x  X & t > 0. fixed point theorems for more general commutative (ii) R-weakly commuting if there exists some R > 0 such condition i.e. occasionally weakly compatible mappings in that M(fgx, gfx,t) ≥ M(fx, gx, t/R) x  X and t > 0. fuzzy metric space. Before giving the results, some Definition 1.6 [11] Two self mappings f and g of a fuzzy preliminary definitions are given below. metric space (X,M, *) are called compatible if Definition 1.1 [24] A fuzzy set A in X is a function with lim M(fgxn, gfxn, t) = 1 domain X and values in [0, 1] n Definition 1.2 [21] A binary operation * : [0, 1] × [0, 1]  whenever {xn} is a sequence in X such that [0, 1] is a continuous t-norms if * is satisfying conditions: lim fxn = lim g xn = x for some x in X. (i) * is an commutative and associative; n n (ii) * is continuous; Definition 1.7 [5]: Two self maps f and g of a fuzzy metric (iii) a * 1 = a for all a  [0, 1]; space (X,M, *) are called reciprocally continuous on X if (iv) a * b  c * d whenever a  c and b  d, and a, b, c, d lim fgxn = fx and lim gfxn = gx  [0, 1]. n n Definition 1.3 [4] A 3-tuple (X,M, *) is said to be a fuzzy whenever {xn} is a sequence in X such that metric space if X is an arbitrary set, * is a continuous t- lim fxn = lim gxn = x for some x in X. norm and M is a fuzzy set on X2 × [0, ] satisfying the n n Definition 1.8 Let X be a set, f, g selfmaps of X. A point x in X is called a coincidence point of f and g iff fx = gx. We Manuscript received October 31, 2010. ‡ Rajesh Kumar Mishra is with the Bhabha Engineering Research shall call w = fx = gx a point of coincidence of f and g. Institute, Bhopal, India. (corresponding author e-mail: Definition 1.9 [11] A pair of maps S and T is called weakly

). † compatible pair if they commute at coincidence points. Sanjay Choudhary is with the Govt. Narmada P.G.College, Definition 1.10 Two self maps f and g of a set X are Hoshangabad, Madhya Pradesh, India. occasionally weakly compatible (owc) iff there is a point x 1857-7202/1010005 46 R. K. MISHRA, S. CHOUDHARY: On Fixed Point Theorems in Fuzzy Metric Spaces in X which is a coincidence point of f and g at which f and for all x, y  X and  : [0, 1] [0, 1] such that  (t) > t for g commute. all 0 < t < 1, then there exists a unique common fixed point A. Al-Thagafi and Naseer Shahzad [1] have shown that of A, B, S and T. occasionally weakly is weakly compatible but converse is Proof 2.2: The proof follows from Theorem 2.1. not true. Theorem 2.3 Let (X,M, *) be a complete fuzzy metric Example 1.11 [1] Let R be the usual metric space. Define space and let A,B, S and T be self-mappings of X. Let the S, T : R  R by Sx = 3x and Tx = x2 for all x  R. Then Sx pairs {A, S} and {B, T} be owc. If If there exists q  (0, 1) = Tx for x = 0, 3 but ST0 = TS0, and ST3 ≠ TS3. S and T such that are occasionally weakly compatible self maps but not M(Ax,By,qt)≥{ M(Sx,Ty,t), M(Sx,Ax,t), M(By,Ty,t), weakly compatible. [M(Ax,Ty,t)+M(By,Sx,t)]/2 Lemma 1.12 [10] Let X be a set, f, g owc self maps of X. If , M(By,Sx, t)}…………………………….(3) f and g have a unique point of coincidence, w = fx = gx, for all x, y  X and : [0, 1]5  [0, 1] such that  (t, 1, 1, then w is the unique common fixed point of f and g. t, t) > t for all 0 < t < 1, then there exists a unique common Main Results fixed point of A,B, S and T. Theorem 2.1 Let (X,M, *) be a complete fuzzy metric Proof: Let the pairs {A, S} and {B, T} are owc, there are space and let A,B, S and T be self-mappings of X. Let the points x, y  X such that Ax = Sx and By = Ty. We claim pairs {A, S} and {B, T} be owc. If there exists q  (0,1) that Ax = By. By inequality (3) we have such that M(Ax,By,qt) ≥ {M(Sx,Ty,t), M(Sx,Ax,t), M(By,Ty,t), M(Ax,By,qt)≥min{M(Sx,Ty,t), M(Sx,Ax,t), M(By,Ty,t), [M(Ax,Ty,t)+M(By,Sx,t)]/2 [M(Ax,Ty,t)+M(By,Sx,t)]/2}……..……(1) , M(By,Sx, t)} for all x, y  X and for all t > 0, then there exists a unique = (M(Ax,By,t), M(Ax,Ax,t), M(By,By,t), point w  X [M(Ax,By,t)+M(By, Ax, t)]/2, such that Aw = Sw = w and a unique point z  X such that M(By, Ax, t)} Bz = Tz = z. Moreover, z = w, so that there is a unique = {(M(Ax, y,t),1,1,M(Ax,By, t)} common fixed point of A,B, S and T. > M(Ax,By, t). Proof 2.1: Let the pairs {A, S} and {B, T} be owc, so there a contradiction, therefore Ax = By, i.e. Ax = Sx = By = Ty. are points x, y  X Suppose that there is a another point z such that Az = Sz such that Ax = Sx and By = Ty. We claim that Ax = By. If then by (3) we have Az = Sz = = Ty, so Ax = Az and w = not, by inequality (1) Ax = Tx is the unique point of coincidence of A and T. By M(Ax,By, qt) ≥ min{M(Sx, Ty, t), Lemma 1.12 w is a unique common fixed point of A and S. M(Sx, Ax, t),M(By, Ty, t), Similarly there is a unique point z  X such that z = Bz = [M(Ax, Ty, t)+M(By, Sx, t)]/2} Tz. Thus z is a common fixed point of A, B, S and T. The = min{M(Ax,By,t),M(Ax,Ax,t), M(By,By,t), uniqueness of the fixed point holds from (3). ,[M(Ax,By, t)+M(By, Ax, t)]/2} = M(Ax,By, t). REFERENCES Therefore Ax = By, i.e. Ax = Sx = By = Ty. [1] A. Al-Thagafi and Naseer Shahzad, Generalized I- Non expansive Suppose that there is a another point z such that Az = Sz Selfmaps And Invariant Approximations, Acta Mathematica Sinica, English Series May, 2008, Vol. 24, No. 5, pp. 867876. then by (1) we have Az = Sz = By = Ty, so Ax = Az and w [2] P. Balasubramaniam, S. Muralisankar, R.P. Pant, ”Common fixed = Ax = Sx is the unique point of coincidence of A and S. points of four mappings in a fuzzy metric space”, J. Fuzzy Math. 10(2) By Lemma 1.12: w is the only common fixed point of A (2002),379-384. and S. Similarly there is a unique point z X such that z = [3] Y.J. Cho, H.K. Pathak, S.M. Kang, J.S. Jung, ”Common fixed points of compatible maps of type (A) on fuzzy metric spaces”, Fuzzy Sets and Bz = Tz. Assume that w ≠ z. We have Systems 93 (1998), 99-111. M(w,z, qt) = [4] A. George, P. Veeramani, ”On some results in fuzzy metric spaces”, M(Aw,Bz,qt)≥ min{M(Sw,Tz,t),M(Sw,Az,t), Fuzzy Sets and Systems, 64 (1994), 395-399. M(Bz,Tz,t), [5] M.Grabiec,”Fixed points in fuzzy metric spaces”,Fuzzy Sets and Systems 27(1988), 385-389. [M(Aw,Tz,t)+M(Bz,Sw, t)]/2} [6]O.Hadzic, ”Common fixed point theorems for families of mapping in =min{M(w, z, t),M(w, z, t), complete metric space”, Math. Japon. 29 (1984), 127-134. M(z, z, t), [7] Mohd. Imdad and Javid Ali, ”Some common fixed point theorems in [M(w, z, t)+M(z,w, t)]/2} fuzzy metric spaces”, Mathematical Communications 11(2006), 153-163 [8] G. Jungck, ”Compatible mappings and common fixed points (2)”, = M(w, z, t) Internat. J. Math. Math. Sci. (1988), 285-288. Therefore we have z = w by Lemma 1.12 and z is a [9] G. Jungck and B. E. Rhoades, ”Fixed Point for Set Valued functions common fixed point of A,B, S and T. The uniqueness of the without Continuity”, Indian J. Pure Appl. Math., 29(3), (1998), pp.771- fixed point holds from (1). 779. [11] G. Jungck and B. E. Rhoades, ”Fixed Point Theorems for Theorem 2.2 let (X,M, *) be a complete fuzzy metric space Occasionally Weakly compatible Mappings”, Fixed Point Theory, Volume and let A,B, S and T be self-mappings of X. Let the pairs 7, No. 2,2006, 287-296. {A, S} and {B, T} be owc. If there exists q  (0, 1) such [11] G. Jungck and B. E. Rhoades, ”Fixed Point Theorems for that Occasionally Weakly compatible Mappings”, Erratum, Fixed Point Theory, Volume 9,No. 1, 2008, 383-384. M(Ax,By,qt) ≥ (min{M(Sx,Ty,t),M(Sx,Ax,t), M(By, Ty, [12] O. Kramosil and J.Michalek, ”Fuzzy metric and statistical metric t), [M(Ax,Ty,t)+M(By,Sx,t)/2}……….(2) spaces”,Kybernetika, 11 (1975), 326-334. IMACST: VOLUME 1 NUMBER 1 DECEMBER 2010 47 [14] S. Kutukcu, ”A fixed point theorem for contraction type mappings in Menger spaces”, Am.J.Appl.Sci.4(6) (2007),371-373. [15] Servet Kutukcu, Sushil Sharma1 and Hanifi Tokgoz, ”A Fixed Point Theorem in Fuzzy Metric Spaces”, Int. Journal of Math. Analysis, Vol. 1,2007, no. 18, 861 - 872. [16] S.N. Mishra, ”Common fixed points of compatible mappings in PM spaces”,Math. Japon. 36 (1991), 283-289. [17] R.P. Pant, ”Common fixed points of four mappings”, Bull. Cal. Math.Soc. 90 (1998), 281-286. [18]R.P. Pant, ”Common fixed point theorems for contractive maps”, J. Math.Anal. Appl. 226 (1998), 251-258. [21] R.P. Pant, K. Jha, ”A remark on common fixed points of four mappings in a fuzzy metric space”, J. Fuzzy Math. 12(2) (2004), 433-437. [22] H. K.Pathak and Prachi Singh, ”Common Fixed Point Theorem for Weakly Compatible Mapping ”, International Mathematical Forum, 2,2007, no. 57, 2831 - 2839. [23] B.E. Rhoades, ”Contractive definitions and continuity”, Contemporary Math. 72 (1988), 233-245. [24] B. Schweizer and A. Sklar, ”Statistical metric spaces”, Pacific J. Math.10(1960), 313-334. [25] Seong Hoon Cho, ”On common fixed point in fuzzy metric space”, Int.Math. Forum, 1, 2006, 10, 471-479. [26] R. Vasuki, Common fixed points for R-weakly commuting maps in fuzzy metric spaces, Indian J. Pure Appl. Math. 30 (1999), 419-423. [27] L.A. Zadeh, Fuzzy sets, Inform and Control 8 (1965), 338-353. Rajesh Kumar Mishra, Assist. Prof & Head of Department of Engineering Mathematics, Bhabha Engineering Research Institute, Bhopal. He did his graduation in Mathematics from Barkatullah University, Bhopal and Post Graduation from same university in 1986. He also did M.Phil from Madurai Kamraj University in year 2007. His field of interest is Non linear analysis and Topology. Dr. Sanjay Choudhary, Head of Department of Mathematics, Govt. Narmada P.G.College, Hoshangabad, Madhya Pradesh, India. He did Post graduation in year 1984 from Barkatullah University, BHOPAL (MP) India. He completed his research work in field of Non linear analysis and awarded Ph.D from Barkatullah University, BHOPAL (MP) India in year 2003. 1857-7202/1010005 International Magazine on Advances in Computer Science and Telecommunications Published by the Association for Computer Science and Telecommunications AKOMNAT TEL DOO IMACST 1 (1) 1-47 (2010) ISSN 1857-7202 www.imacst.com