CN105391635A - Network virtualization method based on software defined network (SDN) - Google Patents

Abstract

The invention discloses a network virtualization method based on a software defined network (SDN). The network virtualization method comprises the steps of obtaining SDN topology information by a controller through detection in network initialization; creating a virtual network sheet, calling a virtual network generation module by the created virtual network sheet, adding host computers into the virtual network after network creation is finished, adding the host computers into the virtual network sheet, and communication between a certain host computer and another host computer is required, if a switch has a matched flow item, directly forwarding a data package, and if the switch has no matched flow item, transmitting the data package to the controller, calling an information interception module by the controller for intercepting the data package, calling an information analyzing module by the information interception module, waiting for a result which is returned from the information analyzing module, and determining whether to discard the data package. The network virtualization method can be used for flexibly creating a virtual network and is totally driven according to a user requirement and has relatively high expandability. Furthermore the invention provides a relatively good solution for improving network throughput and preventing competition of busy links.

Description

A method of network virtualization based on SDN

technical field

The invention relates to the field of computer network virtualization, in particular to an SDN-based network virtualization method.

Background technique

Virtualization technology has always been inseparable from the development of the network. In order to solve the current Internet "ossified" problem and stimulate innovation in future network research, the concept of network virtualization was proposed. Network virtualization technology refers to the use of abstraction, distribution and isolation The mechanism realizes the virtualization of nodes and links, and builds a diversified virtual network that coexists but is isolated from each other by sharing the underlying physical resources. The physical network can realize the reasonable allocation and management of physical resources according to the dynamically changing virtual resource requests. Researchers use virtualization technology to build logical networks based on existing network architectures to meet specific business needs. Such as virtual local area network for user isolation, virtual private network for connecting remote users, etc.

Now, many groups and academic institutions at home and abroad propose to use network virtualization to build a network experiment platform, and use network virtualization technology as the infrastructure for building the next generation Internet. Including GENI (Global Environment for Network Innovations), which aims to build a general and open large-scale experimental platform to solve the shortcomings of the traditional Internet in terms of security, reliability and management. Its design goal is to build a programmable, virtualized , A secure global network that satisfies different types of network interconnections. GENI can enable users to access and control the underlying resources; the PlantLab project, started in 2003, the initial architecture was jointly designed by Larry Peterson of Princeton University, Tom Anderson of the University of Washington, and David Culler of the University of California, Berkeley. It is an open , A global experimental platform for next-generation Internet and services. Computing resources, memory resources, and network resources of nodes are shared by multiple virtual machines. A virtual machine composed of multiple virtual machines is called a resource slice of PlantLab. Multiple resource slices run on PlantLab at the same time, and logically do not affect each other; the VegaNet (VirtualGigabitNetwork) project, started in 2009, was initiated by Beijing University of Science and Technology, Tsinghua University, and Beijing University of Posts and Telecommunications. The main features of VegaNet include the introduction of real user traffic, support for node and link fault injection, and synchronization of underlying network faults. The virtual router is implemented based on a real commercial router platform, supports high-bandwidth virtual network traffic, and the protocol suites running in the virtual network are independent. Based on the underlying physical network, the virtual network is transparent to the underlying physical network; the 4WARD project is a sub-project of the European Union's Seventh Science and Technology Framework Program EP7 in the field of network technology research, which was launched in January 2008. Its goal is to overcome the shortcomings of existing communication networks through innovation and build an architecture that can coexist with multiple networks at the same time. The 4WARD virtualization framework allows multiple networks to run on a common platform, realizes the coexistence of multiple network architectures through the virtualization of network resources at the operator level, and only allows multiple networks to coexist at the link layer and the application layer at the same time as the existing Internet The difference is that 4WARD should also be able to coexist multiple networks at the network layer and transport layer. 4WARD can support heterogeneous network virtualization, heterogeneous end users and new network protocols at the same time. Its main research content includes network virtualization technology, the principle and content of new architecture, etc.

