System and method for simulating IP network routing

• US 8,325,720 B2
• Filed: 07/17/2009
• Issued: 12/04/2012
• Est. Priority Date: 07/17/2008
• Status: Active Grant

• Current Assignee: Netbrain Technologies Incorporated
• Original Assignee: Netbrain Technologies Incorporated
• Inventors: Gao, Lingping, Liao, Guangdong
• Primary Examiner(s): Nguyen, Brian D
• Application Number:
  US12/505,461
• Publication Number:
  US 20120209581A1
• Time in Patent Office: 1,236 Days
• Field of Search: 370/252, 370/254, 370/255, 370/256, 370/395.53, 370/401, 703/13
• US Class Current: 370/389
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 45/46 Cluster building

Abstract

Methods and systems for simulating IP networks. Routing Clusters are formed by grouping routers that are connected directly or indirectly and are running the same routing protocol. Routers that are configured to run more than one routing protocols became Border Routers for routing clusters based on these routing protocols. Routing tables are formed by flooding the routers inside the routing clusters and by flooding routes across routing links by redistribution command.

Claims

1. A method for simulating a network routing by a computer processor, the method steps performed by the computer processor comprising the actions of:

building a Network Cluster Graph (NCG) based on a set of configuration information of a network, wherein the NCG comprises at least one routing cluster having a plurality of network devices; and

calculating at least one simulated routing table for the network using the NCG;

extracting a first configuration information including routing protocols from a first network device;

identifying and extracting a second configuration information of at least one neighboring network device of said first network device using the first configuration information;

building at least one routing cluster (RC) wherein a set of network devices that run a same routing protocol are grouped in one cluster;

identifying a border cluster router (BCR), if any, that is configured to run at least two routing protocols;

upon the identified border cluster router, identifying a second set of routing clusters in which said border cluster belongs to;

linking the second set of routing clusters in which said border cluster router belongs to via said border cluster router; and

displaying the second set of routing clusters on a screen device.

2. The method of claim 1, further comprising actions of:

calculating a set of route entries for a cluster router, each said route entry having a metrics;

determining whether each of the set of route entries can be updated to a neighboring network device; and

updating the metrics of each of the route entries.

3. A method of claim 1, further comprising actions of:

calculating a set of route entries for a cluster router having at least one interface;

determining a neighboring interface for said interface of the cluster router;

determining whether each of the set of route entries may be denied by the neighboring interface; and

updating each of the set of route entries in the routing table of the cluster router.

4. The method of claim 1, wherein the network is an IP network.

5. The method of claim 1, wherein the neighboring devices are determined by an IP address of each of the devices.

6. The method of claim 1, further comprising actions of:

flooding a route from one router cluster to another router cluster via a border cluster router.

7. The method of claim 6, wherein flooding a route from one router cluster to another router cluster further comprising:

determining whether a route is blocked by a distribution command in a configuration of the border cluster router.

8. The method of claim 6, wherein flooding a route from one router cluster to another router cluster further comprising:

determining whether a source routing protocol matches a redistribution command of the border cluster router; and

if yes for the above step, updating the routing table of the border cluster router and resetting a set of route parameters according to the redistribution command.

9. A network simulation system, comprising:

a screen for displaying network simulation; and

a computer system for extracting and processing a plurality of network device information from a physical network;

wherein the screen displays a dynamically generated simulation of the physical network in which a plurality of network devices that are connected directly or indirectly and are running on a same routing protocol are grouped to be in a same router cluster; and

a router running more than one routing protocols is a border router that forms a cluster link between two router clusters.

10. The network simulation system of claim 9, wherein the computer system further conducts the actions of:

calculating a plurality of route entries for a cluster router that has a set of routes wherein each of the route entries has a metrics;

determining whether each of the route entries may be updated to a neighboring device by at least one interface of the router; and

updating the metrics of each of the route entries.

11. The network simulation system of claim 9, wherein the computer system further conducts the actions of:

calculating a plurality of route entries in a routing table for a cluster router having at least one interface;

determining a neighboring interface for the interface of the cluster router;

determining whether each of the route entries may be denied by the neighbor interface; and

updating each of the route entries in the routing table of the cluster router.

12. The network simulation system of claim 9, wherein the computer system further conducts the actions of:

flooding a set of route entries from one router cluster to another router cluster via a border cluster router.

13. The network simulation system of claim 9, wherein the computer system further conducts the actions of:

determining whether a route is blocked by a distribution command in the configuration of the border cluster router.

14. The network simulation system of claim 9, wherein the network is an IP network.

15. The network simulation system of claim 9, wherein whether a network device is a neighboring device to another network device is determined by an IP address of each of the devices.