2014 · 28 citations · 14 references
ComputingComputer ScienceComputer SystemsComputer NetworksFault-tolerant ComputingFault-tolerant SystemsFault ManagementNetwork ReliabilityNetwork SwitchingNetwork TopologyRoutingSoftware-defined NetworkingControl Plane SeparationFailure LocalizationFault-tolerant NetworkingFault-tolerant NetworksLink Failure DetectionNetwork Fault DiagnosisNetwork VerificationUpper Bounds
Software Defined Networks (SDN) decouple the forwarding and control planes from each other. The control plane is assumed to have a global knowledge of the underlying physical and/or logical network topology so that it can monitor, abstract and control the forwarding plane. When parts of the control plane become unavailable or unreliable, individual controllers should still be able to monitor the forwarding plane and run diagnostics to take the correct routing actions. In our paper, we present solutions that install an optimal or near-optimal number of static forwarding rules on switches/routers for any controller to be able to verify the topology connectivity and detect/locate link failures at data plane speeds without relying on state updates from forwarding plane nodes and other controllers while requiring reachability to only one (arbitrary) forwarding node. Our upper bounds on performance indicate that sub-second link failure localization is possible even at data-center scale networks. For networks with hundreds or few thousand links, tens of milliseconds of latency is achievable.
14
Nick McKeown, Tom Anderson, Hari Balakrishnan et al. · ACM SIGCOMM Computer Communication Review · 2008 · 8.4K citations
Matching, Euler tours and the Chinese postman
Jack Edmonds, Ellis L. Johnson · Mathematical Programming · 1973 · 987 citations
Header space analysis: static checking for networks
Peyman Kazemian, George Varghese, Nick McKeown · 2012 · 629 citations
Keith Kirkpatrick · Communications of the ACM · 2013 · 604 citations
Abstractions for network update
Mark Reitblatt, Nate Foster, Jennifer Rexford et al. · 2012 · 580 citations · Full text