Reducing packet reordering in flow-based networks
View Patent ↗The present disclosure provides for methods, network devices, and computer readable storage media for packet reordering. In one embodiment, a method includes receiving a first packet of a first flow at a network device and determining whether flow-identifying information extracted from the first packet matches an existing flow entry. The method also includes, in response to a determination that the flow-identifying information does not match any existing flow entries, generating a new transient flow entry that includes the flow-identifying information and packet-in state. The method also includes forwarding the first packet to a controller via a packet-in stream.
1. A method, the method comprising:
receiving a first packet of a first flow at a network device;
determining whether flow-identifying information extracted from the first packet matches any existing flow entries;
in response to a determination that the flow-identifying information does not match any existing flow entries, generating, by the network device, a new transient flow entry that includes the flow-identifying information and packet-in state, wherein the packet-in state indicates that packets of the first flow are presently being forwarded to a controller;
forwarding the first packet to the controller via a packet-in stream;
receiving flow policy for the first flow from the controller; and
in response to installation of the flow policy on the network device,
sending a marker packet to the controller via the packet-in stream, wherein the marker packet indicates an end to the packet-in stream, and
updating the new transient flow entry to include packet-out state, wherein the packet-out state indicates that packets of the first flow are no longer being forwarded to the controller.
2. The method of claim 1 , wherein
the existing flow entries comprises at least one of a group including:
an existing non-transient flow entry stored in a flow table, and
an existing transient flow entry stored in one of the flow table and a transient table,
wherein the existing non-transient flow entry includes flow policy that has been received from the controller and installed on the network device, and
wherein the existing transient flow entry includes transient status that indicates packets of a flow are presently being communicated between the network device and the controller.
3. The method of claim 1 , further comprising:
receiving a subsequent packet of the first flow at the network device from another network device before the flow policy has been installed on the network device; and
in response to a determination that second flow-identifying information extracted from the subsequent packet matches the new transient flow entry having packet-in state, forwarding the subsequent packet to the controller via the packet-in stream.
4. The method of claim 1 , further comprising:
generating, by the network device, the marker packet, wherein the marker packet includes the flow-identifying information extracted from the first packet.
5. The method of claim 1 , further comprising:
receiving a returning packet of the first flow from the controller via a packet-out stream, wherein the returning packet corresponds to a packet forwarded to the controller via the packet-in stream; and
in response to a determination that second flow-identifying information extracted from the returning packet matches the new transient flow entry having packet-out state, processing the returning packet according to the flow policy installed on the network device.
6. The method of claim 1 , further comprising:
receiving a subsequent packet of the first flow from another network device after the flow policy has been installed on the network device; and
in response to a determination that second flow-identifying information extracted from the subsequent packet matches the new transient flow entry having packet-out state, storing the subsequent packet in a FIFO (first in first out) buffer.
7. The method of claim 1 , further comprising:
receiving a returning marker packet for the first flow from the controller via a packet-out stream, wherein the returning marker packet corresponds to the marker packet sent to the controller via the packet-in stream, and the returning marker packet indicates an end to the packet-out stream; and
in response to a determination that second flow-identifying information extracted from the returning marker packet matches the new transient flow entry having packet-out state,
flushing a set of packets of the first flow from a FIFO (first in first out) buffer, wherein the set of packets were received at the network device after the marker packet was sent to the controller, and
processing the set of packets according to the flow policy installed on the network device.
8. The method of claim 7 , further comprising:
removing the new transient flow entry in response to receipt of the returning marker packet, wherein
the removing the new transient flow entry comprises one of
removing the new transient flow entry from a transient table, and
removing transient status from the new transient flow entry to result in a new non-transient flow entry stored in a flow table.
9. The method of claim 1 , further comprising:
receiving a subsequent packet of the first flow from another network device after the flow policy has been installed on the network device; and
in response to a determination that second flow-identifying information extracted from the subsequent packet does not match any transient flow entries, searching non-transient flow entries for the second flow-identifying information; and
in response to a determination that the second flow-identifying information matches a non-transient flow entry, processing the subsequent packet according to the flow policy indicated in the non-transient flow entry.
10. A network device comprising:
a port configured to receive a first packet of a first flow;
a first notifier configured to
detect a determination made by a flow match module whether flow-identifying information extracted from the first packet matches any existing flow entries;
a marker generator configured to
generate a new transient flow entry that includes the flow-identifying information and packet-in state, in response to a notification received from the first notifier that indicates the flow-identifying information does not match any existing flow entries, wherein
the packet-in state indicates that packets of the first flow are presently being forwarded to a controller; and
the flow match module is configured to forward the first packet to the controller via a packet-in stream; and
a second notifier configured to detect installation of a flow policy for the first flow received from the controller, wherein
the marker generator is further configured to
send a marker packet to the controller via the packet-in stream, in response to a second notification received from the second notifier that indicates the installation is detected, and
update the new transient flow entry to include packet-out state, in response to the second notification, wherein the packet-out state indicates that packets of the first flow are no longer being forwarded to the controller.
11. The network device of claim 10 , wherein
the existing flow entries comprises at least one of a group including:
an existing non-transient flow entry stored in a flow table, and
an existing transient flow entry stored in one of the flow table and a transient table,
wherein the existing non-transient flow entry includes flow policy that has been received from the controller and installed on the network device, and
wherein the existing transient flow entry includes transient status that indicates packets of a flow are presently being communicated between the network device and the controller.
12. The network device of claim 10 , wherein
the port is further configured to receive a subsequent packet of the first flow from another network device before the flow policy is installed on the network device,
wherein the flow match module is further configured to
forward the subsequent packet to the controller via the packet-in stream, in response to a determination that second flow-identifying information extracted from the subsequent packet matches the new transient flow entry having packet-in state.
13. The network device of claim 10 , wherein
the marker generator is further configured to generate the marker packet, wherein the marker packet includes the flow-identifying information extracted from the first packet.
14. The network device of claim 10 , further comprising:
a marker merger configured to
receive a returning packet of the first flow from the controller via a packet-out stream, wherein the returning packet corresponds to a packet forwarded to the controller via the packet-in stream, and
forward the returning packet to an action module for processing according to the flow policy installed on the network device, in response to a determination that second flow-identifying information extracted from the returning packet matches the new transient flow entry having packet-out state.
15. The network device of claim 10 , further comprising:
a marker merger configured to
receive a subsequent packet of the first flow from another network device after the flow policy is installed on the network device, and
store the subsequent packet in a FIFO (first in first out) buffer, in response to a determination that second flow-identifying information extracted from the subsequent packet matches the new transient flow entry having packet-out state.
16. The network device of claim 10 , further comprising:
a marker merger configured to
receive a returning marker packet for the first flow from the controller via a packet-out stream, wherein the returning marker packet corresponds to the marker packet sent to the controller via the packet-in stream, and the returning marker packet indicates an end to the packet-out stream, and
flush a set of packets of the first flow from a FIFO (first in first out) buffer to an action module for processing according to the flow policy installed on the network device, in response to a determination that second flow-identifying information extracted from the returning marker packet matches the new transient flow entry having packet-out state, wherein the set of packets were received at the network device after the marker packet was sent to the controller.
17. The network device of claim 16 , further comprising:
the marker merger further configured to remove the new transient flow entry in response to receipt of the returning marker packet, wherein
the marker merger is configured to perform one of
removal of the new transient flow entry from a transient table, and
removal of transient status from the new transient flow entry to result in a new non-transient flow entry stored in a flow table.
18. A non-transitory computer readable storage medium configured to store program instructions that, when executed on a processor, are configured to cause the processor to perform a method comprising:
receiving a first packet of a first flow at a network device;
determining whether flow-identifying information extracted from the first packet matches any existing flow entries;
in response to a determination that the flow-identifying information does not match any existing flow entries, generating a new transient flow entry that includes the flow-identifying information and packet-in state, wherein the packet-in state indicates that packets of the first flow are being forwarded to a controller; and
forwarding the first packet to the controller via a packet-in stream;
receiving flow policy for the first flow from the controller; and
in response to installation of the flow policy on the network device,
sending a marker packet to the controller via the packet-in stream, wherein the marker packet indicates an end to the packet-in stream, and
updating the new transient flow entry to include packet-out state, wherein the packet-out state indicates that packets of the first flow are no longer being forwarded to the controller.
19. The non-transitory computer readable storage medium of claim 18 , the method further comprising:
receiving a subsequent packet of the first flow from another network device after the flow policy has been installed on the network device; and
in response to a determination that second flow-identifying information extracted from the subsequent packet matches the new transient flow entry having packet-out state, storing the subsequent packet in a FIFO (first in first out) buffer.
20. The non-transitory computer readable storage medium of claim 18 , the method further comprising:
receiving a returning marker packet for the first flow from the controller via a packet-out stream, wherein the returning marker packet corresponds to the marker packet sent to the controller via the packet-in stream, and the returning marker packet indicates an end to the packet-out stream; and
in response to a determination that second flow-identifying information extracted from the returning marker packet matches the new transient flow entry having packet-out state,
flushing a set of packets of the first flow from a FIFO (first in first out) buffer, wherein the set of packets were subsequently received at the network device after the marker packet was sent to the controller, and
processing the set of packets according to the flow policy installed on the network device.