Survivability and Traffic Grooming in WDM Optical Networks
Providing detailed coverage of key issues in modern optical networks, this highly useful book provides a framework for dealing with survivability and traffic grooming in wide-area networks.
TABLE OF CONTENTS Survivability and Traffic Grooming in WDM Optical Networks
Appendix 4: Graph Algorithms
Once we select the graph model of a network, various algorithms can be used to efficiently design and analyze a network architecture. Some of the most fundamental algorithms among them are finding trees in a graph with minimum cost (where cost is defined appropriately) or finding a minimum spanning tree, visiting nodes of a tree in a specific order, finding connected components of a graph, finding the shortest paths from a node to another node, from a node to all nodes, and from all nodes to all nodes in a distributed or centralized fashion, and assigning flows on various links for a given traffic matrix.
In the following we describe some useful graph algorithms that are important in network design. Recall that N represents the number of nodes and M represents the number of links in the graph.
A4.1 Shortest-Path Routing
Shortest-path routing, as the name suggests, finds a path of the shortest length in the network from a source to a destination [19, 73, 224, 241, 249]. This path may be computed statically for the given graph regardless of the resources being used (or assuming that all resources are available to set up that path). In that case, if at a given moment all resources on that path are in use then the request to set a path between the given pair is blocked. On the other hand, the path may be computed for the graph of available resources. This will be a reduced graph that is...
Copyright Cambridge University Press 2005 under license agreement with Books24x7
