CN108337168A - It flows cluster and exchanges routing mechanism OpenFlow group table selection methods - Google Patents

Abstract

The present invention relates to route switching fields to support the route switching mechanism exchanged based on stream cluster to propose to realize under conditions of not changing original software defined network data plane forwarding mechanism.For this purpose, of the invention, stream cluster exchanges routing mechanism OpenFlow group table selection methods, and steps are as follows：1) perception bottom-layer network topology；2) reachable path is issued on each interchanger by controller；3) arrival time last time Hash table is initialized；4) last time time departure Hash table is initialized；5) timeout value is initialized；6) time for cryptographic Hash being calculated according to five-tuple, reaching interchanger；7) it executes following step 11 or executes following step 8；8) it executes following step 9 or executes following step 10；9) following step 11 is executed；10) following step 11 is executed；11) packet is sent to next-hop, executes step 6.Present invention is mainly applied to route switching occasions.

Description

Flow cluster switching routing mechanism OpenFlow group table selection method

technical field

The invention relates to the field of routing switching, in particular to an OpenFlow group table selection algorithm for realizing a flow cluster (flowlet) switching (switching) routing mechanism in a software-defined network.

Background technique

Explanation of terms:

Software-defined networking is a new type of network architecture that separates the data plane and control plane of traditional networks, so that the programmable control of the underlying forwarding hardware can be realized through the software platform of the centralized controller.

The OpenFlow protocol is a communication protocol between the data plane and the control plane in the software-defined network. The controller of the control plane instructs the switch of the data plane how to forward network data packets through the rules and actions defined by the OpenFlow protocol.

A flow table is a table structure defined in the OpenFlow protocol similar to a traditional network routing table, and it consists of several flow entries. A flow entry is composed of rules and action sets. If a network data packet conforms to the rules defined by the flow entry, the corresponding action will be executed on the data packet, such as forwarding from a certain port or modifying the source and destination IP addresses.

The group table is a special flow table defined by the OpenFlow protocol, which consists of several group entries. Each group entry includes: a group entry identifier, a group entry type, a group entry counter and an action bucket set. The type of group entry determines the semantics of the group entry. For example, a group entry of type all means that all actions in the action bucket of the group entry will be executed, while a group entry of type select means that the actions in the bucket of the group entry will be set. Only one of the actions will be executed. The action bucket set contains multiple action buckets, and each action bucket represents a kind of processing that can be performed on network data packets, such as forwarding from a certain port or modifying certain fields of data packets.

A flow cluster (Flowlet) refers to a set of related packets in the same TCP flow. The correlation here refers to: if the time interval between any two adjacent packets arriving at the same switching device is less than the predefined timeout value, then the packets that meet this condition are regarded as a collection, which is called a flow cluster.

Flowlet switching is a routing switching technology with flowlet as the granularity. Packets belonging to the same flowlet will be forwarded from the same port, and different flowlets can randomly select the forwarding port. Usually, the timeout value is defined as the maximum value of the delay difference between multiple paths in the multipath forwarding technology, so that the TCP reordering phenomenon will not be caused.

Flow cluster switching is an important routing switching technology, which is applied in the field of load balancing. Since the timeout value for distinguishing different flow clusters is set to be greater than the delay difference between any two load balancing parallel paths, the load balancing based on flow clusters will not cause out-of-order packets, which can improve TCP performance and network throughput . At the same time, it is relatively simple to use this routing switching mechanism to achieve load balancing, and does not require additional congestion control information, such as: the current congestion situation of a certain link. Load balancing based on flow cluster switching has adaptive load balancing capabilities, that is, it can distribute network traffic to each link approximately in proportion to the bandwidth of the link.

Realizing the routing switching mechanism based on flow cluster switching at the hardware level generally requires the support of a dedicated switching chip, such as: Cisco (Cisco) implements this switching mechanism in a self-developed hardware switch. The implementation at the software level is generally based on the open source software switch OpenvSwitch or the programmable software switch P4, but this implementation generally results in the lack of other switching functions of the switch, and becomes a software switch that only supports the flow cluster switching routing mechanism. At present, there is no implementation solution that can perfectly connect with software-defined networking.

The group table defined by the OpenFlow protocol in the software-defined network provides us with additional forwarding capabilities. For example, we can use the all-type group table to support multicast routing. The forwarding capability provided by the group table will not destroy other forwarding mechanisms supported by the OpenFlow protocol, such as the forwarding mode based on the matching of flow entry rules. The routing and forwarding mechanism expanded through the group table will not affect the original forwarding mechanism of the OpenFlow protocol, and is a supplement to the routing and forwarding mechanism in the OpenFlow protocol. The invention utilizes this advantage to realize the flow cluster exchange through the group table selection algorithm, and it is a perfect solution for realizing the flow cluster exchange routing mechanism in the software-defined network.

