Method and apparatus for configuring a virtual network

• US 5,802,286 A
• Filed: 05/22/1995
• Issued: 09/01/1998
• Est. Priority Date: 05/22/1995
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Bay Networks, Inc. (Nortel Networks Corporation)
• Inventors: Dere, Judy Y., Leong, Leon Y. K., Simone, Daniel A., Thomson, Allan
• Primary Examiner(s): An, Meng-Ai T.
• Assistant Examiner(s): Davis, Jr., Walter D.
• Application Number:
  US08/447,066
• Time in Patent Office: 1,198 Days
• Field of Search: 395/200.01, 395/200.02, 395/200.1, 395/200.11, 395/200.5, 395/200.53, 395/200.56, 395/200.3, 370/254
• US Class Current: 709/220
• CPC Class Codes: H04L 2012/5626 Network management, e.g. Intelligent nets
• CPC Class Codes: H04L 41/0823 characterised by the purposes of a change of settings, e.g. optimising configuration for enhancing reliability for optimising operational conditions of wireless networks H04W24/02
• CPC Class Codes: H04L 41/0826 for reduction of network costs H04L41/0833 takes precedence
• CPC Class Codes: H04L 41/0889 Techniques to speed-up the configuration process
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method of configuring a network. The network includes some physical devices, some hosts, and a network management tool. The method comprises the following steps. First, generate a set of leaf nodes. Each leaf node includes at least one physical device and connects to at least one host. Next, generate an adjacency matrix from said set of leaf nodes. Next, generate a set of interconnect nodes, the interconnect nodes connect the set of leaf nodes. Next, determine the resource availability for the set of interconnect nodes. Finally, configure the set of interconnect nodes and the set of leaf nodes after determining that sufficient resources are available.

Claims

1. A method of configuring a network, said method comprising the steps of:

(a) generating a set of leaf nodes, a first leaf node representing a first physical device being coupled to a first host on said network;

(b) generating an adjacency matrix for said set of leaf nodes;

(c) generating a set of virtual network nodes by using said adjacency matrix, said set of virtual network nodes connecting said set of leaf nodes;

(d) determining a resource availability for said set of virtual network nodes; and

(e) configuring said set of virtual network nodes in response to said determining said resource availability.

2. The method of claim 1 further comprising the step of generating a set of network nodes, said set of network nodes including a node corresponding to each physical device of a plurality of physical devices.

3. The method of claim 2 wherein the step of generating said set of network nodes further comprises the steps of:

(a) determining a type of a physical device of said plurality of physical devices;

(b) identifying other physical devices of said type of said plurality of physical devices and said physical device as a group, said other physical devices being connected to said physical device; and

,

(c) generating a network node representing said group.

4. The method of claim 2 further comprising the step of generating said adjacency matrix from said set of network nodes.

5. The method of claim 1 wherein said generating said set of virtual network nodes comprises the steps of:

(a) merging said set of leaf nodes into said set of virtual network nodes;

(b) for each virtual network node in said set of virtual network nodes, performing the steps of;

(i) finding an adjacent node for each virtual network node, and

(ii) adding said adjacent node to an interconnect node set; and

(c) merging said set of virtual network nodes and said interconnect node set.

6. The method of claim 1 further comprising the step of determining a link availability between each virtual network node in said set of virtual network nodes.

7. A network management tool comprising:

(a) a means for determining a set of nodes corresponding to said set of physical devices;

(b) a means for generating an adjacency matrix for said set of nodes;

(c) a means for determining a set of virtual network nodes representing a subset of said set of physical devices that implement said virtual network, said means using said adjacency matrix;

(d) a means for determining a resource availability for said set of virtual network nodes; and

(e) a means for configuring said subset of physical devices to implement said virtual network.

8. The network management tool of claim 7 wherein said means for determining said set of nodes corresponding to said set of physical devices further comprises:

(a) a means for determining a type of a first physical device of said set of physical devices;

(b) a means for grouping other physical devices of said type of said set of physical devices, said other physical devices being connected to said first physical device; and

(c) a means for generating a network node representing said first physical device and said other physical devices.

9. The network management tool of claim 7 wherein said means for determining said set of virtual network nodes comprises:

(a) a means for determining a set of leaf nodes, a leaf node of said set of leaf nodes corresponding to each physical device in said virtual network; and

(b) a means for determining a subset of said physical devices that connect said set of leaf nodes.

10. The network management tool of claim 7 further comprising a means for determining a link availability between each virtual network node of said set of virtual network nodes.

11. A method of configuring a plurality of physical devices to form a virtual network, said method comprising the steps of:

(a) communicating with said plurality of physical devices to determine a topology of said plurality of physical devices, said topology comprising a list of said plurality of physical devices and a list of corresponding physical interconnections;

(b) generating a plurality of network nodes from said topology;

(c) generating a plurality of leaf nodes from said topology and a plurality of terminals coupled to said plurality of physical devices;

(d) determining a plurality of interconnect nodes from said plurality of leaf nodes and said plurality of network nodes; and

