## 3 Multi-Scope State Area (MSSA)
### State Lookup  
Although the switch has \(1+t+\sum_{i=0}^{t}f_{i}+\sum_{i=0}^{p}P_{i}\) state areas at time \(T\), the packet processing state can only be in four state areas at most. Because the number of states that can be stored in each state area is limited, constant-time state lookup is possible. By the shared scope of the state, there can be only four state areas needed in packet processing. When a packet matches an entry, it can only access the following state areas: the packet's packet state area, the matching entry's flow state area, the entering table's table state area, and the global state area (as shown in Figure 6). The state required by the packet will then be limited to these four states. Obviously, the limited state areas can only be determined after the packet matches the entry. As stated in Section 2, the switch processes packets by using a match-action table. Moreover, matching the packet to an entry is a switch-inherent process.  
Assume that each state area has a maximum storage capacity of \(M\) states. If there are no restrictions on the state sharing scope, even if the state is divided into multiple state areas, in order to obtain a state, we must first locate the state area, and then obtain the state. The time complexity of locating the state area in this case is shown in Equation (2).  
\[\text{O}(1+t+\sum_{i=0}^{t}f_{i}+\sum_{i=0}^{p}P_{i}) \tag{2}\]  
However, due to the state sharing scope limitation, the state required by the packet can only be in four state areas, so the time complexity of looking up the state area is O(1), which is a constant. There are at least \(M\) states in the state area, and even if linear search is used, one of the states can be obtained in constant time. As a result, using MSSA, a state can be found in real time.  
When processing a packet, Algorithm 1 describes the process of looking up the state. The state is identified by type and name, where type denotes the type of state (packet state, flow state, table state, and global state), and name uniquely identifies the state within the state area. When the packet enters the switch, the global state area, _gsa_, and the packet state area, _psa_, can be determined. When the packet matches an entry, the table's state area, _tsa_,  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Type** & **Sharing Scope** & **Life Cycle** & **Amount** \\ \hline Global state & all packets in the switch & = Switch & 1 \\ \hline Table state & packets entering the table & = Table & Number of tables \\ \hline Flow state & packets matching the entry & = Entry & Number of entries \\ \hline Packet state & a single packet & = Packet & Number of packets \\ \hline \hline \end{tabular}
\end{table}
Table 2: Four types of states’ sharing scope, life cycle, and quantity in the switch.  
Figure 6: Four state areas that can be accessed when the packet, \(P\), matches the entry \(R1\) in the table \(T0\).  
and the matching entry's flow state area, _fsa_, can be determined. As a result, in the state lookup, first get the state area based on the type of state (lines 1, 3, 5, and 7) and then look up the state value based on the state name (lines 2, 4, 6, and 8).  
Input: state s = {type,name}, global state areas gsa, packet enters table's state area tsa, packet matches entry's flow state area fsa, packet state area psa Output: state value  
1. If s.type == packet state:  
2. Find the state value according to s.name in psa  
3. If s. type == flow state:  
4. Find the state value according to s.name in fsa  
5. If s. type == table state:  
6. Find the state value according to s.name in tsa  
7. If s. type == global state:  
8. Find the state value according to s.name in psa  
9. Return state value ```  
**Algorithm 1** Look up the state  
In summary, MSSA restricts the scope of state sharing; the states that packets can find or store in packet processing are limited to four state areas. Therefore, constant-time state search and insertion can be realized when the number of states stored in each state area is limited.