Offline queries in software defined networks
Methods and systems for finding a packet's routing path in a network includes intercepting control messages sent by a controller to one or more switches in a software defined network (SDN). A state of the SDN at a requested time is emulated and one or more possible routing paths through the emulated SDN is identified by replaying the intercepted control messages to one or more emulated switches in the emulated SDN. The one or more possible routing paths correspond to a requested packet injected into the SDN at the requested time.
1. A method for finding a packet's routing path in a network, comprising:
intercepting control messages sent by a controller to one or more switches in a software defined network (SDN);
emulating a state of the SDN at a requested time; and
identifying one or more possible routing paths through the emulated SDN by replaying the intercepted control messages to one or more emulated switches in the emulated SDN, wherein said one or more possible routing paths correspond to a requested packet injected into the SDN at the requested time; and
determining a starting time T s , defined as the time before which switch states will not influence routing decisions for the packet, as T s =T 0 if, for every control message that is sent to a switch matching the packet and incoming port on the packet fields, the control message has a recorded time stamp T i that satisfies:
T
i
+
E
RTT
2
+
k
σ
RTT
<
T
0
OR
T
i
+
E
RTT
2
-
k
σ
RTT
>
T
0
where E RTT is the mean RTT, σ RTT is the variance on the RTT, T 0 is the input timestamp, and k is the Z-value in the statistical confidence interval, and
T
s
=
T
x
+
E
RTT
2
-
k
σ
RTT
otherwise, where T x is the time stamp of the earliest control message matching the packet and violating the above condition; and
wherein identifying one or more possible routing paths comprises reconstructing flow table states of the one or more emulated switches based on the intercepted control messages and round trip time (RTT) information.
2. A method for finding a packet's routing path in a network, comprising:
intercepting control messages sent by a controller to one or more switches in a software defined network (SDN);
emulating a state of the SDN at a requested time; and
identifying one or more possible routing paths through the emulated SDN by replaying the intercepted control messages to one or more emulated switches in the emulated SDN, wherein said one or more possible routing paths correspond to a requested packet injected into the SDN at the requested time; and
wherein identifying one or more possible routing paths comprises reconstructing flow table states of the one or more emulated switches based on the intercepted control messages and round trip time (RTT) information; and
wherein intercepted control messages selected for reconstructing the flow table states are all messages earlier than T x until the first message whose time stamp T c0 satisfies
T
c
0
+
E
RTT
2
-
k
σ
RTT
⋂
[
T
s
,
T
s
+
T
D
]
≠
∅
and
T
c
0
+
E
RTT
2
+
k
σ
RTT
⋂
[
T
s
,
T
s
+
T
D
]
≠
∅
,
where T D is the maximum time a packet can remain in the network and is a function of network diameter, wherein a first selected message and any remaining control messages satisfying the same conditions are copied into a time ordered list that includes all of the control messages that potentially affect the routing decision on the packet at the switch.
3. A system for finding a packet's path in a network, comprising:
a proxy comprising a processor and a memory storing an executable program code executed by the processor configured to intercept control messages sent by a controller to one or more switches in a software defined network (SDN); and
a network emulator comprising a processor and a memory storing an executable program code executed by the processor configured to emulate a state of the SDN at a requested time and to identify one or more possible routing paths through the emulated SDN by replaying the intercepted control messages to one or more emulated switches in the emulated SDN, wherein said one or more routing possible paths correspond to a requested packet inserted into the SDN at the requested time
wherein the network emulator is configured to reconstruct flow table states of the one or more emulated switches based on the intercepted control messages and round trip time (RTT) information; and
wherein the network emulator is further configured to determine a starting time T s , defined as the time before which switch states will not influence routing decisions for the packet, as T s =T 0 if, for every control message that is sent to a switch matching the packet and incoming port on the packet fields, the control message has a recorded time stamp T i that satisfies:
T
i
+
E
RTT
2
+
k
σ
RTT
<
T
0
OR
T
i
+
E
RTT
2
-
k
σ
RTT
>
T
0
where E RTT is the mean RTT, σ RTT is the variance on the RTT, T 0 is the input timestamp, and k is the Z-value in the statistical confidence interval, and
T
s
=
T
x
+
E
RTT
2
-
k
σ
RTT
otherwise, where T x is the time stamp of the earliest control message matching the packet and violating the above condition.
4. A system for finding a packet's path in a network, comprising:
a proxy comprising a processor and a memory storing an executable program code executed by the processor configured to intercept control messages sent by a controller to one or more switches in a software defined network (SDN); and
a network emulator comprising a processor and a memory storing an executable program code executed by the processor configured to emulate a state of the SDN at a requested time and to identify one or more possible routing paths through the emulated SDN by replaying the intercepted control messages to one or more emulated switches in the emulated SDN, wherein said one or more routing possible paths correspond to a requested packet inserted into the SDN at the requested time
wherein the network emulator is configured to reconstruct flow table states of the one or more emulated switches based on the intercepted control messages and round trip time (RTT) information; and
wherein intercepted control messages selected for reconstructing the flow table states are all messages earlier than T x until the first message whose time stamp T c0 satisfies
T
c
0
+
E
RTT
2
-
k
σ
RTT
⋂
[
T
s
,
T
s
+
T
D
]
≠
∅
and
T
c
0
+
E
RTT
2
+
k
σ
RTT
⋂
[
T
s
,
T
s
+
T
D
]
≠
∅
,
is the maximum time a packet can remain in the network and is a function of network diameter, wherein a first selected message and any remaining control messages satisfying the same conditions are copied into a time ordered list that includes all of the control messages that potentially affect the routing decision on the packet at the switch.