TAILIEUCHUNG - 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 .

Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.