nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

Distributed Graph Algorithms for Computer Networks

verfasst von: K. Erciyes

Verlag: Springer London

Buchreihe : Computer Communications and Networks

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book presents a comprehensive review of key distributed graph algorithms for computer network applications, with a particular emphasis on practical implementation. Topics and features: introduces a range of fundamental graph algorithms, covering spanning trees, graph traversal algorithms, routing algorithms, and self-stabilization; reviews graph-theoretical distributed approximation algorithms with applications in ad hoc wireless networks; describes in detail the implementation of each algorithm, with extensive use of supporting examples, and discusses their concrete network applications; examines key graph-theoretical algorithm concepts, such as dominating sets, and parameters for mobility and energy levels of nodes in wireless ad hoc networks, and provides a contemporary survey of each topic; presents a simple simulator, developed to run distributed algorithms; provides practical exercises at the end of each chapter.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

A distributed system consists of a set of computational nodes connected by a communication network that cooperate to accomplish common tasks. In this chapter, we will review the benefits of using a distributed system, the architecture of a distributed system, and the challenges facing the designers.

K. Erciyes

Fundamental Algorithms

Frontmatter

Chapter 2. Graphs

Abstract

Graphs are discrete structures that consist of vertices and edges connecting some of these vertices. Graphs have many applications in Mathematics, Computer Science, Engineering, Bioinformatics, and many other disciplines. Graphs are frequently used to model a communication network where computational nodes of a network are represented by vertices and the communication links between the nodes are represented by edges of the graph. In this chapter, we will review basic concepts in graph theory in relation to the modeling of a distributed system.

K. Erciyes

Chapter 3. The Computational Model

Abstract

In this chapter, we investigate how to model the application software, namely the distributed algorithm, the middleware, and the network that delivers the messages between the nodes of the distributed system.

K. Erciyes

Chapter 4. Spanning Tree Construction

Abstract

Spanning trees have many applications in computer networks as they provide a subgraph of less number of links than the original network resulting in lowered communications. This chapter introduces the basic distributed algorithms to construct spanning trees of graphs without any particular optimization objective.

K. Erciyes

Chapter 5. Graph Traversals

Abstract

This chapter introduces the basic distributed algorithms for breadth first search and depth first search in a graph. A spanning tree of the graph is formed after the execution of both algorithms.

K. Erciyes

Chapter 6. Minimum Spanning Trees

Abstract

A minimum spanning tree of a weighted graph is its spanning tree T with a minimum total cost of edges in T of all possible spanning trees. Minimum spanning trees have many applications in computer networks. In this chapter, we investigate synchronous and asynchronous distributed algorithms to construct minimum spanning trees.

K. Erciyes

Chapter 7. Routing

Abstract

Routing in a computer network is the process of communicating messages from source nodes to destination nodes along selected paths with the lowest possible costs. This chapter introduces few sample distributed routing algorithms based on sequential routing algorithms.

K. Erciyes

Chapter 8. Self-Stabilization

Abstract

A distributed algorithm is self-stabilizing if starting from any state, it eventually reaches an allowed (legal) state. A self-stabilizing system running self-stabilizing algorithms recovers from faults and, once recovered, stays recovered. Self-stabilizing algorithms typically run in background and never stop. In this chapter, we review basic self-stabilization concepts and analyze BFS and DFS self-stabilizing algorithms.

K. Erciyes

Graph Theoretical Algorithms

Frontmatter

Chapter 9. Vertex Coloring

Abstract

Vertex coloring is an assignment of colors to the vertices of a graph such that there are no two neighbor nodes having the same color. Vertex coloring has many applications such as task scheduling, register allocation, and channel frequency assignment. In this chapter, we investigate distributed vertex coloring algorithms for arbitrary graphs and trees.

K. Erciyes

Chapter 10. Maximal Independent Sets

Abstract

An independent set of a graph is a subset of its vertices such that there are not any two adjacent vertices in this set. Finding the maximal independent set of a graph has many important applications such as clustering in wireless networks, and independent sets can also be used to build other graph structures. In this chapter, we describe rank-based, randomized, and self-stabilizing distributed algorithms to form maximal independent sets of graphs.

