Method and Apparatus for Configuring a Virtual Network

.COPYRGT.1994, 1995 SynOptics Communications Inc. A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent file or the records, but otherwise reserves all copyright rights whatsoever.

1. Field of the Invention

The present invention relates to the field of computer networking. In particular, the present invention describes a method and apparatus for configuring physical devices in a network to create a virtual network.

2. Description of Related Art

Computer networks continue to grow in size and complexity. In a network, physical devices are interconnected with communication media. Computers on the network may be grouped into virtual networks. A virtual network allows computers to appear to be physically connected on their own network. This enables, for example, all people in the finance department of a company to have their computers communicating in one virtual network.

One difficulty in creating virtual networks has been that a network administrator must configure the physical devices in the network. This configuration process can be very complex. For example, assume that the people of the finance department are located in a number of buildings on a campus. Ethernet networks, token ring networks, and ATM networks may connect all the computers used in the finance department. That is, one part of the department may be connected to the network using an ATM switch, while another part of the department may be connected to the network via an ethernet network. Finally, another part of the finance department may be connected via a token ring network.

To create a virtual network, the network administrator must determine whether all the computers of the finance department can be connected to form one virtual network. The administrator must also determine whether the network has sufficient resources to do this. Typically this process requires a great deal of time and effort on the part of the network administrator. Through a process of trial and error, the network administrator would attempt to configure a set of physical devices that would support the virtual network. If during the configuration process one physical device could not be configured (e.g. because insufficient resources were available at the device), the network administrator would have to determine a different set of physical devices. Sometimes the path would be longer than would be necessary, and therefore possibly less efficient. In other cases, not until multiple configuration attempts had been made would the network administrator realize that the desired virtual network could not be realized.

Further complications occur when multiple network administrators work on the same network. Each network administrator may not have an up to date understanding of the entire network.

Therefore, creating virtual networks can be complex and time consuming. What is needed is an improved method and apparatus for configuring a virtual network.

A method and apparatus for determining a connection path between two physical devices in a heterogeneous network is described.

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.

Although a great deal of detail has been included in the description and figures, the invention is defined by the scope of the claims. Only limitations found in those claims apply to the invention.

The present invention is illustrated by way of example, and not limitation, in the figures. Like references indicate similar elements.

FIG. 1 illustrates a computer system upon which one embodiment of the present invention can be implemented.

FIG. 2 illustrates a network including a network management tool.

FIG. 3 illustrates one embodiment of a method of determining the physical connections in a network.

FIG. 4 illustrates one embodiment of a method of determining the path to connect virtual network nodes.

FIG. 5 illustrates one embodiment of a method of finding an adjacent node for the current vnet node.

FIG. 6 illustrates on embodiment of a method of determining resource availability in a network.

FIG. 7 illustrates a network that can be configured to support a virtual network.

FIG. 8 illustrates a second network that can be configured to support a virtual network.

FIG. 9 illustrates the network of FIG. 8 after grouping physical devices into nodes.

A method and apparatus for determining a connection path between two physical devices in a heterogeneous network is described. In the following description, specific details are set forth such as adjacency matrix contents, etc., in order to provided a thorough understanding of the present invention. In other instances, known circuits, structures and techniques have not been shown in detail in order not to obscure the present invention.

In one embodiment of the present invention, a network management tool connects to the network and configures a virtual network. The network management tool determines: the capabilities of the physical devices on the network; the necessary configuration information for each physical device; and, the physical links between the physical devices (that is, the network management tool determines all the interconnections between all the nodes in the network). Next, the network management tool finds the virtual network's leaf nodes and all the nodes that interconnect them. Then, the network management tool determines the availability of links between all the leaf nodes and the interconnect nodes. That is, the resource availability for the physical devices are checked and determined whether a path can be created between all the physical devices of the virtual network. Once the resource availability has been determined, the network management tool configures the virtual network nodes.

In another embodiment of the present invention, a network management tool modifies a presently existing network by adding a host to, or subtracting a host from, a virtual network.