SDN first originated from the cleanstate project of Stanford University. It is an innovative network architecture. Its core idea is to decouple the forwarding plane and the control plane. Devices are managed. At present, OpenFlow has been widely used as a standard interface, and the central controller implements refined monitoring and management of physical switches through the OpenFlow protocol. At the same time, SDN has the advantages of natural network virtualization, especially for network virtualization applications in data centers. Due to deployment requirements, virtualization requires a centralized control network architecture, and the SDN network is precisely a centralized management network architecture.

After searching, there is no patent application for a technical solution closer to the technical solution of this application on the website of the National Patent Office and the website of foreign patent offices, and there is no journal document that is closer to the technical solution of this application, and there is no realization of creating a virtual network based on SDN. current technology.

Contents of the invention

The purpose of the present invention is to provide a network virtualization method based on SDN to address the defects and deficiencies in the above-mentioned prior art. This method can not only create a virtual network based on a MAC address, but also create a virtual network based on an IP address. The virtual network can be Carries specific application layer energy or certain traffic from or to the host.

The present invention is achieved by adopting the following technical solutions:

A method for network virtualization based on SDN, characterized in that:

Step 1, when the network is initialized, the controller obtains the SDN network topology information through detection, including switch information and link information;

Step 2, when the network is initialized, no virtual network exists, and all underlying network resources are temporarily unavailable;

Step 3, the prerequisite for using network resources is to obtain a virtual network slice, otherwise no network resources can be used, create a virtual network slice, and go to step 4;

Step 4: Create a virtual network slice and call the virtual network generation module. The virtual network generation module collects information on various request parameters from users, and creates a virtual network slice according to the request parameters. The request parameters include the virtual network ID, name, traffic isolation type, and bandwidth requirements. , after the creation is complete, add a host to the virtual network and go to step 5;

Step 5. Add hosts to the virtual network slice. A virtual network is a collection of hosts that share resources in the virtual network. The hosts added to the virtual network slice are based on the host's MAC address or IP address, but the same virtual network It can only be added based on one method, such as adding only the host MAC address or only adding the host IP address. After the host is added, go to step 6;

Step 6. When a host needs to communicate with another host, if the switch has a matching flow entry, it will directly forward the data packet. If the switch does not have a matching flow entry, the data packet will be sent to the controller, and go to step 6. 7;

Step 7, the controller calls the message interception module to intercept the data packet, the message interception module calls the message analysis module, turns to step 8, waits for the result returned by the message analysis module, and decides whether to discard the data packet;

Step 8: The message parsing module parses the data packet, and queries whether the data packet comes from a certain virtual network. If the query result belongs to a certain virtual network and meets the relevant parameters of the virtual network, the message interception module is notified to allow the data packet to pass and deliver the flow Table, otherwise the notification message interception module discards the packet;

To check whether the data packet comes from a certain virtual network, you need to call the virtual network mapping module, and go to step 9;

Step 9, the virtual network mapping module queries the mapping relationship, determines whether the data packet belongs to a certain virtual network, and at the same time determines the relevant parameters of the virtual network, and determines the processing flow of the data packet according to the relevant parameters, such as calling the traffic isolation module and generating bandwidth virtualization routes module, if you need to call the traffic isolation module, go to step 10, if you need to call the bandwidth virtualization routing generation module, go to step 11;

Step 10, if the carried traffic is specified in the initial stage of virtual network creation, the traffic isolation module isolates the traffic carried by all non-virtual networks, otherwise it will not isolate any type of traffic;

Step 11, if the bandwidth requirement is specified in the initial stage of virtual network creation, the bandwidth virtualization route generation module first calls the MM_ATT algorithm to calculate a route, installs a flow table on the path, and then connects the edge switches connected to all hosts in the virtual network Set the rate-limited queue on the outbound port.

The virtual network generating module is used to generate a logical virtual network slice from a user virtual network request, the generation of the virtual network originates from the user's request, the user determines the request parameters, and the controller generates the virtual network slice data structure, and maintains A map of all virtual network related parameters.

The message interception module is used to intercept all packet_in messages from the underlying physical network. When the network is initialized, any physical network resources cannot be used, and all unmatched packets will be forwarded to the controller through the packet_in message; only virtual network, and the packet_in message belongs to the flow of a certain virtual network, after passing through the message parsing module, the message is allowed to pass, otherwise the message is discarded.

Described message parsing module, for the packet intercepted by message intercepting module, message parsing module parses out relevant information, as source IP address, purpose IP address, source TCP/UDP port number, purpose TCP/UDP port number, source MAC address , the destination MAC address and the port number of the incoming switch; at the same time, it is determined whether the message is a broadcast message or a DHCP message, and the intercepting module does not intercept such messages.

The virtual network mapping module is used to manage all virtual network mapping relationship data structures, including mapping from virtual network ID to virtual network, mapping from virtual network ID to virtual network name, mapping from virtual network ID to virtual network host set, IP Address-to-MAC address mapping and host-to-switch port mapping. These mapping data structures are the core data structures of the virtual network mapping module.

The traffic isolation module is used to isolate the specific traffic of the application layer, such as HTTP, FTP and P2P traffic; if the traffic to be isolated is specified when the virtual network is created, the traffic isolation module processes the request and installs a traffic flow on all switches on the path Tables, these flow tables only match specific packets to achieve exact matching. For example, the following fields are exactly matched: inbound switch port, source MAC address, destination MAC address, source IP address, destination IP address, source transport layer port, and destination transport layer port.

The bandwidth virtualization routing generation module is used to complete the generation of bandwidth virtualization routing. Bandwidth virtualization means bandwidth limitation and isolation for virtual networks. Generally, the minimum or maximum bandwidth required for virtual networks is set, and MM_ATT is used to The algorithm finds a route for the flow, and sets a number of rate-limiting queues on the outbound ports of the edge switches connected to all virtual network hosts to realize the rate limit of the flow and the generation of routes.

The formal description of the MM_ATT algorithm is as follows: Given a network G(V, E), source node s∈V, destination node d∈V, bandwidth requirement b∈R. For ?(i, j)∈E, link capacity Cij∈R, remaining capacity Lij∈R, it is required to find a path p with source node s and destination node d, so that the available bandwidth of path p is available≥b, and available is The minimum remaining capacity of all links on the path p requires the minimum bandwidth utilization rate U(p) of p, that is, U(p)=minU(pi); where V represents the node set, E represents the link set, and R represents the positive A set of real numbers, pi∈P, P represents the set of all paths from s to d;

Algorithm steps:

(1) Delete the links in graph G that do not meet the bandwidth requirements, and get a new graph G2=(V, E2).

(2) Calculate bandwidth utilization Uij for each link in Figure G2.

(3) Search all paths P from the source node s to the destination node d, while limiting the number of hops to be no greater than max_hop.

(4) Find a path with the minimum bandwidth utilization rate from the paths found in step (3).

Said step 1 further includes:

The controller periodically sends LLDP detection packets to detect the connection status of switches in the SDN network and maintain the topological relationship of the SDN network.

Said step 5 further comprises:

The virtual network to which the added host belongs is identified by the ID of the virtual network, and the port to which the host is connected to the switch is specified. The added host address is identified in a standard address format;

Said step 8 further includes:

Whether the query data packet comes from a certain virtual network is determined by the source address and destination address of the data packet. If the hosts represented by these addresses are all in the host collection of the virtual network, the data packet belongs to the virtual network, otherwise discard the packet directly;

Said step 9 further includes:

The virtual network mapping module first inquires whether the data packet belongs to a certain virtual network, and further inquires the parameter attributes of the virtual network. Specifically include: the virtual network only bears the specified source and destination addresses, isolation of application layer traffic, and bandwidth requirements. Among them, the "virtual network only bears the specified source and destination addresses" traffic, it is only necessary to simply judge whether the source and destination addresses of the data packets match in the network mapping module.

Described step 10 further comprises:

The traffic isolation module isolates the specified application layer traffic, including HTTP, FTP, P2P and other traffic. The transport layer ports used by these standard application layer traffic have been standardized. The traffic isolation module determines the source transport layer port and the destination transport layer port of the data packet. The application layer traffic of the upper layer realizes the purpose of traffic isolation.

Said step 11 further comprises:

