Method and apparatus for accelerating forwarding in software-defined networks

A network element to act as a forwarding plane within a software-defined network (SDN) and reduce negative effects of slow-path packet processing, the network element comprising:

• a set of one or more physical network interfaces configured to:
• receive packets to be forwarded, and
• provide, for a controller in the SDN, access to unprocessed entries of a packet miss table (PMT) upon the controller seeking said access, wherein the PMT is to store portions of packets received by the set of physical network interfaces that do not match any flow entry of a set of one or more flow tables, wherein said set of physical network interfaces is to provide said access by being configured to:
• receive, from the controller, pull entry request messages that indicate pull requests for the unprocessed entries of the PMT, and
• transmit, to the controller, pull entry response messages that comprise one or more of said unprocessed entries of the PMT;
• and
• a packet processing module configured to:
• configure the set of one or more flow tables comprising a set of one or more flow entries, each of the set of flow entries including a match criteria to be matched against match portions of incoming packets and a set of one or more actions to be performed for packets having said match portions that match the match criteria of that flow entry,
• determine whether match portions of received packets match the match criteria of any of the set of flow entries of the set of flow tables, and
• perform a miss procedure when a received packet does not match any entry of the set of flow tables, wherein the miss procedure is one of:
• inserting at least a portion of the received packet as an entry of the PMT, and
• updating an existing entry of the PMT based upon the received packet.

A network element to act as a controller within a software-defined network and reduce negative effects of slow-path packet processing, the network element comprising:

• a set of one or more physical network interfaces;
• and
• a control module coupled to the set of physical network interfaces and configured to:
• access unprocessed entries of a packet miss table (PMT) of a second network element acting as a forwarding plane in the software-defined network, wherein each entry of the PMT stores portions of packets received by the second network element that did not match any entry within a set of one or more flow tables of the second network element, wherein the set of flow tables comprise a set of one or more flow entries, each of the set of flow entries to include a match criteria to be matched against match portions of incoming packets and a set of one or more actions to be performed for packets having said match portions that match the match criteria of that flow entry, and
• responsive to said access of unprocessed entries of the PMT, transmit, to the second network element, one or more flow entry modification messages that indicate a command to insert a set of one or more flow entries into one or more of the set of flow tables.

A method performed by a forwarding node within a software-defined network to reduce negative effects of slow-path packet processing, comprising:

• receiving, by the forwarding node, a first packet;
• determining whether the first packet matches any flow entry within a set of one or more flow tables of the forwarding node, wherein the set of flow tables comprise a set of one or more flow entries, each of the set of flow entries including a match criteria to be matched against a match portion of incoming packets and a set of one or more actions to be performed for packets having said match portion that matches the match criteria;
• responsive to determining that the first packet does not match any flow entry within the set of flow tables, performing a miss procedure comprising:
• inserting at least a portion of the first packet as a first entry in a packet miss table (PMT), wherein the PMT stores portions of packets received by the forwarding node that did not match any flow entry of the set of flow tables;
• receiving a pull entry request message from a controller indicating a pull request for one or more unprocessed entries of the PMT;
• and
• responsive to the receiving of the pull entry request message, transmitting a pull entry response message to the controller, the pull entry response message comprising the first entry of the PMT.

A method performed by a controller executing on a server within a software-defined network to reduce negative effects of slow-path packet processing, comprising:

• transmitting, to a forwarding node in the software-defined network, a pull entry request message indicating a pull request for one or more unprocessed entries of a packet miss table (PMT), wherein each entry of the PMT stores portions of packets received by the forwarding node that did not match any entry within a set of one or more flow tables of the forwarding node, wherein the set of flow tables comprises a set of one or more flow entries, each of the set of flow entries including a match criteria to be matched against a match portion of incoming packets and a set of one or more actions to be performed for packets having the match portion that matches the match criteria of that flow entry;
• receiving, from the forwarding node, a pull entry response message including a set of one or more unprocessed entries of the PMT;
• and
• responsive to receipt of the pull entry response message, transmitting, to the forwarding node, one or more flow entry modification message indicating a command to insert a set of one or more flow entries into one or more of the set of flow tables.

A method performed by a network element acting as a forwarding plane within a software-defined network to reduce negative effects of slow-path packet processing, comprising:

• receiving, by the network element, a first packet;
• determining whether the first packet matches any flow entry within a set of one or more flow tables of the network element, wherein the set of flow tables comprise a set of one or more flow entries, each of the set of flow entries including a match criteria to be matched against a match portion of incoming packets and a set of one or more actions to be performed for packets having said match portions matching the match criteria of that flow entry;
• responsive to determining that the first packet does not match any flow entry within the set of flow tables, performing a miss procedure comprising:
• inserting at least a portion of the first packet as a first entry in a packet miss table (PMT), wherein the PMT stores portions of packets received by the network element that did not match any flow entry of the set of flow tables;
• and
• providing, to a controller, access to the first entry of the PMT upon the controller seeking said access, wherein the controller seeking said access comprises the network element receiving, from the controller, a pull entry request message indicating a request for one or more unprocessed entries of the PMT, and providing said access to the first entry comprises transmitting a pull entry response message to the controller, the pull entry response message comprising the first entry of the PMT.

A method performed by a network element acting as a forwarding plane within a software-defined network to reduce negative effects of slow-path packet processing, comprising:

• receiving, by the network element, a first packet;
• determining whether the first packet matches any flow entry within a set of one or more flow tables of the network element, wherein the set of flow tables comprise a set of one or more flow entries, each of the set of flow entries including a match criteria to be matched against a match portion of incoming packets and a set of one or more actions to be performed for packets having said match portions matching the match criteria of that flow entry;
• responsive to determining that the first packet does not match any flow entry within the set of flow tables, performing a miss procedure comprising:
• inserting at least a portion of the first packet as a first entry in a packet miss table (PMT), wherein the PMT stores portions of packets received by the network element that did not match any flow entry of the set of flow tables;
• providing, to a controller, access to the first entry of the PMT upon the controller seeking said access;
• receiving, from the controller, one or more flow entry modification messages indicating a command to insert a first flow entry into one of the set of flow tables;
• inserting the first flow entry into the one of the set of flow tables, wherein the match criteria of the first flow entry matches a match portion of the first packet;
• and
• modifying the first entry of the PMT to be no longer unprocessed.