## 3 Shortest Queue Length-Cluster-Based Routing Protocol
### Specific Routing Process of SQL-CBRP  
As mentioned before, satellite self-organizing network routing faces issues such as high dynamics, high latency, and high signaling overhead. Therefore, SQL-CBRP adopts the concept of cluster-based routing, dividing the network into multiple cluster structures and separating routing into inter-cluster and intra-cluster routing. This approach can reduce the signaling overhead for network management and to some extent mitigate the impact of topology changes on routing, thereby reducing packet loss. Additionally, unlike traditional cluster-based routing protocols, SQL-CBRP does not use on-demand routing to establish paths passively. This is because in satellite networks with frequent topology changes, on-demand routing could lead to the frequent transmission of route discovery packets, which not only result in significant signaling overhead but also introduce latency in the process of searching for the routes. Accordingly, SQL-CBRP adopts a greedy algorithm to select the neighbor node with the shortest queue as the next hop, which not only eliminates the need for frequent route discovery flooding but also reduces queuing delay and packet loss due to queue overflow.  
The specific routing decision process of SQL-CBRP is as follows: Every time a cluster head node u forwards a data packet, the next hop cluster head node v sends a message back to node u, informing it of its current queue length. When node u needs to forward data the next time, it compares the queue lengths sent back by all neighbor nodes last time according to the locally maintained neighbor queue length table and selects the neighbor with the shortest queue length to forward, as shown in Algorithm 1. The process of this algorithm is as follows:  
1. When a cluster head node CH has a data packet to forward, it determines whether the destination node is within its cluster. If it is, the packet is sent directly to the destination node. If not, it consults the connection table;
2. If the local connection table indicates that there is a neighbor node closer to the destination node, then proceed to the next step. Otherwise, it is determined that the routing has failed;
3. Among the neighbor nodes closer to the destination node, compare their queue lengths and select the node with the shortest queue length as the next hop.  
```
Input: destination node Dest, neighbor cluster heads'set \(N\)
```  
Output: Nexthop;
1: Calculate the distance between this node and the destination node DistanceLocal
2:if Dest is in this cluster then
3:
4:
5:else
6:
7:for each neighbor \(n\in\)N do
8:
9: Calculate distance between neighbor \(n\) and destination node
10:
11:endfor
12:
13:if there are neighbors closer to destination than this node then
14:
15:
16:
17:else
18:
19:
20:
21:
22:endif
23:
24:returnNexthop ```  
**Algorithm 1** Routing Algorithm Based on Shortest Queue Length  
After the next hop node receives the data packet, it sends back its current queue length to node CH, and based on this, CH updates the queue length table of its neighbors. The updates of local queue length information are frequent as the cluster heads forward packets continuously, so a cluster head can determine next hop based on the queue length information updated recently, which can lead to a relevant reliable routing decision.  
Although the information of nodes' queue lengths adds overhead, it does not need to be flooded over the entire network. Its transmission is limited between cluster heads, and it only needs to be sent to the last hop cluster head instead of being broadcasted. Therefore, the increased overhead is not severe. Compared to routing protocols that require global flooding of signaling, this algorithm actually reduces the overall network overhead.