After the bandwidth virtualization route generation module generates the route and delivers the flow table, the port rate of the edge switch needs to be set. Several rate-limited queues can be configured on the switch port. The queue specifies the queue id, the minimum sending rate of the queue, and the maximum sending rate of the queue, and then The switch adds a special flow entry, which indicates that the flow arriving from a certain port is directed to the previously configured port-specific queue, achieving the purpose of accurate flow rate limitation.

Compared with the prior art, the beneficial effects achieved by the present invention are as follows:

1. The system formed by this method can be used as an application module on the controller. It can be added and deleted flexibly in the form of a pluggable component. When the virtual network function is not needed, it can be added in the configuration file Just delete this item. This method can create a virtual network flexibly, is completely driven by user needs, and has good scalability. At the same time, it also proposes a better solution to improve the throughput of the network and avoid the competition of hot links.

2. This technical solution flexibly creates virtual networks and sets virtual network parameters by dividing virtual networks, and multiple virtual networks coexist and share network resources. This solution can not only create virtual networks based on MAC addresses, but also create virtual networks based on IP addresses. Virtual networks can carry specific application-layer energy or certain traffic from/to hosts.

3. This technical solution uses the MM_ATT algorithm to select a relatively idle link for a virtual network with bandwidth requirements. The routing principle of this algorithm is to find a path with the smallest path bandwidth utilization, so as to ensure the virtual network bandwidth requirements. Under the premise, the remaining bandwidth of the path is maximized, so that the overall throughput of the network is effectively improved. At the same time, after finding the route, set a rate-limiting queue on the outbound ports of all virtual network host edge switches, so that the traffic injected into the virtual network will not be greater than the required bandwidth requirements, thus well controlling the burst traffic.

Description of drawings

The present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments of the description, wherein:

FIG. 1 is a block diagram of an SDN-based network virtualization method according to the present invention.

FIG. 2 is a flow chart of communication between hosts in a virtual network based on MAC addresses according to an embodiment of the present invention.

FIG. 3 is a flow chart of communication between hosts in a virtual network based on IP addresses according to an embodiment of the present invention.

FIG. 4 is a schematic diagram of a pathfinding topology based on the MM_ATT algorithm according to an embodiment of the present invention.

detailed description

Example 1

As the best implementation of this technical solution, referring to the network topology in Figure 1 and the processing flow in Figure 2, this example first establishes a virtual network based on the MAC address, sets the relevant parameters of the virtual network and adds several hosts, and briefly describes the interaction between hosts in the virtual network The communication process, the specific steps are as follows:

Step 1, create a new virtual network slice1, specify the virtual network name and id, specify the establishment of a virtual network based on the MAC address, specify the traffic isolation parameter as http traffic, and specify the bandwidth requirement of the virtual network as bandwidth;

Step 2: Add hosts h1, h3, and h4 to the virtual network slice1, and their mac addresses are mac1, mac3, and mac4 respectively. At this time, the set of host addresses in the virtual network slice1 is {mac1, mac3, mac4};

Step 3, the host h1 sends an http data packet to h4, and the data packet first reaches the switch s1. If the switch s1 has no matching flow entry, the data packet will be forwarded to the controller for processing. If switch s1 has a matching flow entry, it forwards the data packet directly;

Step 4, the message interception module of the controller intercepts the data packet, and hands it over to the message parsing module for processing, and turns to step 5;

In step 5, the message parsing module obtains the data packet and begins to parse the data packet. If the parsing fails for any reason, the data packet is discarded, and the procedure goes to step 9. Otherwise, hand it over to the virtual network mapping module and go to step 6;

Step 6, the virtual network mapping module searches whether the source mac address and the destination mac address of the data packet are in the same virtual network according to the stored relevant mapping data structure, and if they are in the same virtual network, hand it over to the traffic isolation module and go to step 7. Otherwise, discard the data packet and go to step 9. Here mac1 and mac4 belong to the host set of virtual network slice1, so it will go to step 7;

Step 7, the traffic isolation module determines whether the traffic is the traffic that needs to be isolated in the virtual network by searching the parameters of the virtual network, if not, it will be handed over to the bandwidth virtualization route generation module for processing, and then go to step 8. Otherwise, the module needs to isolate the traffic, discard the data packet, and go to step 9. Here, the traffic isolation module does not need to isolate http traffic, so go to step 8 for processing;

