## 1 Introduction  
Software-defined networking (SDN) decouples the network's control plane and data plane, bringing unprecedented programmability to the network and encouraging the development of network algorithms. Many network algorithms (such as congestion control [1; 2; 3; 4], scheduling [5], measurement [6; 7; 8], active queue management [9; 10; 11; 12; 13], security [14], and load balancing [15; 16; 17; 18]) require the creation and modification of algorithm-defined states during packet traversal through the switch in order to respond to network emergencies [19]. However, in a traditional SDN, a centralized controller manages network states, while the stateless data plane is only responsible for packet forwarding and lacks state-processing capability. As a result, the states of these network algorithms can only be recorded in the control plane and processed by the controller [20]. The remote-control delay and communication overhead between the switch and the controller do not just reduce the response speed of network applications; they also increase the controller's burden and impact the controller's decision-making quality [21]. A lot of work has been proposed to maintain states in the data plane to enhance the response time of network applications and reduce the controller's burden [22; 23]. OpenState [24], the early stateful data-plane proposal, proposed the use of an extended finite state machine (XFSM) to improve the data-plane programmability, and the XFSM function was supported in the follow-up work, Open Packet Processor [25]. FAST (flow-level state transition) [26] uses state machine filter tables to isolate the states of different applications and speed up state search, while SDPA (Stateful Data Plane Architecture) [27] uses Forwarding Processors (FP). FlowBlaze [28] introduces an extended finite state machine (EFSM) [29]to maintain flow states and global states inside the switch, enhancing state-programming capabilities. The widely used network programming scheme P4 [30] supports the use of metadata to store a temporary state between flow tables and global registers for the persistent recording state. Although processing the state in the data plane improves network programmability, the time overhead added by looking up the state when processing packets may seriously harm switch's performance, which is exacerbated when there are a large number of states inside the switch [31]. Even though a data structure such as a cuckoo hash table [32] can guarantee constant lookup time, it may require a non-constant insertion time [28]. Slow insertion will also have a negative impact on the switch's throughput. For example, when performing 60 updates per second, the OpenFlow switch's throughput will be reduced by two times [33]. Furthermore, the network device's storage space is limited, and ensuring the state search speed may necessitate sacrificing the device's storage space. In a load-balancing application, for example, tens of millions of connections are tracked at the same time, and storing the states of 10 million connections in a match-action table requires hundreds of MB of SRAM, whereas the available SRAM in the latest generation of switches is only 50-100 MB [17]. In this paper, to ensure constant-time state search and insertion, as well as to optimize storage space utilization, we propose a state storage structure named multi-scope state area (MSSA) and a corresponding state search algorithm. By using MSSA, it is possible to achieve the following: (1) constant-time state search and state insertion; (2) effective use of state storage space and timely recovery of useless space. More precisely, the multi-scope state area is a hierarchical tree structure for storing states that is connected to the switch's multilevel match-action table structure. MSSA can limit the state search scope and possible insertion position in packet forwarding by utilizing the inherent operation of the match-action table.