• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Algorithmic performance of large-scale distributed networks: A spectral method approach

    Thumbnail
    View/Open
    gkantsidis_christos_200605_phd.pdf (1.230Mb)
    Date
    2005-12-09
    Author
    Gkantsidis, Christos
    Metadata
    Show full item record
    Abstract
    Complex networks like the Internet, peer-to-peer systems, and emerging sensor and ad-hoc networks are large distributed decentralized communication systems arising repeatedly in today's technology. In such networks it is critical to characterize network performance as the size of the network scales. The focus of my work is to relate basic network performance metrics to structural characteristics of underlying network topologies, and to develop protocols that reinforce and exploit desired structural characteristics. For the case of the Internet at the Autonomous System level, we relate the graph theoretic notions of conductance and spectrum to network clustering and network congestion. In particular, we show how spectral analysis can identify clusters, and how the presence of clusters affects congestion. This is important for network prediction and network simulation. For the case of peer-to-peer networks we relate conductance and spectral gap to the fundamental questions of searching and topology maintenance. We propose new protocols for maintaining peer-to-peer networks with good conductance and low network overhead. We compare the performance of the traditional method of search by flooding to searching by random walks. We isolate cases of practical interest, such as clustered and dynamic network topologies, where the latter have superior performance. The improvement in the performance can be directly quantified in terms of the conductance of the underlying topology. We introduce further hybrid search schemes, of which flooding and random walks are special instances, which aim to improve the performance of searching by using locally maintained information about the network topology.
    URI
    http://hdl.handle.net/1853/10420
    Collections
    • College of Computing Theses and Dissertations [1071]
    • Georgia Tech Theses and Dissertations [22402]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology