The algebraic path problem is a generalization of the shortest path problem in graphs. Various instances of this abstract problem have appeared in the literature, and similar solutions have been independently discovered and rediscovered. The repeated appearance of a problem is evidence of its relevance. This book aims to help current and future researchers add this powerful tool to their arsenal, so that they can easily identify and use it in their own work. Path problems in networks can be conceptually divided into two parts: A distillation of the extensive theory behind the algebraic path problem, and an exposition of a broad range of applications. First of all, the shortest path problem is presented so as to fix terminology and concepts: existence and uniqueness of solutions, robustness to parameter changes, and centralized and distributed computation algorithms. Then, these concepts are generalized to the algebraic context of semirings. Methods for creating new semirings, useful for modeling new problems, are provided. A large part of the book is then devoted to numerous applications of the algebraic path problem, ranging from mobile network routing to BGP routing to social networks. These applications show what kind of problems can be modeled as algebraic path problems; they also serve as examples on how to go about modeling new problems. This monograph will be useful to network researchers, engineers, and graduate students. It can be used either as an introduction to the topic, or as a quick reference to the theoretical facts, algorithms, and application examples. The theoretical background assumed for the reader is that of a graduate or advanced undergraduate student in computer science or engineering. Some familiarity with algebra and algorithms is helpful, but not necessary. Algebra, in particular, is used as a convenient and concise language to describe problems that are essentially combinatorial. Table of Contents: Classical Shortest Path / The Algebraic Path Problem / Properties and Computation of Solutions / Applications / Related Areas / List of Semirings and Applications
Author(s): John Baras, George Theodorakopoulos, Jean Walrand
Edition: 1
Publisher: Morgan & Claypool Publishers
Year: 2010
Language: English
Pages: 80
Preface......Page 11
Graph Theory......Page 13
The shortest path problem......Page 14
Dijkstra......Page 15
Bellman-Ford......Page 16
Distributed computation of shortest paths......Page 17
Distributed Bellman-Ford......Page 18
Semirings and the Algebraic Path Problem......Page 21
Why semirings?......Page 22
Ordered semirings......Page 23
Creating new semirings......Page 24
Convolution......Page 25
Semirings of Endomorphisms......Page 26
Alternative viewpoints: paths and matrices......Page 29
Existence of A*......Page 30
Edge sensitivities......Page 31
Generalization of Dijkstra......Page 34
Formal model of the Distributed Algebraic Path Problem......Page 35
Conditions for the convergence of the distributed computation......Page 36
Conditions for convergence in dioids......Page 37
Path enumeration......Page 39
Expectation Semirings......Page 40
Minimum Weight Spanning Tree......Page 41
Quality of Service (QoS) routing......Page 42
BGP routing......Page 43
Shortest path with time-inhomogeneous edges......Page 45
Deterministic failures......Page 46
Probabilistic failures......Page 47
Shortest paths with gains/losses on the edges......Page 48
Trust-reputation......Page 49
Distance semiring......Page 50
PGP trust computation model......Page 51
EigenTrust......Page 52
Social networks......Page 53
Cluster Semiring......Page 54
Geosetic semiring......Page 55
Traffic Assignment......Page 57
Traffic Redirection Attacks......Page 59
Non-semiring path problems......Page 63
Semirings as an algebra for combinatorics......Page 65
Network Calculus......Page 66
List of Semirings and Applications......Page 69
Bibliography......Page 73
Authors' Biographies......Page 77
