2.1. MAC Missing and Flooding

The channel of the Internet’s data-link layer has two working modes: point-to-point and broadcast. Broadcast, sometimes also known as multicast, is generally completed by a switch, which forwards a frame from all ports (excluding the frame’s entry port). This forwarding mode often causes chain reactions from other switches, resulting in flooding. Flooding can bring a large amount of load to the network, limit network expansion, and worsen network performance.

Technically, there are two main reasons for flooding: MAC missing and protocol requirements. MAC missing refers to the switch being unable to find the corresponding MAC address of the frame in its forwarding table, unable to perform point-to-point forwarding, and can only broadcast, resulting in flooding, which is called passive flooding. Another reason for flooding is that a certain protocol generates a broadcast message, requiring the switch to broadcast the message, resulting in network flooding, which we call protocol flooding.

Protocol flooding is the prerequisite of protocol operation, and the switch must complete this action, not only cannot eliminate it but also fully guarantee it. For passive flooding, it is essentially caused by a lack of knowledge, i.e., a lack of relevant entries in the switch’s forwarding table. If these entries can be supplemented, the impact of flooding can be reduced or even eliminated. This paper mainly discussed the use of multitable search and path generation in the SDN environment to compensate for missing entries in switches and reduce the harm of passive flooding to the network.

2.1.1. Frame Forwarding in Ethernet

Flooding is a data stream transfer technology used by the switch to send data to all interfaces. One switch’s flooding will often cause the simultaneous flooding of other switches, resulting in a large number of broadcast messages in LAN and subsequently increasing the network burden. MAC missing occurs when a MAC address, which is requested, does not exist in the MAC table of the switch. The disadvantage of the Ethernet switch is the production of considerable flooding when MAC missing occurs.

In the following derivation, assuming the network topology is a tree and the transmission delay between switches is negligible. Therefore, a wired network with arbitrary topology and layer-2 interoperability can be transformed to a tree G by spanning tree protocol (STP), where G = 〈V,  E,  M,  F〉.

V represents the node set, which is also known as the switch set, V = {v₁, v₂, ⋯, v_n};

E denotes the edge set, which is also known as the links between switches, E = {e₁, e₂, ⋯, e_n−1};

M refers to the MAC address set, M = {m_v1, m_v2, …, m_vn}, where m_vi is the MAC address set owned by switch v_i, 1 ≤ i ≤ n;

F indicates the frame count set, F = {f_v1, f_v2, …, f_vn}, where f_vi denotes the number of frames generated when flooding occurs in switch v_i, 1 ≤ i ≤ n.

If a switch v receives a frame, then the destination address of the frame is MAC_X. If MAC_X ∉ m_v, then v will broadcast the frame to all ports except the entry port in accordance with the forwarding principle of the Ethernet switch, that is, flooding occurs. We record the flooding in switch v triggered by MAC_X as missing(v, MAC_X) and using frame(v, MAC_X) to represent the number of frames generated by missing(v, MAC_X).

For the convenience of subsequent discussion, the meanings of related concepts are shown in Figure 1.

•  

  Set V is {v₁,  v₂, …,  v₇}

•  

  Set E is {e₁,  e₂, …,  e₆}

•  

  Set M is {m_v1,  m, …,  m_v7}

Support v₁, v₂, and v₃ does not have MAC_X, but v₄, v₅, v₆, and v₇ do, and then, missing(v₁, MAC_X) covers set {v₁, v₂, v₃}.

Definition 1. MAC missing cover. If missing(v, MAC_X) occurs and results in all nodes in set V^′(V^′⊆V and v ∈ V^′) flooding, then it means missing(v, MAC_X) covers V^′, and the total number of frames caused by missing(v, MAC_X) is flood(V^′).

Theorem 2. In tree G, if nodes u and v satisfy the following conditions:

• (1)

  MAC_X ∈ m_v

• (2)

  and MAC_X ∈ m_u

Then, the MAC set of each node in path p, which connects nodes u and v, should contain MAC_X. Hence, $$ where v^′ ∈ p.

Proof. On the basis of MAC learning, if f is forwarded from switch v to target switch u for frame f with the source address MAC_X and the forwarding path p, then f will pass through all switches on path p, and all nodes on path p will learn the MAC_X. Hence, $$ where v^′ ∈ p.

Theorem 3. In tree G, if missing(v, MAC_X) covers V^′ and |V^′| > 1, then all nodes in V^′ can form a subtree of G.