Contents of the invention

In order to overcome the deficiencies in the prior art, the present invention aims to propose an OpenFlow group table selection algorithm, which can support the routing switching mechanism based on flow cluster switching without changing the original software-defined network data plane forwarding mechanism . For this reason, the technical solution that the present invention adopts is, flow cluster switching routing mechanism OpenFlow group table selection method, the steps are as follows:

1) The controller of the software-defined network control plane perceives the underlying network topology and calculates multiple reachable paths between the source network device and the destination network device;

2) The controller uses each accessible port of the switch on the reachable path as the action bucket of the group entry, and sends it to each switch in the form of a group entry;

3) Initialize the last arrival time hash table: the hash table records the time when the last packet of each flow arrives at the switch;

4) Initialize the last departure time hash table: the hash table records the outgoing port of the current last packet of each flow;

5) Initialize the timeout value timeout: This timeout value is used to distinguish different flow clusters, and it should be greater than the maximum delay difference of multiple parallel paths in load balancing;

6) When the port of the switch receives the data packet, calculate the hash value hash_key of the packet according to the five-tuple including the incoming port, source IP address, destination IP address, source port, and destination port, and record the packet arrival switch time arrive_time.

7) If there is no record whose keyword is hash_key in the hash table of the last arrival time, the arrival of the record corresponding to the keyword hash_key is added to the hash table of the last arrival time; Randomly select a port indicated by an action bucket in the bucket set as the output port output_port, add the record output_port corresponding to the keyword hash_key to the last departure time hash table, and execute the following step 11, otherwise, execute the following step 8;

8) Obtain the last_time record last_time of the arrival time of the last packet of the flow corresponding to the packet to which the packet belongs from the last arrival time hash table, and update the record corresponding to the keyword hash_key in the last departure time hash table as the arrival time , if the arrival time arrive_time-last_time≥timeout of the last packet arriving at the switch is established, then perform the following step 9; otherwise, perform the following step 10;

9) Randomly select a port indicated by an action bucket bucket from the action bucket set of the group entry corresponding to the package as the output port output_port, add the record output_port corresponding to the keyword hash_key to the last_output_port hash table of the previous package output port, and Execute step 11 below;

10) From the last_output_port hash table, obtain the output port record of the previous packet of the flow corresponding to the packet to which the keyword hash_key belongs as output_port, and perform the following step 11;

11) The packet is sent to the next hop from the port whose port number is output_port of the switch, and step 6 is performed.

The specific steps in an example are:

1) In the underlying network topology, the TCP sending end is IP:10.0.0.1Port:3301, the TCP receiving end is IP:10.0.0.2Port:3302, and there are two reachable paths between the sending and receiving ends, which are: and

2) The software-defined network controller sends the group entry to each switch, and the group entry sent to switch S1 is as follows:

group_id=1, type=select, selection_method=flowlet_switching, bucket=output:2, bucket=output:3

3) Initialize the last_arrive_time hash table: the hash table records the time when the last packet of each flow arrives at the switch;

4) Initialize the last_outout_port hash table: the hash table records the outgoing port of the current last packet of each flow;

5) Initialize the timeout value timeout: This timeout value is used to distinguish different flow clusters, and it should be greater than the maximum delay difference of multiple parallel paths in load balancing;

6) The data packets sent from the sending end to the receiving end are processed on the switch S1 according to the group table selection algorithm

6.1.1) The switch S1 receives the first data packet of the sending end, calculates the hash value of the packet according to the quintuple hash_key, and the quintuple is: input port=1, source IP address=10.0.0.1, destination IP address =10.0.0.2, source port=3301, destination port=3302;

6.1.2) If there is no record with key 100 in the last_arrive_time hash table, add the record arrive_time=867674us corresponding to key 100 to the last_arrive_time hash table. Execute step 6.1.3 below;

6.1.3) Randomly select a port indicated by an action bucket from the group entry action bucket set matched by the packet as the output port output_port=2, add the record output_port=2 corresponding to the keyword 100 to the last_output_port hash table, and set the The packet is sent from port 2 of the switch;

6.2.1) The switch S1 receives the second data packet from the sending end, calculates the hash value of the packet according to the quintuple, and records the arrival_time of the packet to the switch;

