Method and system of checkpoint and rollback recovery for forwarding states of a software-defined networking (SDN) system

Patent metadata

Field	Value
Publication number	US-10009261-B2
Application number	US-201414525107-A
Country	US
Kind code	B2
Filing date	Oct 27, 2014
Priority date	Aug 21, 2014
Publication date	Jun 26, 2018
Grant date	Jun 26, 2018

Abstract

Methods implemented in an electronic device are disclosed for checkpoint and rollback recovery in a SDN system. The method utilizes message identifiers to indicate an order of consistent states of forwarding tables of a plurality of network elements of the SDN system. The SDN controller of the SDN system receives a request to recover the network to a previous state, and identifies a consistent state of forwarding table for each of the plurality of network elements utilizing the message identifiers associated the consistent states, where the identified consistent states represent the previous state of the network without the identified consistent states being captured at the same time at the plurality of network elements. The SDN controller indicates the identified consistent state for each of the plurality of the network elements to a corresponding network element, where the corresponding network element makes its forwarding table consistent with the identified consistent state.

First claim

What is claimed is:

1. A method implemented in an electronic device serving as a software-defined networking (SDN) controller in a network containing a plurality of network elements, each network element of the plurality of network elements containing a corresponding forwarding table for forwarding traffic, the method comprising:
sending messages to the plurality of network elements from the electronic device, wherein each message contains a message identifier, wherein the message identifier indicates an order of the messages, wherein the plurality of network elements utilize at least some of the messages to update corresponding forwarding tables of the plurality of network elements, wherein the plurality of network elements asynchronously capture consistent states of the corresponding forwarding tables of the plurality of network elements, wherein all of the plurality of the network elements capture the consistent states of the corresponding forwarding tables within a predetermined time window, wherein each consistent state includes values, copied within the corresponding forwarding tables of the plurality of network elements, at one moment in time, and wherein each consistent state is associated with one message identifier;
receiving a set of values from each network element of the plurality of network elements, wherein each value of the set of values is associated with one consistent state for one network element;
receiving a request to recover the network to a previous state of the network, the request being triggered when a fault is detected in the network, wherein the request is received after the detected fault is contained by the electronic device;
identifying a consistent state of the corresponding forwarding table for each network element of the plurality of the network elements utilizing message identifiers associated with the consistent states, wherein the identified consistent states represent the previous state of the network without the identified consistent states being captured at a same time at the plurality of network elements; and
indicating the identified consistent state for each network element of the plurality of the network elements to the network element, wherein the network element updates the corresponding forwarding table to match the identified consistent state if the corresponding forwarding table is inconsistent with the identified consistent state.

2. The method of claim 1 , wherein the message identifier is a number.

3. The method of claim 2 , wherein the number is a transaction identifier complying with an OpenFlow standard.

4. The method of claim 1 , wherein capturing the consistent states of the corresponding forwarding tables comprises:
at each network element of the plurality of network elements, determining whether activity of the network element is over a predetermined threshold; and
capturing one consistent state of the network element only when the activity of the network element is below the predetermined threshold.

5. The method of claim 1 , wherein each consistent state of the corresponding forwarding table is captured through performing a snapshot of the corresponding forwarding table, wherein the snapshot is a copy of the corresponding forwarding table at a particular moment in time.

6. The method of claim 1 , wherein identifying the consistent state for each network element of the plurality of the network elements comprises:
selecting one consistent state for each network element, wherein each selected consistent state is a most recently captured consistent state for each network element prior to receiving the request to recover the network to the previous state of the network;
for each message utilized to update the corresponding forwarding tables, identifying inconsistency between consistent states of pairs of the plurality of network elements, wherein the corresponding forwarding tables of both network elements of each pair are updated utilizing the message;
for each pair where inconsistency is identified, adding one edge to a checkpoint graph pointing to one previous consistent state for one network element in the pair from a current consistent state for the other network element in the pair, wherein the previous consistent state of the network element results in consistency between the consistent states of the pair; and
for each network element that the checkpoint graph contains an edge pointing to the one consistent state for the network element, updating the one consistent state for the network element using the checkpoint graph.

7. An electronic device serving as a software-defined networking (SDN) controller coupled to a network containing a plurality of network elements, each network element of the plurality of network elements containing a corresponding forwarding table for forwarding traffic, the electronic device comprising:
a processor and a non-transitory machine-readable storage medium coupled to the processor, the non-transitory machine-readable storage medium containing a consistent state finder executable by the processor, wherein the electronic device is operative to:
send messages to the plurality of network elements from the electronic device, wherein each message is to contain a message identifier, wherein the message identifier is to indicate an order of the messages, wherein the plurality of network elements is to utilize at least some of the messages to update corresponding forwarding tables of the plurality of network elements, wherein the plurality of network elements asynchronously capture consistent states of the corresponding forwarding tables of the plurality of network elements, wherein all of the plurality of the network elements capture the consistent states of the corresponding forwarding tables within a predetermined time window, wherein each consistent state includes values, copied within the corresponding forwarding tables of the plurality of network elements, at one moment in time, and wherein each consistent state is to be associated with one message identifier,
receive a set of values from each network element of the plurality of network elements, wherein each value of the set of values is to be associated with one consistent state for one network element,
receive a request to recover the network to a previous state of the network based on a fault being detected in the network, wherein the electronic device is operative to receive the request to recover the network to a previous state of the network after the detected fault is contained by the electronic device,
identify a consistent state of the corresponding forwarding table for each network element of the plurality of the network elements utilizing message identifiers associated with the consistent states, wherein the identified consistent states are to represent the previous state of the network without the identified consistent states being captured at a same time at the plurality of network elements, and
indicate the identified consistent state for each network element of the plurality of the network elements to the network element, wherein the network element is to update the corresponding forwarding table to match the identified consistent state if the corresponding forwarding table is inconsistent with the identified consistent state.

8. The electronic device of claim 7 , wherein the message identifier is a number.

9. The electronic device of claim 8 , wherein the number is a transaction identifier complying with an OpenFlow standard.

10. The electronic device of claim 7 , wherein the capture of the consistent states of the corresponding forwarding table is to:
at each network element of the plurality of network elements, determine whether activity of the network

Assignees

• Ericsson Telefon Ab L M
• Ericsson Telefon Ab L M

Inventors

• Zhang Ying
• Beheshti-Zavareh Neda
• Manghirmalani Ravi

Classifications

• H04L45/745

  Address table lookup; Address filtering · CPC title

• H04L41/0863

  by rolling back to previous configuration versions · CPC title

• H04L47/33

  using forward notification · CPC title

• H04L45/28 Primary

  using route fault recovery · CPC title

• H04L41/40 Primary

  using virtualisation of network functions or resources, e.g. SDN or NFV entities · CPC title