Step 8: The bandwidth virtualization routing generation module searches whether the virtual network has a bandwidth requirement, and if there is no bandwidth requirement, directly sends the flow table and forwards it. Otherwise, routes are generated by the bandwidth virtualization routing generation module, flow tables are installed on all switches on the path, and rate-limiting queues are set on the outbound port of the edge switch connected to the host where the virtual network is located. Assuming that the generated route is: s1-s6-s5-s4, the rate limit queue will be set on the port s1-s6 of s1 and the port s4-s5 of s4, and the data packets from h1 to h4 will be directed to the port s1-s6 already The set speed limit queue, the data packets from h4 to h1 will be directed to the set speed limit queue of port s4-s5;

Step 9, the processing ends;

Example 2

As the best implementation of this technical solution, with reference to Figure 4, an example is given to illustrate how to use the MM_ATT algorithm to find a routing algorithm that improves network throughput and avoids competing hotspot links. The specific steps are as follows:

In step 1, the bandwidth utilization of each link needs to be calculated during the initialization process.

Step 2. Delete all links whose remaining bandwidth does not meet the bandwidth requirements of the virtual network. The deleted topology is shown in Figure 4. The number next to the link represents the bandwidth utilization rate of the link (unit: %).

Step 3, assuming that the route from s1 to s11 needs to be calculated, first we set max_hop=6, the algorithm will search the route from s1 to s11 in depth first, and the route found by the algorithm is: s1-s0-s3-s8-s10-s11, the The bandwidth utilization ratios on the path are 4, 6, 6, 6, 4, and it can be found that the maximum bandwidth utilization ratio on the path is 6, which is the minimum value of the bandwidth utilization ratios of all the paths from s1 to s11. If max_hop=5 is set, the route found by the algorithm is s1-s0-s3-s8-s11, and the bandwidth utilization rate on this path is 4, 6, 6, 8. It can be found that the maximum bandwidth utilization rate on this path is 8, although This number is larger than the number found by setting max_hop=6, but the path is shorter, which further reduces the search complexity. In actual use, you can reduce the search time by adjusting the size of the max_hop parameter.

In general, the algorithmic routing principle is to find a path as far as possible, so that the remaining bandwidth of the path is relatively sufficient, avoiding hot links, thereby increasing the throughput of the network to a certain extent, and achieving the purpose of effective utilization of network bandwidth resources.

Example 3

As another preferred embodiment of this method, it includes:

Step 1, when the network is initialized, the controller obtains the SDN network topology information through detection, including switch information and link information;

Step 2, when the network is initialized, no virtual network exists, and all underlying network resources are temporarily unavailable;

Step 3, the prerequisite for using network resources is to obtain a virtual network slice, otherwise no network resources can be used, create a virtual network slice, and go to step 4;

Step 4: Create a virtual network slice and call the virtual network generation module. The virtual network generation module collects information on various request parameters from users, and creates a virtual network slice according to the request parameters. The request parameters include the virtual network ID, name, traffic isolation type, and bandwidth requirements. , after the creation is complete, add a host to the virtual network and go to step 5;

Step 5. Add hosts to the virtual network slice. A virtual network is a collection of hosts that share resources in the virtual network. The hosts added to the virtual network slice are based on the host's MAC address or IP address, but the same virtual network It can only be added based on one method, such as adding only the host MAC address or only adding the host IP address. After the host is added, go to step 6;

Step 6. When a host needs to communicate with another host, if the switch has a matching flow entry, it will directly forward the data packet. If the switch does not have a matching flow entry, the data packet will be sent to the controller, and go to step 6. 7;

Step 7, the controller calls the message interception module to intercept the data packet, the message interception module calls the message analysis module, turns to step 8, waits for the result returned by the message analysis module, and decides whether to discard the data packet;

Step 8: The message parsing module parses the data packet, and queries whether the data packet comes from a certain virtual network. If the query result belongs to a certain virtual network and meets the relevant parameters of the virtual network, the message interception module is notified to allow the data packet to pass and deliver the flow Table, otherwise the notification message interception module discards the packet;