6.2.2) Obtain keyword 100 from the last_arrive_time hash table corresponding to the time record last_time=867674us when the first packet arrives at the switch, update the record corresponding to keyword 100 in the last_arrive_time hash table as arrive_time=868125us; because arrive_time-last_time= 451<500 is established, so execute the following step 6.2.3;

6.2.3) Obtain the output port record output_port=2 of the first packet corresponding to the keyword 100 from the last_output_port hash table. Send the packet out of port 2 of the switch. ;

6.3.1) The switch S1 receives the third data packet from the sending end, calculates the hash value of the packet according to the quintuple, and records the arrival_time of the packet to the switch;

6.3.2) Obtain the key 100 from the last_arrive_time hash table corresponding to the time record when the second packet arrives at the switch. Update the record corresponding to keyword 100 in the last_arrive_time hash table to arrive_time; because arrive_time–last_time=512>500 is established, so execute the following step 6.3.3;

6.3.3) Randomly select a port indicated by an action bucket from the set of group table item action buckets matched by the package as the output port output_port=3, and add the record output_port=3 corresponding to the keyword 100 to the last_output_port hash table; The packet is sent from port 3 of the switch.

Features and beneficial effects of the present invention are:

Regardless of whether a dedicated hardware switching chip is used or an existing software switch solution is used to implement a routing mechanism based on flow cluster switching, the forwarding method of the switch becomes single, so it cannot be applied in software-defined networks and cannot support OpenFlow well. protocol.

In view of the above problems, the present invention provides support for the flow cluster switching routing mechanism by expanding the OpenFlow protocol group table selection algorithm without changing the normal forwarding mechanism of the OpenFlow protocol. It is an incremental implementation method that enables software-defined networks to use The routing switch based on flow cluster switching is made possible.

Description of drawings:

Fig. 1 is a schematic flow diagram of an OpenFlow group table selection algorithm that supports a flow cluster switching routing switching mechanism.

Figure 2 Software-defined network topology diagram.

Detailed ways

The purpose of the present invention is to provide an OpenFlow group table selection algorithm, which can implement a routing switching mechanism based on flow cluster switching in a software-defined network data plane.

The technical solution adopted by the present invention to solve its technical problems is:

1) The controller of the software-defined network control plane perceives the underlying network topology, and calculates multiple reachable paths between the source network device and the destination network device.

2) The controller uses each accessible port of the switch on the reachable path as an action bucket of a group entry, and sends it to each switch in the form of a group entry.

3) Initialize the last_arrive_time hash table: the hash table records the time when the last packet of each flow arrives at the switch.

4) Initialize the last_outout_port hash table: the hash table records the outgoing port of the current last packet of each flow.

5) Initialization timeout value timeout: This timeout value is used to distinguish different flowlets, and is generally greater than the maximum delay difference of load balancing multiple parallel paths.

6) When the port of the switch receives the data packet, calculate the hash value of the packet according to the quintuple (ingress port, source IP address, destination IP address, source port, destination port) as hash_key, and record the packet arrival switch time arrive_time.

7) If there is no record whose keyword is hash_key in the last_arrive_time hash table, add the record arrive_time corresponding to the keyword hash_key to the last_arrive_time hash table. Randomly select a port indicated by an action bucket from the action bucket set of the group entry corresponding to the packet as the output port output_port, add the record output_port corresponding to the keyword hash_key to the last_output_port hash table, and perform the following step 11. Otherwise, perform step 8 below.

8) From the last_arrive_time hash table, obtain the time record last_time when the last packet of the flow to which the packet belongs corresponds to the keyword hash_key arrives at the switch. Update the record corresponding to the keyword hash_key in the last_arrive_time hash table to arrive_time. If arrive_time-last_time≥timeout is established, execute step 9 below; otherwise, execute step 10 below.

9) Randomly select a port indicated by an action bucket from the action bucket set of the group entry corresponding to the package as the output port output_port, add the record output_port corresponding to the keyword hash_key to the last_output_port hash table, and perform the following step 11.

10) From the last_output_port hash table, obtain the output port record of the previous packet of the stream to which the packet belongs corresponding to the keyword hash_key as output_port. Perform step 11 below.

11) The packet is sent to the next hop from the port whose port number is output_port of the switch, and step 6 is performed.

The technical solutions of the present invention will be described in detail below in combination with specific embodiments. The schematic flow diagram of the OpenFlow group table selection algorithm of the present invention is as shown in Figure 1, and the specific operation steps are as follows:

1) Assuming that the underlying network topology is shown in Figure 2, there are two reachable paths between the TCP sender (IP:10.0.0.1Port:3301) and the TCP receiver (IP:10.0.0.2Port:3302), respectively for: and

