Determining violation of a network invariant

• US 10,541,873 B2
• Filed: 11/20/2015
• Issued: 01/21/2020
• Est. Priority Date: 11/20/2015
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Zhang, Ying, Lee, Jeongkeun, Sharma, Puneet, Kang, Joon-Myung
• Primary Examiner(s): Aung, Sai
• Application Number:
  US15/775,378
• Publication Number:
  US 20180331909A1
• Time in Patent Office: 1,523 Days
• CPC Class Codes: H04L 41/0681 Configuration of triggering conditions
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/342 between virtual entities, e.g. orchestrators, SDN or NFV entities
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 41/5032 Generating service level reports
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2483 involving identification of individual flows

Abstract

Example implementations relate to determining whether network invariants are violated by flow rules to be implemented by the data plane of a network. In an example, a verification module implemented on a device receives a flow rule transmitted from an SDN controller to a switch, the flow rule relating to an event. The module determines whether the flow rule matches any of a plurality of network invariants cached in the device. If determined that the flow rule matches one of the plurality of network invariants, the verification module determines whether the flow rule violates the matched network invariant. If determined that the flow rule does not match any of the plurality of network invariants, the verification module (1) reports the event associated with the flow rule to a policy management module, (2) receives a new network invariant related to the event from the policy management module, and (3) determines whether the flow rule violates the new network invariant. The verification module generates an alarm if determined that the flow rule violates any of the network invariants.

Claims

1. A method, comprising, by a device implementing a verification module:

receiving, by the verification module, a flow rule transmitted from an SDN controller to a switch, the flow rule relating to an event;

determining whether the flow rule matches any of a plurality of network invariants cached in the device;

if determined that the flow rule matches one of the plurality of network invariants, determining whether the flow rule violates the matched network invariant;

if determined that the flow rule does not match any of the plurality of network invariants, (1) reporting the event associated with the flow rule to a policy management module, (2) receiving a new network invariant related to the event from the policy management module, and (3) determining whether the flow rule violates the new network invariant; and

generating an alarm if determined that the flow rule violates any of the network invariants.

2. The method of claim 1, further comprising caching the new network invariant in the device.

3. The method of claim 1, wherein the new network invariant applies to a flow space that shares a same policy as a flow associated with the event.

4. The method of claim 1, further comprising forwarding the alarm to the policy management module.

5. The method of claim 1, further comprising determining whether a path has been established between a source and destination associated with the flow rule.

6. The method of claim 5, wherein if initially determined that a path has not been established between the source and destination, waiting for a period of time specified by a timeout value and then checking again whether a path has been established between the source and destination.

7. The method of claim 5, further comprising waiting to determine whether a path has been established between the source and destination until a plurality of flow rules marked with a same transaction number as the flow rule are received, wherein the flow rules were marked with the same transaction number by the SDN controller.

8. The method of claim 1, further comprising determining whether a service function chain policy specified by a network invariant is implemented correctly by (1) constructing a path based on a plurality of flow rules having a same transaction number, and (2) determining whether the constructed path passes through service function instances of the service function chain policy in an order specified by the service function chain policy.

9. The method of claim 8, further comprising determining physical addresses of the service function instances by querying a logical-to-physical mapping database in the SDN controller, wherein the physical addresses are used to determine whether the path passes through the service function instances in the order specified by the service function chain policy.

10. A device implementing a verification module in a network, comprising:

a communication module to intercept a flow rule transmitted to a switch from an SDN controller;

a computer-readable storage medium to store a plurality of network invariants received from a policy management module;

a match determination module to determine whether the flow rule matches any of the network invariants, wherein if the flow rule does not match any of the network invariants, the communication module transmits an event associated with the flow rule to the policy management module to request a new network invariant associated with the event;

a policy violation module to determine whether the flow rule violates a matched network invariant or the new network invariant; and

an alarm generator to generate an alarm to send to the policy management module if any of the network invariants is violated.

11. The device of claim 10, wherein the network invariants include one of whitelists, blacklists, and service function chains.

12. The device of claim 10, wherein the device stores the new network invariant in the computer-readable storage medium.

13. The device of claim 10, wherein the policy management module implements high-level policies in the network.

14. The device of claim 10, wherein the network is a software defined network.

15. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to:

receive a flow rule transmitted from an SDN controller to a switch, the flow rule relating to an event;

determine whether the flow rule matches any of a plurality of network invariants stored in the computer-readable storage medium;

if determined that the flow rule matches one of the plurality of network invariants, determine whether the flow rule violates the matched network invariant;

if determined that the flow rule does not match any of the plurality of network invariants, (1) report the event associated with the flow rule to a policy management module, (2) receive a new network invariant related to the event from the policy management module, and (3) determine whether the flow rule violates the new network invariant; and

generate an alarm if determined that the flow rule violates any of the network invariants.