tailieunhanh - Lecture Networking theory & fundamentals - Chapter 11

The following will be discussed in this chapter: Routing in data network, graph representation of a network, undirected graphs, spanning trees and minimum weight spanning trees, directed graphs, shortest-path algorithms, distributed asynchronous bellman-ford algorithm. | Lecture Networking theory & fundamentals - Chapter 11 TCOM 501: Networking Theory & Fundamentals Lecture 11 April 16, 2003 Prof. Yannis A. Korilis 1 2 Topics Routing in Data Network Graph Representation of a Network Undirected Graphs Spanning Trees and Minimum Weight Spanning Trees Directed Graphs Shortest-Path Algorithms: Bellman-Ford Dijkstra Floyd-Warshall Distributed Asynchronous Bellman-Ford Algorithm 3 Introduction to Routing What is routing? The creation of (state) information in the network to enable efficient delivery of packets to their intended destination Two main components Information acquisition: Topology, addresses Information usage: Computing “good” paths to all destinations Questions Where is B? A E How to reach B? How to best reach B? How to best distribute all traffic C D G (not only A to B)? F B 4 Graph-Theoretic Concepts An Undirected Graph G = (N, A) consists of: a finite nonempty set of nodes N and a collection of “arcs” A, interconnecting pairs A E of distinct nodes from N. If i and j are nodes in N and (i, j) is an arc in C D G A, the arc is said to be incident on i and j Walk: sequence of nodes (n1, n2, , nk), where (n1, n2), (n2, n3), , (nk-1, nk) are arcs F B Path: a walk with no repeated nodes N = { A, B, C , D, E , F , G} Cycle: a walk (n1, n2, , nk), with n1=nk and A = {( A, E ),( A, C ),(C , D ),(C , F ), no other repeated nodes ( B, D ),( B, G ),( E , G )} Connected Graph: for all i, j∈ N, there exists a path (n1, n2, , nk), with i=n1, j=nk 5 Spanning Tree A graph G' = (N ', A' ), with N '⊆ N and A'⊆ A is called a subgraph of G Tree: a connected graph that contains no cycles Spanning tree of a graph G: a subgraph of G, that is a tree and contains all nodes of G, that is N ' = N A E C D G F B Lemma: Let G be a connected graph G = (N, A) and S a nonempty strict subset of the set of nodes N. Then, there exists at least one .