To aid in the understanding of this description, the following definitions are presented,

Host: A terminal on a network. Typically, a host is a computer. Typically, a host will have a unique address within a virtual network.

Virtual Network (Vnet): In a network of physical devices, a vnet is a particular configuration of the physical devices that allows a group of hosts to communicate.

Node: A logical or physical device in a network.

Configuration Node: A configuration node is a node that can be configured to allow communication between media coupled to that configuration node; for example, a hub, a group of ethernet switches or an ATM network. In one embodiment of the present invention, knowledge of the internal topology of a switched network, such as an ATM network, is not needed. Therefore, related physical switching devices can be grouped into one logical configuration node.

Network Node List: The list of nodes in the network.

Leaf Node List: The list of nodes connected to the hosts that are to be in one vnet.

Interconnect Node List: The list of nodes that connect the leaf nodes. The nodes in the interconnect node list must be configured in order for the vnet to be created or modified.

Virtual Network Node List: the list of all the nodes which will be configured in the construction or modification of the virtual network.

Interconnection List: The list of connections (links) between configuration nodes.

FIG. 1 illustrates a computer system 100 upon which an embodiment of the invention can be implemented. The computer system 100 includes a bus 101, or other communications hardware and software, for communicating information, and a processor 109, coupled with the bus 101, is for processing information. The processor 109 can be a single processor or a number of individual processors that can work together. The computer system 100 further includes a memory 104. The memory 104 can be random access memory (RAM), or some other dynamic storage device. The memory 104 is coupled to the bus 101 and is for storing information and instructions to be executed by the processor 109. The memory 104 also may be used for storing temporary variables or other intermediate information during the execution of instructions by the processor 109. The computer system 100 also includes a ROM 106 (read only memory), and/or some other static storage device, coupled to the bus 101. The ROM 106 is for storing static information such as instructions or data.

The computer system 100 can optionally include a data storage device 107, such as a magnetic disk, a digital tape system, or an optical disk and a corresponding disk drive. The data storage device 107 can be coupled to the bus 101.

The computer system 100 can also include a display device 121 for displaying information to a user. The display device 121 can be coupled to the bus 101. The display device 121 can include a frame buffer, specialized graphics rendering devices, a cathode ray tube (CRT), and/or a flat panel display. The bus 101 can include a separate bus for use by the display device 121 alone.

An input device 122, including alphanumeric and other keys, is typically coupled to the bus 101 for communicating information, such as command selections, to the processor 109 from a user. Another type of user input device is a cursor control 123, such as a mouse, a trackball, a pen, a touch screen, a touch pad, a digital tablet, or cursor direction keys, for communicating direction information to the processor 109, and for controlling the cursor's movement on the display device 121. The cursor control 123 typically has two degrees of freedom, a first axis (e.g., x) and a second axis (e.g., y), which allows the cursor control 123 to specify positions in a plane. However, the computer system 100 is not limited to input devices with only two degrees of freedom.

Another device which may be optionally coupled to the bus 101 is a hard copy device 124 which may be used for printing instructions, data, or other information, on a medium such as paper, film, slides, or other types of media.

A sound recording and/or playback device 125 can optionally be coupled to the bus 101. For example, the sound recording and/or playback device 125 can include an audio digitizer coupled to a microphone for recording sounds. Further, the sound recording and/or playback device 125 may include speakers which are coupled to digital to analog (D/A) converter and an amplifier for playing back sounds.

A video input/output device 126 can optionally be coupled to the bus 101. The video input/output device 126 can be used to digitize video images from, for example, a television signal, a video cassette recorder, and/or a video camera. The video input/output device 126 can include a scanner for scanning printed images. The video input/output device 126 can generate a video signal for, for example, display by a television.

Also, the computer system 100 can be part of a computer network (for example, a LAN) using an optional network connector 127, being coupled to the bus 101. In one embodiment of the invention, an entire network can then also be considered to be part of the computer system 100.

