Networking Theory and Fundamentals - Lecture 11

Tham khảo tài liệu 'networking theory and fundamentals - lecture 11', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Networking Theory and Fundamentals - Lecture 11 TCOM 501: Networking Theory & Fundamentals Lecture 11 April 16, 2003 Prof. Yannis A. Korilis 1 Topics 2 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 Introduction to Routing 3 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? E A How to reach B? How to best reach B? D C G How to best distribute all traffic (not only A to B)? B F Graph-Theoretic Concepts 4 An Undirected Graph G = (N, A) consists of: a finite nonempty set of nodes N and a collection of “arcs” A, interconnecting pairs E A of distinct nodes from N. If i and j are nodes in N and (i, j) is an arc in D C 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 B F 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 Spanning Tree 5 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 E A D C G B F 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 arc (i, j) such that i∈S, and j∉S. Spanning Tree Algorithm 6 Select arbitrary node n∈N, and initialize: G' = (N ', A' ), 1. N ′ = {n}, A ′ = ∅ If N' = N, STOP: G' = (N ', A' ) is a spanning tree 2. ELSE: go to step 3 Let (i, j) ∈ A with i ∈ N' and j ∈ N - N' 3. Update: N ′ := N ′ ∪ { j}, A ′ := A ′ ∪ {(i, j )} Go to step 2 Proof of correctness: Use induction to establish that after a new node i is added, G' remains connected and does not contain any cycles – therefore, it is a tree. After N-1 iterations, the algorithm terminates, and G' contains N nodes and N-1 arcs. Construction of a Spanning Tree 7 N' = {A}; A' = ∅ N' = {A,E}; A' = {(A,E)} N' = {A,E,C}; E A A' = {(A,E),(A,C)} N' = {A,E,C,D}; D C G A' = {(A,E),(A,C),(CD)} N' = {A,E,C,D,F}; A' = {(A,E),(A,C),(CD),(CF)} B F N' = {A,E,C,D,F,B}; A' = {(A,E),(A,C),(CD),(CF),(F,B)} N' = {A,E,C,D,F,B,G}; A' = {(A,E),(A,C),(CD),(CF),(F,B),(E,G)} Spanning Trees 8 Proposition: Let G be a connected graph with N nodes and A links G contains a spanning tree 1. A ≥ N-1 2. G is a tree if and only if A=N-1 3. Proof: The spanning tree construction algorithm starts with a single node and at each iteration augments the tree by one node and one arc. Therefore, the tree is constructed after N-1 iterations and has N-1 links. Evidently A ≥ N-1. If A=N-1, the spanning tree includes all arcs of G, thus G is a tree. If A>N-1, there is a link (i, j) that does not belong to the tree. Considering the path connecting nodes i and j along the spanning tree, that path and link (i, j) form a cycle, thus G is not a tree. Use of Spanning Trees 9 Problem: how to distribute information to all nodes in a graph (network) – e.g., address and topology information Flooding: each node forwards information to all its neighbors. Simple, but multiple copies of the same packet traverse each link and are received by each node Spanning tree: nodes forward information only along links that belong to the spanning tree. More efficient: Information reaches each node ...