## 3 REDSwitch
### Hash Table  
The developed REDSwitch includes a hash table, based on an open-source project [24]. In this table, all elements are connected to each other and are identified by two fields: a key and value. In this table, it is possible to insert, delete, and search for elements. The elements are inserted at the first empty address of the table, and, upon deletion, the respective address will be stored in the empty addresses list. After being inserted, each element will have added two new fields, one identifying whether there is an element next to it and the other with the respective address. Having all elements connected in this way will allow a search through the table without using specific addresses.  
This hash table will be used for the redundant packets; when working in normal mode, the switch will use the original MAC table. To identify the packet in the hash table, a key field consisting of a combination of 48 bits is used, using the lowest 40 bits from the source MAC address and the lowest 8 bits from the sequence number, because these are the bits that will change the most. Regarding the field value, it will be used to store the age of the packet, which will be used by the aging algorithm. The field value will start at zero.  
In this work, the delete algorithm of the hash table was changed to implement the proposed aging algorithm. Originally, the delete algorithm would have searched for a given key in the table, deleting the element if there was a match. The proposed aging algorithm, presented in Listing 1, keeps cycling through all elements, incrementing the value field (the age) of each one. When this value reaches a defined threshold (very old), it is deleted. Therefore, it is crucial to choose an appropriate threshold value to ensure that the first packet is not discarded before the second one arrives. Otherwise, the second packet may be incorrectly treated as a new packet. It is important to note that the aging algorithm starts when a delete command is received with a key with all bits equal to zero. Since no element can be inserted using zero as a key, this value was used to start the execution of the aging algorithm.  
```
1 threshold=10(customizableparameter)
2
3 cyclethroughalltableelements
4 calculatedifferencebetweenagingcounterand
5 elementvalue
6 ifdifference<threshold
7 updateelementvalue(+1)
8 else
9 checkcurrentstate(tofindelementposition)
10 ifstate=READ_HEAD_S
11 deleteelem.(stateKEY_MATCH_IN_HEAD_S)
12 else
13 ifstate=GO_ON_CHAIN_S
14 checkifelementsimiddle/end
15 ifgottail
16 deleteelem.(stateKEY_MATCH_IN_TAIL_S)
17 else
18 deleteelem.(stateKEY_MATCH_IN_MIDDLE_S)
19
20 setnextstatedonanalyzethenextelement:
21 ifgottail
22 statenext=READ_HEAD_S
23 else
24 statenext=GO_ON_CHAIN_S
```  
**Listing 1** Pseudocode of aging algorithm.  
It is possible to observe, in Listing 1, that there are three distinct key match states when an element needs to be deleted. The difference between these three key match states is related to the position of the element to be deleted, changing how the algorithm deals with the previous element. When an element is deleted, the algorithm needs to update the next pointer field of the previous element, except when deleting the first element (in the state KEY_MATCH_IN_HEAD_S). If it is a middle element (KEY_MATCH_IN_MIDDLE_S state), the algorithm updates the next pointer field with the current element's address. For the last element (in the state KEY_MATCH_IN_TAIL_S), it deletes the next pointer field value and changes the field's next valid element to zero, since the previous element is now the last one.