Change search
ReferencesLink to record
Permanent link

Direct link
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, -6 p.Conference 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. -6 p.
National Category
Computer Science
URN: urn:nbn:se:kth:diva-147116DOI: 10.1109/ICNP.2013.6733669ScopusID: 2-s2.0-84896767386OAI: diva2:727727
The 3rd International Workshop on Rigorous Protocol Engineering (WRiPE),7-10 Oct. 2013, Goettingen, Germany

QC 20140704

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

Open Access in DiVA

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

Other links

Publisher's full textScopusIEEEXplore

Search in DiVA

By author/editor
Kostic, Dejan
Computer Science

Search outside of DiVA

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

Altmetric score

Total: 80 hits
ReferencesLink to record
Permanent link

Direct link