Is the Network Capable of Computation?
2013 (English)In: Proceedings of the 3rd International Workshop on Rigorous Protocol Engineering (WRiPE), IEEE conference proceedings, 2013, -6 p.Conference paper (Refereed)
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.
IdentifiersURN: urn:nbn:se:kth:diva-147116DOI: 10.1109/ICNP.2013.6733669ScopusID: 2-s2.0-84896767386OAI: oai:DiVA.org:kth-147116DiVA: diva2:727727
The 3rd International Workshop on Rigorous Protocol Engineering (WRiPE),7-10 Oct. 2013, Goettingen, Germany
QC 201407042014-06-232014-06-232014-07-04Bibliographically approved