To check whether the data packet comes from a certain virtual network, you need to call the virtual network mapping module, and go to step 9;

Step 9, the virtual network mapping module queries the mapping relationship, determines whether the data packet belongs to a certain virtual network, and at the same time determines the relevant parameters of the virtual network, and determines the processing flow of the data packet according to the relevant parameters, such as calling the traffic isolation module and generating bandwidth virtualization routes module, if you need to call the traffic isolation module, go to step 10, if you need to call the bandwidth virtualization routing generation module, go to step 11;

Step 10, if the carried traffic is specified in the initial stage of virtual network creation, the traffic isolation module isolates the traffic carried by all non-virtual networks, otherwise it will not isolate any type of traffic;

Step 11, if the bandwidth requirement is specified in the initial stage of virtual network creation, the bandwidth virtualization route generation module first calls the MM_ATT algorithm to calculate a route, installs a flow table on the path, and then connects the edge switches connected to all hosts in the virtual network Set the rate-limited queue on the outbound port.

Example 4

The system formed by this method mainly includes: a virtual network generation module, a message interception module, a message analysis module, a virtual network mapping module, a traffic isolation module, and a bandwidth virtualization routing generation module.

The virtual network generating module is used to generate a logical virtual network slice from a user virtual network request, the generation of the virtual network originates from the user's request, the user determines the request parameters, and the controller generates the virtual network slice data structure, and maintains A map of all virtual network related parameters.

The message interception module is used to intercept all packet_in messages from the underlying physical network. When the network is initialized, any physical network resources cannot be used, and all unmatched packets will be forwarded to the controller through the packet_in message. Only if a virtual network has been established before, and the packet_in message belongs to the flow of a certain virtual network, the message is allowed to pass through the message parsing module, otherwise, the message is discarded.

Described message parsing module, for the packet intercepted by message intercepting module, message parsing module parses out relevant information, as source IP address, purpose IP address, source TCP/UDP port number, purpose TCP/UDP port number, source MAC address , the destination MAC address, and the port number of the incoming switch. At the same time, it is determined whether the message is a broadcast message or a DHCP message, and the intercepting module does not intercept such messages.

The virtual network mapping module is used to manage all virtual network mapping relationship data structures, including mapping from virtual network ID to virtual network, mapping from virtual network ID to virtual network name, mapping from virtual network ID to virtual network host set, IP Address-to-MAC address mapping and host-to-switch port mapping. These mapping data structures are the core data structures of the virtual network mapping module.

The traffic isolation module is used to isolate specific traffic of the application layer, such as HTTP, FTP, P2P traffic and the like. If the traffic to be isolated is specified when the virtual network is created, the traffic isolation module processes the request and installs flow tables on all switches on the path. These flow tables only match specific packets to achieve exact matching. For example, the following fields are exactly matched: Incoming switch Port, source MAC address, destination MAC address, source IP address, destination IP address, source transport layer port, destination transport layer port.

The bandwidth virtualization routing generation module is used to complete the generation of bandwidth virtualization routing. Bandwidth virtualization means bandwidth limitation and isolation for virtual networks. Generally, the minimum or maximum bandwidth required for virtual networks is set, and MM_ATT is used to The algorithm finds a route for the flow, and sets a number of rate-limiting queues on the outbound ports of the edge switches connected to all virtual network hosts to realize the rate limit of the flow and the generation of routes. The MM_ATT algorithm is detailed below:

MM-ATT is an algorithm that includes two requirements. (1) First, the bandwidth requirement is specified when creating a virtual network, then a path is found by using the Min-MaxBandwidthUtilization algorithm, and a flow table is delivered to the switch on the path. At the same time, the The traffic outbound ports of all edge switches are configured with rate-limited queues. These queues specify the maximum bandwidth of the exit, corresponding to the bandwidth requirements specified when creating a virtual network, so these flows can never inject traffic at a rate greater than the specified bandwidth; ( 2) Secondly, there is no specified bandwidth requirement when creating a virtual network, the flow running in the virtual network is relatively random, and the uncertainty of bandwidth fluctuation is relatively large. According to the conventional routing algorithm of the controller, a route is selected for the flow, and the flow table is issued. The controller monitors the bandwidth utilization rate of the link. If the link bandwidth utilization rate is greater than the specified trigger condition, it uses the Min-MaxBandwidthUtilization algorithm to select another relatively idle path for the non-bandwidth-demanding flow of the link, and transfers the flow to the path.