An optional device 128 can optionally be coupled to the bus 101. The optional device 128 can include, for example, a PCMCIA card and a PCMCIA adapter. The optional device 128 can further include an optional device such as modem or a wireless network connection.

FIG. 2 illustrated a network 200 having hosts, physical devices, and a network management tool 210.

In one embodiment of the present invention, the network management tool 210 includes an application that allows the network administrator to provide the network management tool 210 with a set of hosts (in this example, host A222, host B224 and host C226) that are to be part of one virtual network. The network management tool 210 communicates with the physical devices in the network 200 to determine: the capabilities of the physical devices in the network 200 (for example, an ATM device requires configuration information different from a shared media device); the necessary configuration information for each physical device; and, the physical connection of the devices. The management tool 210 attempts to determine at least one possible set of physical devices that will support the virtual network. The network management tool 210 configures that set of physical devices to create the virtual network (vnet). Note the network management tool 210 saves the network administrator from having to attempt to configure the network 200. Without requiring further intervention by the network administrator, the network management tool 210 will configure the physical devices supporting the virtual network or will indicate that the virtual network cannot be created.

Network 200 includes the following hosts: host A 222, host B 224, host C 226, host F 262, host G 264, host H 266 an host I 286. Each host can be a computer such as computer system 100. Network 200 includes the following physical devices: ethernet switch A 232, ethernet switch B 234, hub A 242, hub B 244, hub C 246 and ATM switch 250. An ethernet switch can be, for example, model 28115 LattisSwitch, available from Bay Networks, Inc., of Santa Clara, Calif. A hub can be, for example, System 5000, available from Bay Networks, Inc. An ATM switch 250 can be, for example, model 10114, Lattis Cell, available from Bay Networks, Inc. Note that separate physical devices can be enclosed in one chassis yet still be considered separate physical devices.

Assume that the network administrator wishes to connect host A 222, host B 224 and host C 226 as one virtual network. Host A 222, host B 224, and host C 226 may be the computers used by the people of the finance department in a company. To create the virtual network, the network administrator would typically input the request to the network management tool 210. The network management tool 210 would then, after performing the processes described below, create the virtual network 280. The virtual network is created by identifying the physical devices that need to be configured, and then configuring those physical devices. In this example, ethernet switch B 234, ethernet switch A 232, hub B 244, and ATM switch 250 (configured physical devices 270), would all be configured by the network management tool 210 to create the virtual network 280. Note that hub A 242 and hub C 246 would not be configured because the network management tool 210 would determine that no configuration of these physical devices was necessary.

In prior art systems, the network administrator would have to determine which physical devices should be configured and then configure those physical devices. In a network the size of network 200, this may not be too time consuming (for example, the physical devices may be located in different building or even different cities). However, in a larger network, determining how to configure the physical devices in the network to achieve a virtual network can be difficult and time consuming. The network administrator: needs to have an up to date view of the network; must determine how to configure the physical devices on the network to achieve a virtual network; and must issue the commands to configure those physical devices. When the network includes loops (i.e. multiple paths between two devices), the complexity of the problem increases. This introduces multiple solutions to the problem of creating the virtual network. The network administrator may not discover the best configuration of physical devices to create the virtual network. One embodiment of the present invention determines the best configuration of physical devices even when loops are present in the network.

FIG. 3 illustrates one embodiment of a method of determining the physical connections in a network. This method could be implemented in an network management tool 210 executing on a computer system 100.

At step 310, a test is made to determine whether all the physical devices in the network have been processed. In one embodiment, this is performed by the network management tool 210 accessing a database. The database contains a list of all the physical devices in the network and all the physical interconnections between the physical devices. Such a database can be created by the network administrator. In another embodiment, the information includes a topology which is obtained from an autotopology system. One such autotopology system, Optivity, is available from Bay Networks, Inc., of Santa Clara, Calif. Such an autotopology system determines all the physical devices on the network and their physical interconnections. In any case, what is important in step 310 is that the physical devices in the network and their interconnections are identified.