2) The software-defined network controller sends the group entry to each switch, and the group entry sent to switch S1 is as follows:

group_id=1, type=select, selection_method=flowlet_switching, bucket=output:2, bucket=output:3

3) Initialize the last_arrive_time hash table: the hash table records the time when the last packet of each flow arrives at the switch

4) Initialize the last_outout_port hash table: the hash table records the outgoing port of the current last packet of each flow.

5) Initialization timeout value timeout: This timeout value is used to distinguish different flow clusters, and is generally greater than the maximum delay difference of load balancing multiple parallel paths. In this example, it is assumed that the timeout value is 500us.

6) The data packets sent from the sending end to the receiving end (the first three data packets are taken as an example) are processed on the switch S1 according to the group table selection algorithm (the processing flow on other switches is similar).

6.1.1) The switch S1 receives the first packet of the sending end, according to the quintuple (incoming port=1, source IP address=10.0.0.1, destination IP address=10.0.0.2, source port=3301, destination port= 3302) Calculate the hash value of the package as hash_key, assuming hash_key=100. Record the arrival_time of the packet to the switch as 867674us.

6.1.2) If there is no record with key 100 in the last_arrive_time hash table, add the record arrive_time=867674us corresponding to key 100 to the last_arrive_time hash table. Perform step 6.1.3 below.

6.1.3) Randomly select a port indicated by an action bucket (bucket=output:2) from the group entry action bucket set (bucket=output:2, bucket=output:3) matched by the packet as the output port output_port=2 , Add the record output_port=2 corresponding to the keyword 100 to the last_output_port hash table. Send the packet out of port 2 of the switch.

6.2.1) The switch S1 receives the second packet of the sending end, according to the quintuple (incoming port=1, source IP address=10.0.0.1, destination IP address=10.0.0.2, source port=3301, destination port= 3302) Calculate the hash value of the bag to be 100. Record the arrival_time of the packet to the switch as 868125us.

6.2.2) Obtain keyword 100 from the last_arrive_time hash table and record last_time=867674us corresponding to the time when the first packet arrives at the switch. Update the record corresponding to keyword 100 in the last_arrive_time hash table to arrive_time=868125us. Since arrive_time-last_time=451<500 is established, the following step 6.2.3 is performed.

6.2.3) Obtain the output port record output_port=2 of the first packet corresponding to the keyword 100 from the last_output_port hash table. Send the packet out of port 2 of the switch.

6.3.1) The switch S1 receives the third packet of the sending end, according to the quintuple (incoming port=1, source IP address=10.0.0.1, destination IP address=10.0.0.2, source port=3301, destination port= 3302) Calculate the hash value of the bag to be 100. Record the arrival_time of the packet to the switch as 868637us.

6.3.2) Obtain the key 100 from the last_arrive_time hash table and record last_time=868125us corresponding to the time when the second packet arrives at the switch. Update the record corresponding to keyword 100 in the last_arrive_time hash table to arrive_time=868637us. Since arrive_time-last_time=512>500 holds true, execute the following step 6.3.3.

6.3.3) Randomly select a port indicated by an action bucket (bucket=output:3) from the group entry action bucket set (bucket=output:2, bucket=output:3) matched by the packet as the output port output_port=3 , Add the record output_port=3 corresponding to the keyword 100 to the last_output_port hash table. Send the packet out of port 3 of the switch.

Claims (2)

1. a kind of stream cluster exchanges routing mechanism OpenFlow group table selection methods, characterized in that steps are as follows：

1) the controller perception bottom-layer network topology of software defined network control plane, calculates source network device and is set to purpose network A plurality of reachable path between standby；

2) controller using each of interchanger on reachable path up to exit port as the action bucket for organizing list item, and with a group list item Form be issued on each interchanger；

3) arrival time last time Hash table is initialized：The last one current packet of each stream of Hash table record reach interchanger when Between；

4) last time time departure Hash table is initialized：The exit port of the last one current packet of each stream of Hash table record；

5) initialization timeout value timeout：The timeout value is greater than that load balancing is a plurality of and walking along the street for distinguishing different stream clusters The maximum delay of diameter is poor；

6) when the port of interchanger receives data packet, according to including inbound port, source IP address, purpose IP address, source port, The five-tuple of destination interface calculates the cryptographic Hash hash_key of the packet, and records the time arrive_ that the packet reaches interchanger time；