Therefore, when the bandwidth utilization rate of a certain link is greater than the trigger condition, the flow that does not specify the bandwidth requirement of the link will be transferred to other links, and the flow that originally existed on the link with the bandwidth requirement will not be transferred. The diverted flows are those for which bandwidth requirements are not specified.

Min-MaxBandwidthUtilization, to minimize the maximum bandwidth utilization: to minimize the bandwidth utilization of the selected path, and the path bandwidth utilization is the maximum bandwidth utilization of all links on the path. The goal of this algorithm is to minimize the bandwidth utilization of the path, avoid congested links, and use those relatively idle links. At the same time, this algorithm makes the remaining bandwidth on the link more, which can meet the demand of the incoming flow as much as possible.

Formal description: Given a network G(V, E), source node s∈V, destination node d∈V, bandwidth requirement b∈R. For ?(i, j)∈E, link capacity C _ij ∈R, remaining capacity L _ij ∈R, it is required to find the path p with source node s and destination node d, so that the available bandwidth of path p is available≥b, available is the minimum remaining capacity of all links on the path p, and requires the minimum bandwidth utilization rate U(p) of p, that is, U(p)=minU(pi). Among them, V represents the set of nodes, E represents the set of links, R represents the set of positive real numbers, pi∈P, and P represents the set of all paths from s to d.

Algorithm steps:

(1) Delete links in graph G that do not meet the bandwidth requirements, and get a new graph G ₂ =(V, E ₂ ).

( ₂ ) Calculate bandwidth utilization U _ij for each link in Figure G2.

(3) Depth-first search all paths P from the source node s to the destination node d, while limiting the number of hops to be no greater than max_hop.

(4) Find a path with the minimum bandwidth utilization rate from the paths found in step (3).

For the path finding of this algorithm, refer to Embodiment 2.

Claims (10)

1., based on a network virtualization method of SDN, it is characterized in that:

Step 1, during netinit, controller obtains SDN topology information by detection, comprises exchanger information and link information;

Step 2, exists without any virtual network during netinit, and all bottom-layer network resources wouldn't be used;

Step 3, creates a virtual network sheet, goes to step 4;

Step 4, create virtual network sheet and call virtual network generation module, virtual network generation module collects the information of the various required parameter of user, virtual network sheet is created according to required parameter, required parameter comprises the ID of virtual network, name, flow type of isolation and bandwidth demand, establishment completes in backward virtual network adds main frame, goes to step 5;

Step 5, adds main frame to virtual network sheet, adds the Host Based MAC Address of main frame or the IP address of virtual network sheet to, same virtual network can only based on a kind of addition manner, as only added host MAC address or only adding host IP address, after main frame has added, go to step 6;

Step 6, when certain main frame needs with another main-machine communication, if switch has the stream list item of coupling, then direct forwarding data bag, if the stream list item that switch does not mate, this packet can mail to controller, goes to step 7;

Step 7, controller message call blocking module tackles this packet, and message block module message call parsing module, goes to step 8, the result that the parsing module that waits for the arrival of news returns, and determines the need of abandoning this packet;

Step 8, message resolution module resolves this packet, whether data query bag comes from certain virtual network, if Query Result belongs to some virtual networks and meet virtual network relevant parameter, notification message blocking module allows this packet to pass through and issues stream table, otherwise notification message blocking module abandons this packet.

2. a kind of network virtualization method based on SDN according to claim 1, is characterized in that: whether data query bag comes from some virtual networks needs to call virtual network mapping block, goes to step 9;

Step 9, virtual network mapping block query mappings relation, determine whether packet belongs to some virtual networks, determine the relevant parameter of virtual network simultaneously, according to the handling process of relevant parameter determination packet, as called flow isolation module, bandwidth virtualization route generation module, if need to call flow isolation module, go to step 10, if need to call bandwidth virtualization route generation module to go to step 11;