If all the physical devices have been processed, then step 320 through step 390 create nodes representing one or more physical devices. Some physical devices can be grouped into a single node where those physical devices can configure themselves to create a path between any two connections to the group. This reduces the complexity of the creation of a vnet because fewer nodes need be processed later on.

At step 320, a test is made to determine whether the physical device is an ethernet switch. If the physical device is an ethernet switch, then at step 330 all the ethernet switches physically connected to that ethernet switch are found. At step 340, an ethernet switch node is created from all the ethernet switches found connected in step 330. This effectively amalgamates all the ethernet switches, that are physically connected, into one node.

At step 350, the newly created node is added to a network node list.

If the physical device is not an ethernet switch, then a test at step 360 is performed to determine whether the physical device is a shared media hub such as a System 3000 available from Bay Networks, Inc. If the physical device is a shared media hub, then at step 365, the network management tool creates a node for the shared media hub. Next, at step 350, the new node is added to the network node list.

If the physical device is neither an ethernet switch nor a shared media hub, then a test is made at step 270 to determine whether the physical device is an ATM switch. If the physical device is an ATM switch, then at step 380, all the other ATM switches physically connected to that ATM switch are found. Next, at step 390, and ATM switch node is created from all the ATM switches connected to the ATM switch of step 370. This is analogous to step 340. Then, at step 350, the new node is added to the network node list.

In another embodiment, other types of physical devices can be identified by a node. For example, a token ring network physical device could be identified by a node. A token ring node would then be added to the network node list.

Once all the physical devices have been included in a node in the network node list, then, from step 320, step 395 is executed. At step 395, an adjacency matrix is created for the network node list. The adjacency matrix is created for each node in the network node list. The adjacency matrix includes, for each node, the list of other nodes that are physically connected to that node. That is, the adjacency matrix identifies the physically connected peers for each node in the network. This adjacency matrix can then be used to determine the required virtual network.

In another embodiment of the present invention, the adjacency matrix includes weights. In one embodiment, a weight of one represents no connection. A weight less than one represents a particular type of communications media/amount of bandwidth. In one embodiment, lower weights are given to faster communications links. Therefore, in one embodiment, when presented with multiple possible configurations for a virtual network, the network management tool 210 can compare the weights of the configurations to determine the best configuration. The best configuration would be the one with the lowest value.

Note that many different criteria can be used to determine the best path. For example, the best path may use physical devices experiencing the least load.

This invention is not limited to, for example, using weights of decreasing value. What is important is that some correlation between the physical characteristics of the physical devices of the network and some objective criteria required by the network administrator can be determined.

FIG. 4 illustrates one embodiment of a method of determining the path to connect the nodes of virtual network. The path includes a set of physical devices and the connections between the physical devices. This embodiment can be executed by network management tool 210 executing on computer system 100.

This embodiment determines the best path by determining the smallest set of nodes needed to connect the host of the virtual network. Because each virtual network uses the smallest set of nodes the physical devices in the network are used to their fullest potential. This helps keep the number of physical devices required in the network to a minimum, thereby reducing the cost of the network. Also, because the smallest set of nodes is found, the configuration time is kept to a minimum. This allows a network administrator more time to experiment with different virtual networks.

As mentioned above in another embodiment, the best path may be determined using other criteria (e.g. fastest communications path, most available bandwidth path, most amount of resources available path).

At step 410, the nodes coupling to the hosts (the leaf nodes) are added to the vnet node list. (Each host is connected to one node in the network.) The leaf node list can be generated when the network node list is created.

At step 420, a test is made to determine whether all the leaf nodes have been processed in the vnet node list. If all the leaf nodes have not been processed, then step 430; is executed.

At step 430, a node from the vnet node list is assigned to be the current vnet node.

At step 440, an adjacent node to the current vnet node is searched for. This is described in FIG. 5.