Proof. Suppose that nodes u ∈ V^′ and z ∈ V^′ and no path is available between u and z. As flooding is generated by missing(v, MAC_X), u and z must have their own paths to node v. Suppose their separate paths are p1 and p2, then a path p to connect u and z can be constructed, where p = p1 + p2, that is, a path exists between u and z.

Hence, the hypothesis is invalid. A path exists between all nodes in V^′, that is, V^′ can form a subtree of G.

Theorem 4. In tree G, if missing(v, MAC_X) and missing(u, MAC_Y) cover the same subtree g, then the number of flood frames generated by the two is equal.

Proof. For node v^′, where v^′ ∈ g, when flooding occurs, the number of frames it generates is $$, which has nothing to do with the MAC address that triggered the flooding.

Hence, when flooding occurs at all nodes in g, the total number of frames is fixed as follows:

$$ (1)

Theorem 5. In network G, if MAC_X satisfies $$, then missing(v, MAC_X) covers G.

Proof. All nodes in G are connected because G is a tree. For any node v or u, a path will exist between them. Suppose that the path between u and v is p, where |p| = l and p = v_ie_iv_i+1 ⋯ e_i+l−1u, then v_i+1 on path p will receive the flood frame because the flooding frame propagates along all the edges of v when missing(v, MAC_X) occurs. As MAC_X ∉ m_vi+1, then missing(v_i+1, MAC_X) will occur and cause the flooding frame to continue propagating to the next node on the path p with the process repeating itself. The flooding frame eventually propagates along the path p to u because MAC_X ∉ m_u. Hence, missing(u, MAC_X) occurs. As u is arbitrary, then flooding occurs at all nodes, indicating that missing(v, MAC_X) will cover G.

Theorem 6. In network G, if missing (v, MAC_X) occurs, flooding stops at node u, and u is a leaf, then u is removed from G to form subtree G^′. If missing(v^′, MAC_X) occurs and v^′ ∈ G^′, then missing(v^′, MAC_X) will cover G^′.

Proof. Suppose that missing(v^′, MAC_X) does not cover G^′, then a node u^′ exists in G^′ that satisfies the following conditions:

• (1)

  A path p exists between u^′ and v, and u^′ is the last node on p

• (2)

  $$

As the flooding terminates at switch u, then MAC_X ∈ m_u. Therefore, MAC_X appears on switches u and u^′. Hence, a path p exists in G that connects u and u^′, and v ∈ p. On the basis of Theorem 2, MAC_X exists in the address set of all nodes on p. Hence, MAC_X ∈ f_v exists. That is, missing(v, MAC_X) will not occur, thereby contradicting the premise. Hence, missing(v^′, MAC_X) will cover G^′.

Corollary 7. In tree G, assume missing(v, MAC_X) occurs and flooding terminates at u.

If u is a branch node, taking u as the cut point, after u is deleted, G is divided into set G^′ = (g₁, g₂⋯). Let node v belongs to g_i, and g_i ∈ G^′. If missing(v^′, MAC_X) occurs and v^′ ∈ g_i, then missing(v^′, MAC_X) will cover g_i.

Proof. If |g_i| = 1, it means g_i contains only one node. Hence, v^′ is v. so if missing(v, MAC_X) occurs, it would cover g_i.

If |g_i| > 1, then g_i includes multiple nodes. On the basis of Theorem 3, g_i is a subtree of G. Suppose that missing(v^′, MAC_X) does not cover g_i, then u^′ must exist, satisfying u^′ ∈ g_i and $$. On the basis of Theorem 2, a path p exists between u and u^′ because $$ and MAC_X ∈ m_u and u^′ ∈ g_i and u ∈ G. As missing(v, MAC_X) covers g_i and terminates at node u, then v ∈ p must exist. On the basis of Theorem 2, MAC_X ∈ m_v must exist, that is, missing(v, MAC_X) does not occur in v, which is contradictory to the premise. Hence, missing(v^′, MAC_X) covers g_i.

Corollary 8. The flood frames generated by missing(v^′, MAC_X) in g_i are equal to the flood frames generated by missing(v, MAC_X) in G.

Proof. Corollary 7 shows that missing(v^′, MAC_X) and missing(v, MAC_X) cover the same subtree g_i. Hence, on the basis of Theorem 4, they produce the same amount of frames.

2.1.2. Frame Forward in SDN