(e) configuring said plurality of leaf nodes and said plurality of interconnect nodes to support said virtual network.

12. The method of claim 11 wherein said generating said plurality of network nodes comprises the following steps:

if a first physical device is a first physical device type, then;

(a) finding all other physical devices from said plurality of physical devices that are physically connected to said first physical device and are said first physical device type; and

,

(b) creating a first network node representing said first physical device and said all other physical devices.

13. The method of claim 12 wherein said first physical device type is an ethernet switch.

14. The method of claim 12 wherein said first physical device type is a hub.

15. The method of claim 12 wherein said first physical device type is an ATM switch.

16. The method of claim 11 further comprising the step of:

creating an adjacency matrix representing said plurality of network nodes and physical interconnections between said plurality of network nodes.

17. The method of claim 11 wherein said determining said plurality of interconnect nodes comprises, for each leaf node, the steps of:

(a) finding an adjacent node that connects to said leaf node, and

(b) adding said adjacent node to said plurality of interconnect nodes.

18. The method of claim 11 wherein said configuring said plurality of leaf nodes and said plurality of interconnect nodes comprises the step of testing each link of said virtual network to determine whether sufficient free resources exist between said plurality of leaf nodes and said plurality of interconnect nodes.

19. The method of claim 11 wherein said configuring said plurality of leaf nodes and said plurality of interconnect nodes comprises the step of communicating configuration information to each of said plurality of leaf nodes and said plurality of interconnect nodes.

20. A computer-readable medium having a plurality of sequences of instructions stored thereon including sequences of instructions which, when executed by one or more processors, cause said one or more processors to perform the steps of:

(a) generating a set of leaf nodes, a first leaf node representing a first physical device being coupled to a first host on said network;

(b) generating an adjacency matrix for said set of leaf nodes;

(c) generating a set of virtual network nodes by using said adjacency matrix, said set of virtual network nodes connecting said set of leaf nodes;

(d) determining a resource availability for said set of virtual network nodes; and

(e) configuring said set of virtual network nodes in response to said determining said resource availability.

21. The computer-readable medium of claim 20 further causing the step of generating a set of network nodes, said set of network nodes including a node corresponding to each physical device of a plurality of physical devices.

22. The computer-readable medium of claim 20 wherein the step of generating said set of network nodes further comprises the steps of:

(a) determining a type of a physical device of said plurality of physical devices;

(b) identifying other physical devices of said type of said plurality of physical devices and said physical device as a group, said other physical devices being connected to said physical device; and

,

(c) generating a network node representing said group.

23. The computer-readable medium of claim 21 further causing the step of generating said adjacency matrix from said set of network nodes.

24. The computer-readable medium of claim 20 wherein the step of generating said set of virtual network nodes comprises the steps of:

(a) merging said set of leaf nodes into said set of virtual network nodes;

(b) for each virtual network node in said set of virtual network nodes, performing the steps of;

(i) finding an adjacent node for each virtual network node, and

(ii) adding said adjacent node to an interconnect node set; and

(c) merging said set of virtual network nodes and said interconnect node set.

25. The computer-readable medium of claim 20 further causing the step of determining a link availability between each virtual network node in said set of virtual network nodes.

26. A computer data signal embodied in a carrier wave and encoding a plurality of sequences of instructions which, when executed by one or more processors, cause said one or more processors to configure a virtual network, said plurality of sequences of instructions including sequences of instructions which, when executed by said one or more processors, cause said one or more processors to perform the steps of:

(a) generating a set of leaf nodes, a first leaf node representing a first physical device being coupled to a first host on said network;

(b) generating an adjacency matrix for said set of leaf nodes;

(c) generating a set of virtual network nodes by using said adjacency matrix, said set of virtual network nodes connecting said set of leaf nodes;

(d) determining a resource availability for said set of virtual network nodes; and

(e) configuring said set of virtual network nodes in response to said determining said resource availability.

27. The computer data signal of claim 26 further causing the step of generating a set of network nodes, said set of network nodes including a node corresponding to each physical device of a plurality of physical devices.

28. The computer data signal of claim 26 wherein the step of generating said set of network nodes further comprises the steps of:

(a) determining a type of a physical device of said plurality of physical devices;

(b) identifying other physical devices of said type of said plurality of physical devices and said physical device as a group, said other physical devices being connected to said physical device; and

,

(c) generating a network node representing said group.

29. The computer data signal of claim 27 further causing the step of generating said adjacency matrix from said set of network nodes.

30. The computer data signal of claim 26 wherein the step of generating said set of virtual network nodes comprises the steps of:

(a) merging said set of leaf nodes into said set of virtual network nodes;

(b) for each virtual network node in said set of virtual network nodes, performing the steps of;

(i) finding an adjacent node for each virtual network node, and

(ii) adding said adjacent node to an interconnect node set; and

(c) merging said set of virtual network nodes and said interconnect node set.

31. The computer data signal of claim 26 further causing the step of determining a link availability between each virtual network node in said set of virtual network nodes.