At step 450, a test is made to determine whether an adjacent node has been found. If an adjacent node is found, then, at step 455, the adjacent node is added to the interconnect node list. The necessary link is also recorded. If the adjacent node is already in the interconnect node list, and the corresponding link has been noted, then no further action is taken. If no adjacent node is found, then at step 460, an error is noted in the adjacency list. This indicates that the virtual network cannot be created given the present physical devices and interconnections of the network.

At step 493, the interconnect node list is merged into the vnet node list. The vnet node list represents the set of nodes needed to create the required virtual network, while the recorded links indicate how the vnet node list nodes are connected to form the vnet.

FIG. 5 illustrates one embodiment of a method of finding an adjacent node for a node. In one embodiment of the present invention, the method of FIG. 5 is implemented in a subroutine that has an input a list of nodes. When called from step 440, the input to this subroutine is the current vnet node, the vnet node list and the interconnection node list.

At step 510, a test is made to determine whether all the nodes in the node list have been tested.

Assuming all the nodes have not been tested, then at step 520, a test is made to determine whether the test node is in the adjacency list of the present node. In one embodiment of the present invention this is performed by addressing the adjacency matrix using the test node and the present node. Optionally, if the test node is in the adjacency list of the present node, then at step 570, a link is recorded between the present node and the test node. This recording can be done in an interconnect node list. Then at step 580, a return from the subroutine is made indicating that an adjacent node (the test node) has been found.

At step 530, if the test node is not in the adjacency list of this leaf node, then the adjacency list of the test node is accessed.

At step 540, this subroutine is called for each of the nodes in the adjacency list of the test node.

At step 550, a test is made to determine whether an adjacent node has been found. If an adjacent node has been found, then at step 560, the subroutine returns indicating that an adjacent node has been found. If an adjacent node has not been found, then step 510 is executed.

If all the leaf nodes have been tested and an adjacent node has not been found, then the subroutine exists indicating that no adjacent node has been found.

FIG. 6 illustrates one embodiment of a method for determining the resource availability of a network. That is, the physical devices used to create the virtual network must be able to support the links in the path of the virtual network. The method of FIG. 6 can be performed by the network management tool 210 executing on computer system 100.

At step 610, a test is performed to determine whether all the links in the interconnection list have been processed. If not all the links have been processed, then at step 630, a test is made to determine whether there are resources available between the two nodes that form the link. In one embodiment of the present invention, this is done by accessing the database used in FIG. 3. The database indicates whether physical devices have sufficient resources to make a link. For example, the first physical device might be a hub having a coaxial connection. A second physical device might be another hub having a coaxial connection. The two hubs would be physically connected via a coaxial cable. The test of step 630 would then determine whether the coaxial cable is available for use for the virtual network.

If the resources are available, then at step 620, the exact link connection is recorded. However, if the resources are not available between the two nodes, then at step 640, a record is kept of a failed link interconnection. Step 610 through step 640 are executed for each link in the interconnection list. If there are any failed links then these links can be displayed for the network administrator. The failed links indicate that a particular connection between two physical devices is not available. The network administrator may then modify the network to allow the network to be configured to create the virtual network.

In one embodiment of the present invention not only must the resources between the nodes be tested, but, where a shared media hub is to be a configured physical device 370, the resources within the hub must be tested as well. For example in one type of shared media hub a finite number of ports may be interconnected on that particular hub. Therefore, although two physical devices may be physically connected by ports and those two physical devices may have that resource available, one of the two hubs may not be able to internally support a connection to one of the ports. Therefore, the link could not be made. This failure would then be recorded for the network administrator.

Once the vnet node list has been created, the nodes in that list can be configured to implement the vnet. In one embodiment of the present invention, each node is configured by the network management tool 210 using the link information from the connections list. The following pseudo code illustrates one embodiment of a method for configuring the nodes given the vnet list.

In one embodiment of the present invention, if all the nodes cannot be configured, then an attempt to undo the configuration is made. If this is not possible, or if the network administrator does not want this done, then the network management tool displays an error message.

