METHOD AND APPARATUS FOR TOPOLOGY AND PATH VERIFICATION IN NETWORKS

• US 20150249587A1
• Filed: 09/04/2013
• Published: 09/03/2015
• Est. Priority Date: 09/20/2012
• Status: Abandoned Application

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Kozat, Ulas C., Liang, Guanfeng, Kokten, Koray
• Application Number:
  US14/429,707
• Publication Number:
  US 20150249587A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 12/437 Ring fault isolation or reconfiguration for SDH/SONET ring networks H04J3/085
• CPC Class Codes: H04L 41/0677 Localisation of faults
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• 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 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/20 the monitoring system or the monitored elements being virtualised, abstracted or software-defined entities, e.g. SDN or NFV
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 47/20 Traffic policing

Abstract

A method and apparatus are disclosed herein for topology and/or path verification in networks. In one embodiment, a method is disclosed for use with a pre-determined subset of network flows for a communication network, where the network comprises a control plane, a forwarding plane, and one or more controllers. The method comprises installing forwarding rules on the forwarding elements for identification of network information, wherein the forwarding rules are grouped into one or more separate control flows, where each of the one or more control flows makes a closed loop walk through at least a portion of the network according to the forwarding rules of said each control flow, injecting traffic for one or more control flows onto the forwarding plane, and identifying the network information based on results of injecting the traffic.

Claims

1. A method for use with a pre-determined subset of network flows for a communication network, wherein the network comprises a control plane, a forwarding plane, and one or more controllers, the method comprising:

installing forwarding rules on the forwarding elements for identification of network information, wherein the forwarding rules are grouped into one or more separate control flows, where each of the one or more control flows makes a closed loop walk through at least a portion of the network according to the forwarding rules of said each control flow;

injecting traffic for one or more control flows onto the forwarding plane; and

identifying the network information based on results of injecting the traffic.

2. The method defined in claim 1 wherein the network information comprises one or more of a group consisting of:

link failures, topology connectivity, and routability of a pre-determined subset of network flows.

3. The method defined in claim 1 wherein the forwarding rules are for verifying connectivity of an arbitrary network topology graph.

4. The method defined in claim 3 wherein the forwarding rules verify connectivity of the arbitrary network topology graph by constructing a control flow that traverses each link in a forwarding plane in a network topology represented by the topology graph.

5. The method defined in claim 3 further comprising:

computing an Euler cycle if it exists on the topology graph of the forwarding plane;

computing a minimum length cycle;

installing static rules to route one or more control packets according to the computed minimum length cycle; and

installing dynamic loopback rules at an arbitrary point on the routing loop to send the control flow packets injected by the controller back to the controller after each packet completes one full cycle.

6. The method defined in claim 5 wherein computing the minimum length cycle comprises solving a Chinese postman problem.

7. The method defined in claim 1 wherein the forwarding rules are for verifying connectivity of an arbitrary network topology graph by constructing a control flow that traverses each link in the forwarding plane.

8. The method defined in claim 7 wherein constructing a control flow that traverses each link in the forwarding plane comprises:

creating a link adjacency graph;

creating a weighted complete topology graph;

computing a Hamiltonian cycle on the weighted complete topology graph; and

deriving forwarding rules for the control flow based on the Hamiltonian cycle.

9. The method defined in claim 1 wherein the forwarding rules are used for detecting link failures.

10. The method defined in claim 9 wherein detecting link failures comprises:

computing a logical ring topology;

installing routing rules for constructing control flows to loop the logical ring topology in a first direction, the first direction being a clockwise direction or a counter clockwise direction;

installing routing rules for constructing control flows to loop the logical ring topology in a second direction opposite to the first direction; and

installing bounce back rules to switch routing of control flows to a second direction opposite the first direction.

11. The method defined in claim 1 wherein the forwarding rules are used for verifying routability of a network flow.

12. The method defined in claim 11 wherein the forwarding rules correspond to a forward control flow that passes through an execution pipeline of a network flow and to a reverse control flow that is reflected by an egress switch of the network flow following the reverse path of the forward control flow and terminating at a network controller from which the forward control flow started.

13. A communication network comprising:

a network topology of a plurality of nodes that include a control plane, a forwarding plane comprising forwarding elements, and one or more controllers,

wherein the forwarding elements have forwarding rules for identification of network information, wherein the forwarding rules are grouped into one or more separate control flows, where each of the one or more control flows makes a closed loop walk through at least a portion of the network according to the forwarding rules of said each control flow;

at least one of the controllers operable to inject traffic for one or more control flows onto the forwarding plane and identify the network information based on results of injecting the traffic.

14. The network defined in claim 13 wherein the network information comprises one or more of a group consisting of:

link failures, topology connectivity, and routability of a pre-determined subset of network flows.

15. The network defined in claim 13 wherein the forwarding rules are for verifying connectivity of an arbitrary network topology graph.

16. The network defined in claim 15 wherein the at least one controller verifies connectivity of the network topology by:

computing an Euler cycle if it exists on the topology graph of the forwarding plane;

computing a minimum length cycle;

installing static rules to route one or more control packets according to the computed minimum length cycle; and

installing dynamic loopback rules at an arbitrary point on the routing loop to send the control flow packets injected by the controller back to the controller after each packet completes one full cycle.

17. The network defined in claim 16 wherein computing the minimum length cycle comprises solving a Chinese postman problem.

18. The network defined in claim 13 wherein the forwarding rules are used for verifying connectivity of the network topology graph.

19. The network defined in claim 18 wherein the at least one controller constructs a control flow that traverses each link in the forwarding plane by:

creating a link adjacency graph;

creating a weighted complete topology graph;

computing a Hamiltonian cycle on the weighted complete topology graph; and

deriving forwarding rules for the control flow based on the Hamiltonian cycle.

20. The network defined in claim 13 wherein the forwarding rules are used for detecting link failures.

21. The network defined in claim 20 wherein the at least one controller detects link failures by:

computing a logical ring topology;

installing routing rules for constructing control flows to loop the logical ring topology in a first direction, the first direction being a clockwise direction or a counter clockwise direction;

installing routing rules for constructing control flows to loop the logical ring topology in a second direction opposite to the first direction; and

installing bounce back rules to switch routing of control flows to a second direction opposite the first direction.

22. The network defined in claim 13 wherein the forwarding rules are used for verifying routability of a network flow.

23. The network defined in claim 22 wherein the forwarding rules correspond to a forward control flow that passes through an execution pipeline of a network flow and to a reverse control flow that is reflected by an egress switch of the network flow following the reverse path of the forward control flow and terminating at a network controller from which the forward control flow started.

24. A method for locating link failures in a network topology, the method comprising:

installing a loopback rule on a node in a logical link topology;

performing a binary search on the logical link topology, wherein performing the binary search by

selecting a node on the logical ring,

sending a control packet in a first direction through the ring,

bouncing back the control packet at the selected node into a second direction through the ring, where the second direction is reverse the first direction, and

receiving the control packet at the controller via a loopback rule installed prior to sending the control packet.

25. A method of locating link failures in a network topology having a plurality of nodes, the method comprising:

specifying a bounce back point in the network for each of a plurality of control packets;

sending the plurality of control packets from one or more points on a constructed logical ring representing the network; and

making a link failure detection decision based on whether successfully receiving the plurality of control packets.