SDN is mainly composed of SDN controllers, OpenFlow channels, and OpenFlow switches. OpenFlow switches generally have two working models, namely, proactive and reactive. In the proactive model, the switch can automatically process the MAC frame forwarding through preset flows without the controller’s intervention and simulates the behaviors of the Ethernet switch. In the reactive model, the switch cannot automatically process the transfer of MAC frames because it must interact with the controller [7]. For example, sending PacketIn messages to the controller will command the switch via the dispatching flows. For the SDN, many switches exist in its topology. Each switch may work in a proactive or reactive mode. Therefore, when switches with different modes exist in the SDN, frame forwarding becomes further complex.

The working mode of proactive switch is the same as that of the Ethernet switch and also completes the MAC frame forwarding via MAC learning and flooding.

When switch working in reactive mode, it has to cooperate with the controller. Generally, the controller has to maintain a table to store the dpip < MAC: inport > mappings. When a frame is received, the switch forwards it as follows:

•  

  Step 1: After the frame enters the switch, if frame matches the flow entries, the corresponding instructions are executed.

•  

  Step 2: If table missing occurs, then the switch sends PacketIn to the controller.

•  

  Step 3: After receiving the package message, the controller updates its dpid < MAC: in_port > mapping table on the basis of the src_MAC, in_port, and dpid fields in the PackageIn message.

•  

  Step 4: The controller searches on the basis of the dst_MAC field in the frame. Assuming that the dpid of the switch is X, then the controller looks up entries in the <MAC: inport > mapping table corresponding to X.

•  

  Step 5: If the controller finds a matching entry, then it first dispatches the forwarding flow table to the corresponding switch X and then sends the PacketOut message to the switch X. Figure 2(a) shows these processes.

If the controller does not find any entry matches with the dst_MAC, then it sends a PacketOut message requiring the switch X to flood, which may cause a chain reaction on other switches, as shown in Figure 2(b).

Definition 9. MAC missing. For node v in G, if v received a frame whose target MAC address is MAC_X and no flow entry matches the frame, then v eventually forwards the frame by flooding. Hence, MAC missing occurs at v, which is denoted by missing (v, MAC_X).

As the mode of frame forwarding in the proactive switch simulates the Ethernet switch, the frames generated by both switches are the same when MAC missing occurs. Hence, Theorem 10 exists.

Theorem 10. For the proactive switch, the number of frames generated by missing (v, MAC_X) is equal to that of the Ethernet switch.

Theorem 11. For the reactive switch, the number of frames generated by missing (v, MAC_X) is larger than that of the proactive switch.

Proof. In reactive switch X, if missing (v, MAC_X) occurs, then v will send a PacketIn message to the controller, and the controller could not find any entry corresponding to MAC_X in <MAC: inport > table related to X, then the controller will send a PacketOut message to v and command v to forward the frame by flooding. When MAC missing occurs in the reactive switches, besides the flooding frames, one PacketIn and one PacketOut message will also be generated in the network at least.

Hence, for reactive switch v, missing (v, MAC_X) produces more frames than those running under the proactive mode.

Theorem 12. Regardless of the edges between the controller and switch for Ethernet G and SDN G^′ with the same topology, if missing (v, MAC_X) covers the same subtree g, then the frames generated in G^′ is no less than those in G.

Proof. If missing (v, MAC_X) covers g, on the basis of Theorem 4, the number of frames generated by missing (v, MAC_X) in G is as follows:

$$ (2)

In G^′, if {v^′|v^′ ∈ g and v^′ ∈ V_p} exists, that is, G is composed entirely of proactive switches, then, on the basis of Theorem 10, the number of frames generated by missing (v, MAC_X) is the same as those occurring in G and is presented as follows:

$$ (3)

If ∃v^′ satisfies v^′ ∈ g and v^′ ∈ V_r, because the number of frames generated by v^′ when MAC missing is larger than that generated by the node in the same topology position in G (at least more than two frames), then the number of frames generated by missing (v, MAC_X) at this time is at least flood(g) + 2. Therefore, in SDN, the number of frames increases instead of decreasing.

2.2. Related Work

Traditional methods, such as subnet and virtual local area network (VLAN) division, can alleviate the harm of broadcasting, but these methods are limited in the data centers because the migration of virtual machines requires business continuity and layer-2 consistency [8, 9]. In addition, research on broadcast suppression could be divided into three categories: using new network architectures, combining SDN for proxies, and re-encode MAC address.

3.1. Workflow of MSPG

3.2. Main Algorithms

