kth.sePublications
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
Is the Network Capable of Computation?
IMDEA Networks Institute.ORCID iD: 0000-0002-1256-1070
2013 (English)In: Proceedings of the 3rd International Workshop on Rigorous Protocol Engineering (WRiPE), IEEE conference proceedings, 2013, p. -6Conference paper, Published paper (Refereed)
Abstract [en]

Ensuring correct network behavior is hard. Previous state of the art has demonstrated that analyzing a network containing middleboxes is hard. In this paper, we show that even using only statically configured switches, and asking the simplest possible question - “Will this concrete packet reach the destination?” - can make the problem intractable. Moreover, we demonstrate that this is a fundamental property because a network can perform arbitrary computations. Namely, we show how to emulate the Rule 110 cellular automaton using only basic network switches with simple features such as packet matching, header rewriting and round-robin loadbalancing. This ultimately means that analyzing dynamic network behavior can be as hard as analyzing an arbitrary program.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2013. p. -6
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-147116DOI: 10.1109/ICNP.2013.6733669Scopus ID: 2-s2.0-84896767386OAI: oai:DiVA.org:kth-147116DiVA, id: diva2:727727
Conference
The 3rd International Workshop on Rigorous Protocol Engineering (WRiPE),7-10 Oct. 2013, Goettingen, Germany
Note

QC 20140704

Available from: 2014-06-23 Created: 2014-06-23 Last updated: 2022-06-23Bibliographically approved

Open Access in DiVA

fulltext(255 kB)209 downloads
File information
File name FULLTEXT01.pdfFile size 255 kBChecksum SHA-512
7039517469b9c63b728bf0330994e19a9ce5e5efc29fcb950f494abb807f1037568d84390abd18c44c4384c96e456158ff2c2bdfe576bbe961316e0fcc5b6100
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusIEEEXplore

Authority records

Kostic, Dejan

Search in DiVA

By author/editor
Kostic, Dejan
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 209 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 218 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