The modification of an already existing vnet is performed using a method similar to the creation of the vnet. For simplicity, the modification method will be described in terms of a one host move or reassignment.

Notice, that the modification will be performed the same way as the vnet creation if the host's leaf node is not part of the vnet.

FIG. 7 illustrates a network upon which one embodiment of the present invention can operate. This network includes a number of hosts which are to be connected in a vnet. To create the vnet, the physical devices on the network need to be configured.

The physical devices of this network have already been converted into nodes using the method of step 310 through step 390. In this example, no physical devices can be grouped with other physical devices (as in step 340 and step 390). Lines between the nodes represent physical connections.

This paragraph describes the interconnections of the network of FIG. 7. Nodes are represented by the letter N. The network of FIG. 7 contains both configuration nodes and hosts. Hosts A B, C, D and E are to be included in one vnet. The network includes configuration nodes N1 710, N2 720, N3 780, N750, N5 740, N6 770, N7 730, N8 760 and N9 790. N1 710 is physically connected to N2 720, N4 750 and N3 780. N2 720 is connected to N1 710 and A. N3 780 is connected to N9 790, N1 710 and B. N4 750 is connected to N1 710, N5 740 and N6 770. N5 740 is connected to N4 750, N7 730 and N8 760. N6 770 is connected to N4 750 and C. N7 730 is connected to D and N5 740. N8 760 is connected to N5 740 and E.

Before executing the remaining steps of FIG. 3, the status of the various lists is as follows:

After executing steps 310 through step 390, the status of the lists is as follows:

The embodiment of FIG. 3 creates the adjacency matrix below. An "x" indicates an adjacency.

In the embodiment of FIG. 4, at step 410, the leaf nodes N2 720, N3 780, N6 770, N7 730, and N8 760, are added to the vnet node list. Then step 420 through step 450 is repeated for each node in the vnet node list having the following results.

The final results are shown below.

Next step 610 through step 640 are executed to ensure that the physical devices identified by each link in the interconnection list have the resources needed to create each link. Finally, the nodes in the vnet node list are configured.

FIG. 8 illustrates a network similar to the network of FIG. 7. However, the network of FIG. 8 includes physical devices that can be grouped into nodes.

This paragraph describes the interconnections of the network of FIG. 8. The network includes the following physical devices: ethernet switch5 820, ethernet switch1 880, ethernet switch 2 840, ethernet switch3 850 and ethernet switch4 860. The network also includes hosts A, B, C, D and E. N1 710 is physically connected to ethernet switch 5 820, N4 750, N6 770 and ethernet switch 1 880. Ethernet switch 5 820 is physically connected to N1 710, ethernet switch 2 840 and A. N4 750 is physically connected to N1 710 and N6 770. Ethernet switch1 880 is physically connected to N1 710 and B. Ethernet switch2 840 is physically connected to ethernet switch5 820, ethernet switch3 850 and ethernet switch4 860. Ethernet switch3 850 is physically connected to ethernet switch2 840 and D. Ethernet switch4 860 is physically connected to ethernet switch2 840 and E.

After performing step 310 through step 390, the network of FIG. 8 is logically represented as the network of FIG. 9. When step 320 is executed for ethernet switch 5 820, step 330 and step 340 are performed. Step 330 causes ethernet switch2 840, ethernet switch3 850, and ethernet switch4 860 to be found. Step 340 creates a node ethernet switch SN2 910. Ethernet switch SN2 910 represents a node for these physical ethernet switches. Similarly, ethernet switch1 880, not physically connected with another ethernet switch, is grouped into a separate node ethernet switch SN1 900.

Step 395 then creates the following adjacency matrix.

Next, leaf nodes are added to the vnet node list, at step 410, and step 420 through step 450 are executed. The following results are achieved.

Ensure that there is at least one free link available.

After ensuring that sufficient resources are available, the network is configured as described above.

A method and apparatus for determining a connection path between two physical devices in a heterogeneous network has been described.