Self-organizing network concepts for small cells backhauling

Abstract

A mesh network includes domain(s) of multiple nodes interconnected through links and in which there are gateway(s) connecting a domain to another network. The domain(s), their multiple nodes, and their links are part of a topology. A set of primary and backup routing paths, each including an ST that includes the selected gateway and route to that selected gateway for nodes in the domain, for a selected one of the gateway(s) is accessed or determined. Schedule(s) to be used by node(s) in the mesh network over one or more scheduling cycles are accessed or determined. Based on status of link(s) between nodes and on the schedule(s), switching is performed to a selected one of the primary or backup routing paths for the selected gateway. Routing in the mesh network is caused to be modified based on the selected routing path. Information is sent to nodes for the paths and schedules.

What is claimed is: 
     
       1. A method comprising:
 in a mesh network comprising one or more domains of multiple nodes interconnected through links and including at least one gateway in a selected domain connecting the selected domain to another network, wherein the one or more domains and their multiple nodes and their links are part of a topology, accessing a set of primary and backup routing paths for a selected one of the at least one gateways, wherein the topology is determined at least in part by one of splitting or merging the one or more domains and indicating whether at least one new gateway should be associated with the one or more domains following the one of splitting or merging, wherein each primary and backup routing path for the selected gateway comprises a spanning tree that comprises the selected gateway and route to that selected gateway for nodes in the selected domain, wherein the nodes comprise small cells providing access by user equipment to the another network through backhaul to the gateway, and wherein the gateway comprises a macro cell accessing each of the multiple nodes in the selected domain via at least the backhaul; 
 accessing a link schedule to be used at least by the multiple nodes in the selected domain in the mesh network, the link schedule comprising transmission sets comprising disjoint links that can be active simultaneously, and the transmission sets are ordered into a schedule cycle by one or more of the following:
 identifying and constructing one of the transmission sets in each slot of the scheduling cycle, where the one of the transmission sets is constructed with a highest number of the disjoint links that can be active simultaneously; 
 identifying a minimal number of slots per cycle that can cover all links in the mesh network; or 
 assigning one of the transmission sets to each slot of the scheduling cycle by identifying the order of the transmission sets in the scheduling cycle to ensure an end-to-end delay; 
 switching, based on status of one or more of the links for one or more of the multiple nodes in the selected domain and on the link schedule, to a selected one of the primary or backup routing paths for the selected gateway; and 
 causing routing in at least part of the mesh network in the selected domain to be modified based on the selected routing path. 
 
 
     
     
       2. The method of  claim 1  wherein the method further comprises determining the set of primary and backup routing paths for the selected gateway, wherein determining the set of primary and backup routing paths for the selected gateway is performed by performing at least the following:
 assigning links immediately adjacent to the selected gateway as stems of a tree, which are connected to the root of the tree, and the root is the selected gateway; 
 growing each stem into branches until a union of all branches includes the nodes in the selected domain; and 
 grow each branch until a full spanning tree results that covers the selected domain. 
 
     
     
       3. The method of  claim 2 , further comprising optimizing leaf nodes in the branches at least by moving a leaf node to another parent node if moving the leaf node to the another parent node via a direct hop link to the parent node results in a smaller hop count. 
     
     
       4. The method of  claim 2 , wherein the number of spanning trees is equal to the number of stems, which is equal to the number of routes per node to the selected gateway. 
     
     
       5. The method of  claim 2 , further comprising for each of the multiple nodes in the selected domain, identifying a priority of multiple paths in the spanning trees to the selected gateway at least by:
 setting a highest priority to a path that is lowest in number of hop counts to the selected gateway; 
 breaking a tie in an equal hop count situation to set one path in the situation as a higher priority path; and 
 the path with the highest priority is called the primary path. 
 
     
     
       6. The method of  claim 5 , wherein breaking the tie further comprises breaking the tie by using one or more of the following: weight of the node; expected traffic demand is shared as equally as possible between spanning trees; and random assignment. 
     
     
       7. The method of  claim 1 , wherein for each of the one or more domains that comprise a plurality of gateways:
 the accessing a set of primary and backup routing paths, the accessing a link schedule, the switching and the causing routing are performed for each of the plurality of gateways in the domain; and 
 the spanning trees for each of the plurality of gateways span the nodes in the corresponding domain. 
 
     
     
       8. The method of  claim 1 , further comprising determining the link schedule to be used by one or more of the nodes in the mesh network to implement the one or more scheduling cycles at least by constructing the transmission sets and ordering the constructed transmission sets into the schedule cycle. 
     
     
       9. The method of  claim 8 , wherein the constructing and ordering the transmission sets comprises the following:
 in each schedule cycle, each link should be given at least one chance for transmission; and 
 some links are considered to be more important than other links and should be given more chances in each schedule cycle. 
 
     
     
       10. The method of  claim 1 , performed by a certain node in the mesh network, and wherein the method further comprises the certain node using virtual connections and traffic flows to transfer received client data over links in the mesh network. 
     
     
       11. The method of  claim 10 , wherein using virtual connections comprises mapping incoming traffic for the client data into virtual connections that are identified by virtual connection identifiers. 
     
     
       12. The method of  claim 1 , performed by a certain node, wherein the certain node handles traffic as flows, wherein the flows are separated by quality of service priority identification and virtual connection identification, and the switching causes local forwarding of traffic using pre-calculated route alternatives from the primary and backup routing paths and based on local load and congestion status information. 
     
     
       13. The method of  claim 12 , wherein the local forwarding further comprises one or more of the following:
 selecting by an ingress node as the certain node a path from the primary and backup routing paths by using pre-computed path preferences and status of a bottleneck link in each path; 
 making different forwarding decisions based on each priority class; 
 making forwarding decisions using local forwarding tables comprising a best available path based on preferences set by route computation; 
 forming and maintaining a local forwarding table based on topology configuration information and network status information, comprising updating the table every time a new topology configuration is received and every time new status information is received from the network indicating one or more link failures, link congestion and/or other anomalies; 
 estimating by an ingress node as the certain node the applicability of alternative routing paths for each traffic flow through the ingress node; 
 inspecting by an intermediate node as the certain node only a spanning tree identifier and mesh network identifier when making forwarding decisions; 
 assigning frames into correct queues at an output port based on priority information; and/or 
 using strict priority queueing as a target to force lower priority traffic to alternate paths instead of sharing capacity in a bottleneck link, wherein the using occurs such that the sharing is performed in a fair manner. 
 
     
     
       14. The method of  claim 1 , wherein the switching performs one or more on-demand dynamic load balancing methods comprising one or more of the following:
 path re-selection load balancing is applied only at ingress nodes, and intermediate nodes do not change an originally selected path; 
 based on path status information, an alternative pre-computed path is selected from a priority list; 
 path re-selection load balancing is flow based, and a complete flow is redirected to an alternative path; 
 path re-selection load balancing is priority based, and a highest priority flow gets first the most optimum routing path, the second highest priority flow gets the next best available route, with this process continuing through remaining flows; 
 in path re-selection load balancing, higher priority traffic flow overrides lower priority traffic flow or higher priority traffic flow overrides and pre-empts lower priority traffic flow; 
 inverse multiplexing based load balancing is applied to balance low priority bulk and best effort traffic on a packet-based fashion; 
 inverse multiplexing based load balancing is applied only for lower priority traffic; in inverse multiplexing based load balancing, all available paths are used; 
 in inverse multiplexing based load balancing is packet based, wherein each incoming packet is directed to a least congested path; and/or 
 packets are sequence numbered and re-ordering is performed at domain egress nodes. 
 
     
     
       15. The method of  claim 1 , wherein a scheduling cycle in the one or more scheduling cycles comprises different transmission sets of active links using the multiple nodes in the selected domain and an order of the different transmission sets. 
     
     
       16. The method of  claim 1 , wherein the transmission sets are ordered into a schedule cycle by all of the following:
 identifying and constructing one of the transmission sets in each slot of the scheduling cycle, where the one of the transmission sets is constructed with a highest number of the disjoint links that can be active simultaneously; 
 identifying a minimal number of slots per cycle that can cover all links in the mesh network; and 
 assigning one of the transmission sets to each slot of the scheduling cycle by identifying the order of the transmission sets in the scheduling cycle to ensure an end-to-end delay. 
 
     
     
       17. The method of  claim 1 , wherein the nodes connect to each other through line-of-sight backhaul connections. 
     
     
       18. The method of  claim 17 , wherein the nodes are equipped with a backhaul radio that can only be steered to one neighboring node at a time. 
     
     
       19. An apparatus including one or more processors and one or more memories including computer program code configured to with the one or more processors, cause the apparatus to:
 in a mesh network comprising one or more domains of multiple nodes interconnected through links and including at least one gateway in a selected domain connecting the selected domain to another network, wherein the one or more domains and their multiple nodes and their links are part of a topology, access a set of primary and backup routing paths for a selected one of the at least one gateways, wherein the topology is determined at least in part by one of splitting or merging the one or more domains and indicating whether at least one new gateway should be associated with the one or more domains following the one of splitting or merging, wherein each primary and backup routing path for the selected gateway comprises a spanning tree that comprises the selected gateway and route to that selected gateway for nodes in the selected domain, wherein the nodes comprise small cells providing access by user equipment to the another network through backhaul to the gateway, and wherein the gateway comprises a macro cell accessing each of the multiple nodes in the selected domain via at least the backhaul; 
 access a link schedule to be used at least by the multiple nodes in the selected domain in the mesh network, the link schedule comprising transmission sets comprising disjoint links that can be active simultaneously, and the transmission sets are ordered into a schedule cycle by one or more of the following:
 identifying and constructing one of the transmission sets in each slot of the scheduling cycle, where the one of the transmission sets is constructed with a highest number of the disjoint links that can be active simultaneously; 
 identifying a minimal number of slots per cycle that can cover all links in the mesh network; or 
 assigning one of the transmission sets to each slot of the scheduling cycle by identifying the order of the transmission sets in the scheduling cycle to ensure an end-to-end delay; 
 
 switch, based on status of one or more of the links for one or more of the multiple nodes in the selected domain and on the link schedule, to a selected one of the primary or backup routing paths for the selected gateway; and 
 cause routing in at least part of the mesh network in the selected domain to be modified based on the selected routing path. 
 
     
     
       20. An apparatus including one or more processors and one or more memories including computer program code configured to, with one or more processors, cause the apparatus to:
 in a mesh network comprising one or more domains of multiple nodes interconnected through links, wherein the one or more domains and their multiple nodes and their links are part of a topology, and wherein at least one gateway for a selected domain is configured to connect the selected domain to another network, determine a set of primary and backup routing paths for a selected one of the at least one gateways, wherein the topology is determined at least in part by one of splitting or merging the one or more domains and indicating whether at least one new gateway should be associated with the one or more domains following the one of splitting or merging, wherein the selected gateway is configured to access the multiple nodes in the selected domain, and wherein each primary and backup routing path for the selected gateway comprises a spanning tree that comprises the selected gateway and route to that selected gateway for nodes in the selected domain, wherein the nodes comprise small cells providing access by user equipment to the another network through backhaul to the gateway, and wherein the gateway comprises a macro cell accessing each of the nodes in the selected domain via at least the backhaul; 
 determine a link schedule to be used at least by the multiple nodes in the selected domain in the mesh network, the link schedule comprising transmission sets comprising disjoint links that can be active simultaneously, and the transmission sets are ordered into a schedule cycle by one or more of the following:
 identifying and constructing one of the transmission sets in each slot of the scheduling cycle, where the one of the transmission sets is constructed with a highest number of the disjoint links that can be active simultaneously; 
 identifying a minimal number of slots per cycle that can cover all links in the mesh network; or 
 assigning one of the transmission sets to each slot of the scheduling cycle by identifying the order of the transmission sets in the scheduling cycle to ensure an end-to-end delay; and 
 
 send information to at least the nodes in the selected domain in the mesh network, wherein the information for a node in the selected domain describes at least the primary and backup routing paths for the nodes and the link schedule for the multiple nodes for the selected domain.