Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Investigating how Distributed Computation Pruning performs on the Generalized Linear Preference model
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Finding all shortest paths in a distributed dynamic network has many practical applications, but it is perhaps most important in network routing. To this end a number of algorithms and techniques have been developed. This paper investigates one such technique called Distributed Computation Pruning (DCP), that utilizes a property found in many real-world networks, including the Internet, called Power Law degree distribution. DCP has previously been shown to improve All Pairs Shortest Paths algorithms on networks generated by the Barabási-Albert model. In this paper we extend the experimental evidence by evaluating the performance of algorithms combined with DCP on networks generated by the Generalized Linear Preference model (GLP). This model has previously been shown to generate networks that are more representative of the Internet than those generated by previous models. We found that algorithms that are combined with DCP see a distinct decrease in the amount of messages sent across the network, suggesting that DCP is a viable technique for improving existing routing algorithms.

Place, publisher, year, edition, pages
2015.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-166377OAI: oai:DiVA.org:kth-166377DiVA: diva2:810616
Subject / course
Computer Science
Supervisors
Examiners
Available from: 2015-05-12 Created: 2015-05-07 Last updated: 2015-05-12Bibliographically approved

Open Access in DiVA

fulltext(614 kB)140 downloads
File information
File name FULLTEXT01.pdfFile size 614 kBChecksum SHA-512
83e502e94b940a1346b72e627297e4b80d04b05ff0d7355f21a9598f4738c17c0834ae48ea2d6bf0bdfe065adfcd41c173a1376deae44db7fd79623e7bbf966a
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 140 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 187 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf