网络安全检测|网络安全服务|网络安全扫描-香港墨客投资移动版

To reduce the overhead of looking up for NAT rules, we design QNS Algorithm to search for NAT rules at high speed. It uses hash search instead of sequential search to look up NAT rule tables with complexity of O(1), reducing the time of NAT rule lookup.

QNS algorithm plays a key role in Quick NAT system and the following steps show how Quick NAT system works:

1)Initialize NAT rule tables

In the initialization process of Quick NAT system, we should store the NAT rules into small rule tables. That is to say, Quick NAT system sets up small rule tables (i.e. 32 DNAT rule tables and 32 SNAT rule tables) instead of one big NAT rule table. NAT rules are stored into different small rule tables according to the subnet mask and NAT-type. Moreover, each small NAT rule table has one bit as flag to indicate whether it contains rules. The Figure 3 illustrates how to put NAT rules into different small rule tables.

In Figure 3, NAT rules are shown on the left and small NAT rule tables of Quick NAT system are on the right. We use one SNAT rule as an example to illustrate how to rearrange rules. The hash function calculates hash value on the basis of IP address/mask:port and protocol type of this rule. Consequently this rule is put into the SNAT rule table with 24-bit subnet mask and the bucket to store this rule depends on the hash value (654). Each bucket contains a singly-linked list to deal with hash collisions. Because this rule is the first rule of this rule table with 24-bit subnet mask, we change the flag bit of this rule table from 0 to 1. In this way, we place all of NAT rules into different rule tables.

2)Search for connection record

In Figure 4, one user wants to set up a flow to visit the website and the first packet of this flow arrives at the Quick NAT system running on the commodity server.

Once receiving a packet, Quick NAT system searches connection records that are stored in a separate hash table and keep the NAT mapping records of flows. Since this packet is the first packet of this flow, there is no connection record of this flow.

3)QNS Search for NAT rule

Since the connection record is not found, Quick NAT uses QNS algorithm to search for NAT rules in DNAT rule tables at first and then in SNAT rule tables. The method of searching DNAT rule tables is similar to that of searching SNAT rules tables, so we only illustrate how to look up SNAT rules.

For SNAT rule tables, QNS searches different rule tables one by one in the order of decreasing subnet mask because the rule with longer subnet mask bits is preciser than that with lower mask. As Figure 5 shows, QNS starts with the SNAT rule table with 32-bit subnet mask. For this SNAT rule table, QNS computes hash value on the basis of IP address/mask and the exact port of this packet. The hash value is 1288 and thus it does not find a SNAT rule with exact port and 32-bit subnet mask. And then QNS computes hash value based on IP address/mask and zero port to search SNAT rules with wildcard port. In this case, it still does not find the rule with wildcard port to match this packet. In all, QNS dose not find the rule to match the packet in this sub-table.

Figure 6 turns to the SNAT rule table with 31-bit subnet mask. Since this rule table's flag bit is zero, there is no rule in this table and QNS skips this sub-table. For the same reason, it skips the next few sub-tables.

Figure 7 shows that QNS turns to the rule table with 24-bit subnet mask at this time. Due to the subnet mask of this rule table, QNS uses 255.255.255.0 to mask IP address from 192.168.88.32 to 192.168.88.0 and then calculates the hash value. Ultimately, it finds a SNAT rule on the basis of masked IP and wildcard port. Once finding a NAT rule, QNS stops searching for NAT rules.

4)Modify the tuple and send out

In Figure 8, this rule means that it modifies the source IP from 192.168.88.0 to 166.111.130.166 and chooses a port from the port pool. After modifying the tuple of this packet, Quick NAT system sends out this packet to the website server.

Fig. 8. Change the tuple and send out.

5)Install two connection records