# Time-Dependent Performance of a Multi-Hop Software Defined Network
## 2 Diffusion Model of an SDN Switch  
Figure 1 describes the basic system architecture of an SDN switch proposed in [1]. Arriving packets are temporarily queued at the input buffers and are then removed by the Arbiter and placed scheduled into the Packet Buffer. A copy of the packet header is forwarded to the Parser. The Parser parses the packet header to extract the header fields and then creates a tuple with the extracted information and forwards it to the Flow Match Unit. In the Flow Match Unit, the tuple is matched against existing flow rules stored in Flow Tables' flow entries. The flow entries in the Flow Tables are maintained under the controller's guidance and are updated when the controller installs new flow rules. The Flow Match Unit determines whether the packet is associated with a known flow and hence a known path. In case of success, the packet is then forwarded via the backplane. In case of failure (no flow table entry matches the packet header), a packet-in message will be  
sent by the SDN switch to the corresponding SDN controller [60] to notify the controller about the absence of a flow rule for the packet. The packet-in message contains either the packet or the packet's ID. The controller decides the correct action for the packet and then installs appropriate data in the flow table of the switch so that packets belonging to that particular flow can be forwarded subsequently. If there is no corresponding response from the controller, the packet will be dropped. The delay that can be experienced by packets consists of the queueing delay in the input buffer, the service delay in the input buffer, and the delay at the output buffers. When the output ports' processing and line speeds are significantly greater than the Openflow processing time, which includes the time required to parse the packet, check the flow tables to find matching entries, and execute the flow rule actions, the switch can be represented by a single server queueing as in several recent papers [27; 28; 29; 30; 61; 62; 63]. Since the size of the input buffer is limited, we represent the SDN switch as a single server queueing model with finite capacity \(N\). The packet interarrival times depend on the type of traffic, which the switch carries so that we allow for a generally distributed interarrival time distribution. The service time distribution will also be general to represent the manner in which the packets are handled in the entry buffer. The flow table matching process involves searching the flow tables to find the entries containing corresponding action sets--i.e., flow rules that match the header of the packets of the input flows that pass through the Parser. If there is more than one flow table, the flow match process starts from the first flow table, searches all of its entries, and jumps to the next flow table. The search process continues till an entry that matches the packet header is found. Otherwise, a \"packet-in\" message is generated. For hardware switches whose flow tables are implemented using Ternary Content Addressable Memory (TCAM) modules, the flow match process can be performed within one clock cycle, with parallel access to all the entries of the flow table, resulting in a constant access time. Because of the limited TCAM flow table size and the power-hungry nature of TCAM in hardware switches, software-based switches are an attractive alternative. However, they are limited by a slow processing speed when flow tables are searched sequentially. A majority of previous papers model the matching time as an exponentially distributed random variable [27; 28; 29; 61; 62; 63]. The use of a diffusion process allows us to model the flow matching process with a service time distribution that includes the flow tables' sequential search. Denote by \(p\) the probability that the flow rule of the arriving packet is not installed. The switch knows it after the examination of all \(K\) entries stored in the Flow Match Unit--i.e., time \(KT\)--where the examination of each entry requires time \(T\).