For Ethernet switch running in non-SDN environment, when missing (S_START, MAC_X) occurs, flooding is inevitable. On the basis of Theorem 5, missing (S_START, MAC_X) will cover at least subgraph G^′ and will cover at worst the entire network G. If a switch S_END exists in G, and ∃entry^′ ∈ S_END.SDST, and entry^′.MAC = MAC_X, then flooding will terminate at S_END. On the basis of Theorem 6 and Corollary 7, missing (S_START, MAC_X) will cover subgraph G^′, which includes S_START. We can construct a path between S_START and S_END and use unicast instead of flooding because G is a tree. Therefore, in step 3, MSPG uses a multitable searching algorithm. When the search fails in S_START.SDST, the algorithm will search MAC_X in MDST, and if multiple entries match, then the nearest entry to MAC_X is selected. In this way, unicast forwarding can be used to replace flooding to reduce the network load. The workflow of this process is described in Figure 3, and Algorithms 1–4 shows the details of it.

In step 4, if S_END satisfies the conditions because network G is interconnected, then a path p must exist between S_START and S_END. The purpose of Algorithm 1 is to construct the path p. In Algorithm 1, if MAC_X is a broadcast address, there is no need to calculate. Otherwise, it searches the SDST of the S_START and, if the corresponding entry for MAC_X is found, then returns the corresponding port. Otherwise, we traverse the MDST, if a switch contains an entry corresponding to MAC_X and adds the device to the Flist. Finally, it traverses Flist to find the switch closest to S_START.

Algorithm 2 describes the process of constructing a path p from S_START to S_END in G. In Algorithm 2, if S_START and S_END are the same, then S_START is the only node on path. Otherwise, it constructs path1 from S_START to root and then constructs path 2 from S_END to root. Finally, it identifies the intersection of path 1 and path 2 and constructs a complete path from S_START to S_END;

When the switch enters or leaves or when the switch state or the flow table changes, the maintenance module of MSPG maintains and updates the related important data, such as SDST, MDST, Nodes, and Links. In Algorithm, if a switch entry event occurs, it updates Nodes and Links. If a switch leave event occurs, it first deletes the corresponding device from Nodes, then removes all edges related to the switch in Links, and then deletes the device in MDST. If a statistical event occurs, it updates the entry corresponding to that event in MDST.

When path p is generated between S_START and S_END, the Flow_Dispatch module is responsible for generating the flow set (F − set) and dispatches each flow in the F − set to the corresponding switches, thereby avoiding the flooding of switches in path p. Algorithm 4 shows the F − set generation and dispatch algorithm. It first identifies all edges between adjacent switches on path p, then constructs a forwarding flow table, and adds it to F − set.

The relationship between the above four algorithms is shown in Figure 3. With the help of these algorithms, MSPG can effectively deal with MAC missing, complete the transition from broadcast to unicast, and reduce the broadcast overhead in LAN.

4.1. Experiments

The experimental results are shown in Figures 4, 5, 6, 7, and 8. Figure 4 shows that the forwarding delay increases with the increase in the tree depth. However, the increments of the three methods vary. The delay increases in FSDM and Portland are significant, while that in MSPG is relatively mild. The reason is that when MAC missing occurs in SDN, the switch will send frames that cannot be processed to the controller through packet-in message. In FSDM and Portland, the controller will use a packet-out message to request the switch to broadcast. The process of sending packet-in and receiving packet-out increases the number of repetitions with the increase in the length of the forwarding path. Consequently, the delay increases.

Meanwhile, in MSPG, the process of sending packet-in and receiving packet-out does not repeat with the increase in the path length. The controller will use a path generation module to prevent the spread of MAC missing. The packet-in and packet-out processes will only occur on the first switch.

The comparison of the three methods in terms of CPU overhead is shown in Figure 5. The CPU overhead of processing MAC missing is slightly high in MSPG. When MAC missing occurs, the switch will send packet-in to the controller. The controller will traverse SDST and MDST to find devices with missing MAC and generate a path and a set of flow tables through calculation. Thereafter, these flow tables are deployed to the corresponding switches to reduce the interference of MAC missing on the network, resulting in a higher CPU overhead.

In FSDM, although the switch will send a packet-in message to the controller when MAC missing occurs, the controller only looks up its own host-information table and guides the switch to broadcast. Accordingly, the overhead is lower than MSPG. The method of handling MAC missing in Portland is similar to that in FSDM, with a lower CPU overhead than that of the MSPG. However, the FSDM’s hash calculation results in a slightly higher CPU overhead than in Portland.

In Figure 6, MSPG has a slightly higher memory overhead. MSPG has to maintain MDST and multiple SDST to accelerate the completion of MAC address traversal and path generation. Moreover, the size of the tables increases with the increase in the network topology depth, resulting in a higher memory usage for handling MAC missing. Portland must maintain a PMAC table with entry length lowers than the host-info table in FSDM; hence, its memory overhead is slightly lower than that in FSDM. The data structures that FSDM must maintain include the host-info-table and the location-info table. The consistency of these two tables must be maintained at all times. FSDM also needs to store the hash of the IP address, and its memory overhead is lower than that of MSPG and higher than that of Portland.

In Figure 7, repeated experiments are conducted at different topology depths, and the number of frames generated by MAC missing between MSPG, Portland, and FSDM is tested and compared. It shows that the number of frames generated by Portland and FSDM increase remarkably with the network scale. Due to the lack of a mechanism to handle MAC missing, the numbers of broadcast frames generated by Portland and FSDM are close to the number of switch ports. In contrast, only a slight traffic increase occurs in MSPG. When MAC missing occurs and covers subgraph G^′, flooding will occur in all nodes of G^′. However, MSPG will construct a path by searching MDST, generate a flow set, and dispatch it. In most cases, only a small number of PacketIn, PacketOut, and FlowMod messages are generated. Thus, MSPG effectively suppresses the generation of broadcast frames and greatly reduces the broadcasting traffic.

The energy consumption of the three methods when MAC missing occurs is shown in Figure 8, with MSPG forwarding energy consumption as a benchmark. The switch’s energy consumption mainly lies in frame forwarding and cyclic redundancy check (CRC). The energy consumption of forwarding is 70 times that of CRC, according to the actual measurements. One switch’s MAC missing will trigger flooding, causing a chain reaction of other switches, resulting in a surge in data plane energy consumption, which is positively correlated with an increase in traffic. When MAC missing occurs in MSPG, the controller will suppress flooding through path calculation and dispatch flow tables; thus, its energy consumption is much lower than those in FSDM and Portland. From Figures 7 and 8, it can be seen that MSPG is suitable for large-scale networks in terms of energy consumption and network traffic control.

4.2. Comparison and Analysis

We compare MSPG with several typical approaches in the aspects of add/modify protocols, additional facility, compatible with switch, topology traversal ability, path generation ability, and redeploy network. The compared results are presented in Table 1.

In terms of protocol modification: SEATTLE uses one-hop DHT for frame forwarding, and it needs to add a variety of new protocols in layer-2 and layer-3 and not compatible with Ethernet switch or OpenFlow enabled switch. In SAL, switch needs to encapsulate application and location address information in the frame for other switches to learn, so it is necessary to redesign its layer-2 protocol.

In terms of network facility: Servers under software-defined network architectures to eliminate discovery messages (SSED) redefine the relationship between servers and SDN architecture. In order to reduce the broadcasting caused by service discovery protocols, SSED deploys a variety of dedicated servers in the network, such as ARP servers, and DHCP servers. In addition, it also needs to consider the deployment location of the servers. Portland also needs to add a server to deploy fabric manager to manage global address information. EtherAgent needs to add agents to support the response of ARP messages and the relay of DHCP messages. Floodless service discovery model (FSDM) adds both ARP module and DHCP module to the controller, and it completes address registration by monitoring the DHCP message and host’s ARP behavior, so that controller can complete ARP message forgery response and DHCP message relay. However, FSDM lacks global topology traversal and path generation capabilities.

In terms of compatibility and network deployment, EtherAgent needs to redesign the network and divide it into several regions which are represented by different agents. In order to transfer of application and location information, SAL needs to design new protocols in layer-2, and the address resolution table of switch also needs to be modified to store the virtual machine information of tenant. These are all different from SDN switches, so the network needs to be upgraded. Because SEATTLE uses one-hop DHT for forwarding and routing, the existing switches cannot support it, and it also needs to divide the network into multiple edge-areas and one backbone-area, which need to redesign the network.

In terms of topology traversal and path generation, SSED has the ability of topology awareness. When forwarding ARP messages, different actions can be taken according to the type of the message and the sender. If the reply message is sent by the ARP server, the forwarding path between the starting point and the ending point can be calculated according to topology, and then unicast forwarding can be carried out.

Compared with the above methods, MSPG does not need to modify the network protocols, add network devices or servers, and redeploy the network, compatible with OpenFlow enabled switches. MSPG also has the ability of topology traversal and path generation; it is an efficient and easy-to-deploy forwarding method in layer-2.