# SDN-Based Routing Framework for Elephant and Mice Flows Using Unsupervised Machine Learning
## 3 Proposed Methodology
### Architecture Implementation  
The details of the algorithm for routing a flow are illustrated in Algorithm 1. This algorithm seeks to identify the best path in order to route each flow, which is the major procedure of the proposed framework. The procedure starts with extracting all the information of each input packet, such as source IP, destinationIP, import, and output. For each packet of the input flow, the existence of the source in the macTable is checked. Then, it is added to the macTable if it is not there. Thereafter, the destination is checked if it is in the macTable or not. In the case that a destination does not exist in the macTable, a broadcast  
Figure 2: SDN-Based Application Framework. message will be sent. Otherwise, a topology discovery will be executed using a Link Layer Discovery Protocol (LLDP). Next, Algorithm 2 FAS (Find all Available paths between two Switches) will be implicitly called by Algorithm 3 FAPBS (Find all Available Paths Between each pair of Switches) to find all available paths between each pair of switches. ```
1. Every new flow,extract flow information (src, dst, inport, outport, etc.) 2. adjacency\(\leftarrow\)\(\mathcal{O}\)
3. availableBW\(\leftarrow\)\(\mathcal{O}\) {availableBW:available bandwidth}
4. paths \(\leftarrow\)\(\mathcal{O}\)
5. clusterID\(\leftarrow\)\(\mathcal{O}\)
6. flowType\(\leftarrow\)\(\mathcal{O}\)
7. acceptableLatency \(\leftarrow\)\(\mathcal{O}\)
8. bestpath \(\leftarrow\)\(\mathcal{O}\)
9. if src not in macTable, then
10. add src to macTable
11. end if
12. if dst in macTable, then
13. check topology using LLDP to get adjacency and availableBW
14. paths \(\leftarrow\) FAPBS(adjacency, availableBW)
15. clusterID, flowType, acceptableLatency \(\leftarrow\) flowIdentification(kmeansModel, flow)
16. bestpath \(\leftarrow\) SelectBestPaths(src, dest, acceptableLatency, flowType, paths)
17. paths \(\leftarrow\) updatedPaths(paths, availableBW)
18. else
19. send broadcast message
20. end if
```  
**Algorithm 1** Algorithm for routing a flow  
```
1. source: source switch
2. destination: destination switch
3. adjacency: adjacency matrix represents the network as a graph
4. paths: set of available paths between source and destination
5. paths \(\leftarrow\)\(\mathcal{O}\)
6. QueOfPaths \(\leftarrow\) Queue()
7. QueOfNode \(\leftarrow\) Queue()
8. QueOfNode.add(source)
9. for each len(QueOfPaths) > 0 do
10. currPath \(\leftarrow\) QueOfPaths.pop()
11. lastNode \(\leftarrow\) currQue[\(-\)1]
12. if lastNode matches destination then
13. paths.append(currPath)
14. end if
15. for each neighbor in adjacency[lastNode] do
16. newPath \(\leftarrow\) copy(currPath)
17. newPath.add(neighbor)
18. if!QueOfPaths.contains(newPaths) then
19. QueOfPaths.add(newPath)
20. end if
21. end for
22. end for
23. for each availablePaths in paths do
24. for each path in availablePaths do
25. cost \(\leftarrow\) updateCost(path)
26. path.addLast(cost)
27. end for
28. end for
```  
**Algorithm 2** Find all Available paths between two Switches (FAS)The aim of the K-means clustering and identification processes is to obtain representative flows for each mice and elephant type. Each representative flow is characterized by their network performance metrics. The flow identification process starts with extracting three parameters for each flow in each cluster. These parameters are flow duration, packet count, and average packet size. In the case of having a packet count higher than 15, a flow duration higher than 5 s, and an average packet size higher or equal to 10 KB, the flow is predicted as an elephant. Otherwise, the predicted flow is mice. This process is implemented by calling Algorithm 4. At the end of this process, three variables are obtained. clusterID represents the ID of the predicted cluster, flowType is a string indicating a mice or elephant flow, and the acceptable delay of the flow is represented as a float number called acceptableLatency. ```
1. \(\mathrm{APR}\): set of rules for predefined parameters
2. \(\mathrm{CID}\): set of predicted clusters (kmeansModel)
3.