7) if there is no the records that keyword is hash_key in arrival time last time Hash table, by keyword hash_key Corresponding record arrival is added in arrival time last time Hash table；Random choosing is concentrated from the action bucket of corresponding group of list item of the packet The port of action bucket instruction is selected as exit port output_port, by the corresponding record output_ of keyword hash_key Port is added in last time time departure Hash table, and executes following step 11, otherwise, executes following step 8；

8) the upper packet flowed belonging to the corresponding packets of keyword hash_key is obtained from arrival time last time Hash table to reach Time of interchanger records last_time, updates in last time time departure Hash table that keyword hash_key is corresponding to be recorded as Arrival time, if arrival time arrive_time-it is upper one packet reach interchanger time last_time >=timeout at It is vertical, then execute following step 9；Otherwise, following step 10 is executed；

9) concentrate the port that one action bucket of random selection indicates as exit port from the action bucket of corresponding group of list item of the packet The corresponding record output_port of keyword hash_key are added to upper packet exit port last_ by output_port In output_port Hash tables, and execute following step 11；

10) the upper packet flowed belonging to the corresponding packets of keyword hash_key is obtained from last_output_port Hash tables Exit port record is used as output_port, executes following step 11；

11) packet is sent to next-hop from the port that the port numbers of interchanger are output_port, executes step 6.

2. stream cluster exchanges routing mechanism OpenFlow group table selection methods as described in claim 1, characterized in that an example In comprise the concrete steps that：

1) in bottom-layer network topology, TCP transmitting terminals are IP:10.0.0.1Port:3301, TCP receiving terminals are IP: 10.0.0.2Port:3302, the reachable path between sending and receiving end has two, respectively：With

2) a group list item is issued on each interchanger by software defined network controller, is issued to the following institute of interchanger S1 group list items Show：

Group_id=1, type=select, selection_method=flowlet_switching, bucket= output:2, bucket=output:3

3) last_arrive_time Hash tables are initialized：The last one current packet of each stream of Hash table record reaches interchanger Time；

4) last_outout_port Hash tables are initialized：The exit port of the last one current packet of each stream of Hash table record；

5) initialization timeout value timeout：The timeout value is greater than that load balancing is a plurality of and walking along the street for distinguishing different stream clusters The maximum delay of diameter is poor；

6) transmitting terminal is sent to the data packet of receiving terminal and carries out following processing according to group table selection algorithm on interchanger S1

6.1.1) interchanger S1 receives first data packet of transmitting terminal, and the hash values that the packet is calculated according to five-tuple are Hash_key, five-tuple are：Inbound port=1, source IP address=10.0.0.1, purpose IP address=10.0.0.2, source port= 3301, destination interface=3302；

6.1.2) there is no the record that keyword is 100 in last_arrive_time Hash tables, then keyword 100 is corresponding Record arrive_time=867674us is added in last_arrive_time Hash tables, executes following step 6.1.3；

6.1.3) concentrate the port that one action bucket of random selection indicates as exit port from matched group of list item action bucket of the packet 100 corresponding record output_port=2 of keyword is added to last_output_port Hash by output_port=2 In table, which is sent out from No. 2 ports of interchanger；

6.2.1) interchanger S1 receives second data packet of transmitting terminal, and the hash values of the packet are calculated according to five-tuple, record The packet reaches the time arrive_time of interchanger；

6.2.2 keyword 100) is obtained from last_arrive_time Hash tables corresponds to the time that first packet reaches interchanger Last_time=867674us is recorded, updates in last_arrive_time Hash tables that keyword 100 is corresponding is recorded as Arrive_time=868125us；Because of arrive_time-last_time=451<500 set up, so executing following step Rapid 6.2.3；

6.2.3 the exit port record of 100 corresponding first packets of keyword) is obtained from last_output_port Hash tables Output_port=2 sends out the packet from No. 2 ports of interchanger；

6.3.1) interchanger S1 receives the third data packet of transmitting terminal, and the hash values that the packet is calculated according to five-tuple are to remember Record the time arrive_time that the packet reaches interchanger；

6.3.2 keyword 100) is obtained from last_arrive_time Hash tables corresponds to the time that second packet reaches interchanger It records, keyword 100 is corresponding in update last_arrive_time Hash tables is recorded as arrive_time；Because of arrive_ Time-last_time=512>500 set up, so executing following step 6.3.3；

6.3.3) concentrate the port that one action bucket of random selection indicates as exit port from matched group of list item action bucket of the packet 100 corresponding record output_port=3 of keyword is added to last_output_port Hash by output_port=3 In table；The packet is sent out from No. 3 ports of interchanger.