Step 10, if specify carried flow in the starting stage that virtual network creates, flow isolation module isolates the flow that all non-virtual networks carry, otherwise can not isolate any type flow;

Step 11, if specify bandwidth demand in the starting stage that virtual network creates, first bandwidth virtualization route generation module calls MM_ATT algorithm and calculates a route, path is installed stream table, and the edge switch outbound port that the main frame then in all virtual networks is connected arranges speed limit queue.

3. a kind of network virtualization method based on SDN according to claim 1 and 2, it is characterized in that: described virtual network generation module, be used for user's virtual network requests formation logic virtual network sheet slice, the generation of virtual network stems from the request of user, required parameter is determined by user, by controller generating virtual network sheet data structure, and safeguard the mapping of all virtual network relevant parameters.

4. a kind of network virtualization method based on SDN according to claim 1 and 2, it is characterized in that: described message block module, be used for tackling all packet_in message from bottom physical network, during netinit, cannot use any physical network resource, all bags do not mated all will be transmitted to controller by packet_in message; Establish virtual network before only having, and this packet_in message belongs to the stream at some virtual network places, after message resolution module, allow message to pass through, otherwise abandon this message.

5. a kind of network virtualization method based on SDN according to claim 1 and 2, it is characterized in that: described message resolution module, for the packet that message block module is tackled, message resolution module parses relevant information, as source IP address, object IP address, source TCP/UDP port numbers, object TCP/UDP port numbers, source MAC, target MAC (Media Access Control) address with enter switch ports themselves number; Meanwhile, determine whether message is broadcast, dhcp message, will not tackle for this kind of message block module.

6. a kind of network virtualization method based on SDN according to claim 1 and 2, it is characterized in that: described virtual network mapping block, be used for managing all virtual network mapping relations data structures, comprise virtual network ID to the mapping of virtual network, virtual network ID to the mapping of virtual network name, virtual network ID to the mapping of the mapping of virtual network main frame collection, IP address to MAC address and main frame to the mapping of switch ports themselves.

7. a kind of network virtualization method based on SDN according to claim 1 and 2, is characterized in that: described flow isolation module, is used for the particular flow rate of isolation applications layer, as HTTP, FTP and P2P flow; If virtual network specifies the flow of required isolation when creating, flow isolation module process request, and all switches install stream table on path, and these stream tables are the specific bag of coupling only, realizes exact matching.

8. a kind of network virtualization method based on SDN according to claim 1 and 2, it is characterized in that: described bandwidth virtualization route generation module, be used for the generation of bandwidth virtualization route, bandwidth virtualization meaning is namely for limited bandwidth and the isolation of virtual network, minimum value or the maximum of occupied bandwidth needed for virtual network are generally set, MM_ATT algorithm is utilized to find route for stream, the edge switch outbound port connected at all virtual network main frames arranges some speed limit queues, realizes the speed limit of stream and the generation of route.

9. a kind of network virtualization method based on SDN according to claim 1 and 2, it is characterized in that: the formalized description of described MM_ATT algorithm is: a given network G (V, E), source node s ∈ V, destination node d ∈ V, bandwidth demand b ∈ R.

10. for (i, j) ∈ E, link capacity Cij ∈ R, residual capacity Lij ∈ R, require to find source node to be s, destination node is the path p of d, make the available bandwidth available >=b of path p, available is the least residue capacity of all links on the p of path, requires that bandwidth availability ratio U (p) of p is minimum simultaneously, i.e. U (p)=minU (pi); Wherein V representation node set, E represents link set, and R represents arithmetic number collection, and pi ∈ P, P represent all set of paths from s to d;

Algorithm steps:

(1) deletion figure G link is discontented with the link of sufficient bandwidth requirement, is newly schemed G2=(V, E2);

(2) to the every bar link calculation bandwidth availability ratio Uij in figure G2;

(3) search for all path P from source node s to destination node d, be not more than max_hop with limit jumping figure;

(4) path that a paths bandwidth availability ratio is minimum is found out in the path found from step (3).