K. Erciyes

Chapter 11. Dominating Sets

Abstract

A subset of the vertices of a graph is a dominating set if every vertex not in the subset is adjacent to at least one vertex in this subset. Dominating sets are widely used for clustering and routing in ad hoc wireless networks. In this chapter, we describe sample sequential, distributed, and self-stabilizing dominating set algorithms.

K. Erciyes

Chapter 12. Matching

Abstract

A matching M of a graph G(V,E) is a subset of its edges such that no two edges in M have common endpoints. Matching is a fundamental problem in graph theory, and although there are many sequential algorithms for matching, the distributed algorithms have begun to receive attention recently due to many applications of matchings in distributed systems such as mobile and sensor networks. Matching algorithms in distributed systems may also be the building blocks for other algorithms or protocols. In this chapter, we describe sample distributed algorithms for matching in graphs.

K. Erciyes

Chapter 13. Vertex Cover

Abstract

A vertex cover of a graph is a subset of its vertices such that at least one endpoint of every edge is incident to a vertex in this set. Vertex cover has many important applications such as facility location and monitoring link failures and placement of routers or agents in a computer network so that every node can be attached to a router or an agent. In this chapter, we will describe sequential and basic distributed algorithms for vertex covering.

K. Erciyes

Ad Hoc Wireless Networks

Frontmatter

Chapter 14. Introduction

Abstract

Ad hoc wireless networks communicate over wireless links without a fixed communication structure. As they can be deployed easily and quickly, these networks have many applications such as tactical operations, monitoring, military networks, and rescue operations. In this chapter, we investigate the basic principles, design issues, and modeling and simulation of important types of ad hoc wireless networks.

K. Erciyes

Chapter 15. Topology Control

Abstract

Topology control in ad hoc wireless networks aims to provide a sparser graph by preventing the use some of the existing communication links so that some of the neighbors of a node are excluded from its neighbor list deliberately, which would result in a simpler network graph. A hierarchical network structure is an effective way to organize a network comprising a large number of nodes. An efficient method of providing hierarchy and therefore scalability in ad hoc wireless networks is to group nodes of the network into clusters. Building such a hierarchy has many advantages including routing and load balancing. An efficient way of constructing a backbone and clusters is graph domination. In this chapter, we examine methods to construct sparse graphs, called local graphs, clustering, and the use of connected dominating sets for topology control.

K. Erciyes

Chapter 16. Ad Hoc Routing

Abstract

Routing is the process of deciding on the optimal route between a source node and destination node in a network. A routing protocol is a collection of algorithms and procedures to perform routing. We have already investigated distributed routing algorithms in wired computer networks. Our focus in this chapter is on the routing protocols rather than algorithms for wireless ad hoc networks, and we will see that the routing in such networks have different requirements due to the mobility and energy limitations of the nodes.

K. Erciyes

Chapter 17. Sensor Network Applications

Abstract

Localization is the method of providing the coordinates of sensors in 2-D plane so that these coordinates may be attributed to the sensed data to make it more meaningful and also network protocols such as routing may use this information. An important application of sensor networks is the tracking of mobile objects in the area of deployment to determine their trajectory. In this chapter, we first investigate methods to solve the localization problem and then describe few algorithms to track objects efficiently in sensor networks where distributed graph algorithms such as clustering and tree construction can be used for real-life applications.

K. Erciyes

Chapter 18. ASSIST: A Simulator to Develop Distributed Algorithms

Abstract

We describe a simple simulator, called ASSIST, based on POSIX threads to develop distributed algorithms in this chapter. ASSIST is easy to learn and implement and can be used to test and verify distributed algorithms.

K. Erciyes

Backmatter

Titel: Distributed Graph Algorithms for Computer Networks
verfasst von: K. Erciyes
Verlag: Springer London
Electronic ISBN: 978-1-4471-5173-9
Print ISBN: 978-1-4471-5172-2
DOI: https://doi.org/10.1007/978-1-4471-5173-9