Patent Publication Number: US-2023155929-A1

Title: Parameterized Method for Network Subgraph Root Node Selection

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation of International Patent Application No. PCT/US2020/041825, filed on Jul. 13, 2020, and titled “Parameterized Method for Network Subgraph Root Node Selection,” which is hereby incorporated by reference in its entirety. 
    
    
     TECHNICAL FIELD 
     The present disclosure is generally related to network topologies, and more particularly, to methods of selecting a root node for a subgraph of a given network topology. 
     BACKGROUND 
     Packet switched computer networks comprise a plurality of nodes interconnected to one another via links. When user data traffic arrives at an edge node from source a user equipment (UE), such traffic is forwarded by that node and each subsequent node it encounters to zero or more directly connected nodes in the network. If the traffic reaches one or more subsequent edge nodes, it usually departs the network to a destination UE. Control data may also be transmitted between nodes in the network. In a process referred to as “flooding,” control data may be forwarded to reach every node in the network. 
     SUMMARY 
     A first aspect relates to a method of selecting a root node for a to-be-constructed subgraph of a network. The method includes: obtaining link costs of links connecting a plurality of nodes in the network; selecting a weighting parameter based at least partly on the link costs; calculating node costs corresponding to each of the plurality of the nodes based on the link costs and the weighting parameter; and selecting a node as the root node based on the node costs, wherein the root node is selected from the plurality of nodes. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that selecting the node as the root node comprises selecting at least one node having a lowest node cost. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that selecting the weighting parameter is based on a first quantity of links connected to each node and a second quantity of links that are of lower link costs than other links in the network. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides for calculating the node costs corresponding to each of the plurality of nodes using the following formula: 
     
       
         
           
             
               
                 Node 
                 ⁢ 
                     
                 Cost 
               
               = 
               
                 
                   HarmonicMean 
                   ( 
                   
                     
                       C 
                       ⁢ 
                       
                         1 
                         k 
                       
                     
                     , 
                     
                       C 
                       ⁢ 
                       
                         2 
                         k 
                       
                     
                     , 
                     
                       C 
                       ⁢ 
                       
                         3 
                         k 
                       
                     
                     , 
                     … 
                   
                       
                   ) 
                 
                 NumberOfLinks 
               
             
             , 
           
         
       
     
     where C1, C2, C3, . . . represent the links costs, where k represents the weighting parameter, and where the Number of Links is a quantity of links connected to the node for which the node cost is calculated. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that C1, C2, C3, . . . are integers greater than zero. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that selecting the weighting parameter comprises setting k to a value greater than 1. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that selecting the weighting parameter comprises setting k to a value between 0 and 1. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that selecting the weighting parameter comprises setting k to a value equal to 1. 
     A second aspect relates to a network device for root node selection. The network device includes a storage device and a processor coupled to the storage device. The processor is configured to execute instructions stored on the storage device to cause the network device to: obtain link costs of links connecting a plurality of nodes in the network; select a weighting parameter based at least partly on the link costs; calculate node costs corresponding to each of the plurality of the nodes based on the link costs and the weighting parameter; and select a node as a root node based on the node costs, wherein the root node is selected from the plurality of nodes 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that the network device selects the node as the root node by selecting at least one node having a lowest node cost. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that the network device selects the weighting parameter based on a first quantity of links connected to each node and a second quantity of links that are of lower link costs than other links in the network. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides for calculating the node costs corresponding to each of the plurality of nodes using the following formula: 
     
       
         
           
             
               
                 Node 
                 ⁢ 
                     
                 Cost 
               
               = 
               
                 
                   HarmonicMean 
                   ( 
                   
                     
                       C 
                       ⁢ 
                       
                         1 
                         k 
                       
                     
                     , 
                     
                       C 
                       ⁢ 
                       
                         2 
                         k 
                       
                     
                     , 
                     
                       C 
                       ⁢ 
                       
                         3 
                         k 
                       
                     
                     , 
                     … 
                   
                       
                   ) 
                 
                 NumberOfLinks 
               
             
             , 
           
         
       
     
     where C1, C2, C3, . . . represent the links costs, where k represents the weighting parameter, and where the Number of Links is a quantity of links connected to the node for which the node cost is calculated. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that C1, C2, C3, . . . are integers greater than zero. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that the network device selects the weighting parameter by setting k to a value greater than 1. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that the network device selects the weighting parameter by setting k to a value between 0 and 1. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that the network device selects the weighting parameter by setting k to a value equal to 1. 
     A third aspect relates to a network device for root node selection. The network device includes: means for obtaining link costs of links connecting a plurality of nodes in a network; means for selecting a weighting parameter based at least partly on the link costs; means for calculating node costs corresponding to each of the plurality of the nodes based on the link costs and the weighting parameter; and means for selecting a node as the root node based on the node costs, wherein the root node is selected from the plurality of nodes. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that selecting the node as the root node comprises selecting at least one node having a lowest node cost. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that selecting the weighting parameter is based on a first quantity of links connected to each node and a second quantity of links that are of lower link costs than other links in the network. 
     Optionally, in any of the preceding aspects, another implementation of the aspect provides that a node cost for calculating the node costs corresponding to each of the plurality of nodes is calculated using the following formula: 
     
       
         
           
             
               
                 Node 
                 ⁢ 
                     
                 Cost 
               
               = 
               
                 
                   HarmonicMean 
                   ( 
                   
                     
                       C 
                       ⁢ 
                       
                         1 
                         k 
                       
                     
                     , 
                     
                       C 
                       ⁢ 
                       
                         2 
                         k 
                       
                     
                     , 
                     
                       C 
                       ⁢ 
                       
                         3 
                         k 
                       
                     
                     , 
                     … 
                   
                       
                   ) 
                 
                 NumberOfLinks 
               
             
             , 
           
         
       
     
     where C1, C2, C3, . . . represent the links costs, where k represents the weighting parameter, and where the Number of Links is a quantity of links connected to the node for which the node cost is calculated. 
     The disclosed techniques improve construction of network subgraphs by prioritizing richly connected and more powerful nodes for selection as a root node. Computing the priority of a particular node may be facilitated by prioritizing nodes according to information local to each node, such as a total number of links connecting each node to other nodes as well as the cost of such links, where link costs may be based on bandwidth. To this end, a root node of a to-be-constructed subgraph may be calculated by selecting a node whose cost has a smallest quotient of the harmonic mean of link costs divided by a number of links connected to that node. While this calculation might be impractical for humans to perform, one or more network components (e.g., nodes, routers, controllers, etc.) can be configured to calculate such quotients without having to perform any sort of exponential or polynomial difficult computation of a global metric over an entire network/subgraph/path. 
     For the purpose of clarity, any one of the foregoing implementation forms may be combined with any one or more of the other foregoing implementations to create a new embodiment within the scope of the present disclosure. These embodiments and other features will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings and claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       For a more complete understanding of this disclosure, reference is now made to the following brief description, taken in connection with the accompanying drawings and detailed description, wherein like reference numerals represent like parts. 
         FIG.  1 A  is a schematic diagram of a network according to an embodiment of the disclosure; 
         FIGS.  1 B- 1 H  depict different stages of a subgraph constructed for the network in  FIG.  1 A ; 
         FIG.  2    is a flow chart of selecting a root node for a to-be-constructed subgraph of the network in  FIG.  1 A ; 
         FIG.  3    is a chart depicting Node Costs calculated according to embodiments of the disclosure; 
         FIGS.  4 A- 4 D and  5 A- 5 D  depict different stages of constructing subgraphs according to embodiments of the disclosure; and 
         FIG.  6    is a schematic diagram of a network device according to an embodiment of the disclosure; 
         FIG.  7    is a schematic diagram of an apparatus for implementing root node selection and subgraph construction methods according to embodiments of the disclosure. 
     
    
    
     DETAILED DESCRIPTION 
     It should be understood at the outset that although an illustrative implementation of one or more embodiments are provided below, the disclosed systems and/or methods may be implemented using any number of techniques, whether currently known or in existence. The disclosure should in no way be limited to the illustrative implementations, drawings, and techniques illustrated below, including the exemplary designs and implementations illustrated and described herein, but may be modified within the scope of the appended claims along with their full scope of equivalents. 
     In some cases, a “tree” or “distribution tree” is used for transmission of user data and/or control data. A tree is a subgraph comprising an acyclic subset of the inter-node links that reaches every node in the network. Typical examples of such trees/graphs include a “spanning tree protocol” graph in bridged networks and multicast data distribution trees in the Transparent Interconnection of Lots of Links (TRILL) specification. Unless stated otherwise, “tree,” “distribution tree,” “subgraph,” and “graph” are used herein interchangeably. 
     In other cases, a graph may be used for flooding control information. Such a graph differs from an acyclic tree in that it usually provides some redundancy of paths, and thus includes cycles. For example, the graph might be constructed such that each node is at least doubly connected, i.e., each node is attached to at least two links that are part of the flooding graph. Alternatively, the graph might be constructed so each node is triply or even more richly connected. Such more richly connected graphs can be constructed by first constructing an acyclic tree, and then adding selected links to achieve the desired richness of connectivity. However, there may be some nodes in the network that are only singly connected or otherwise have limited connectivity for which the desired richness of connectivity is unreachable. 
     A routing protocol specifies how routers communicate with each other, distributing information that enables them to select routes between any two nodes on a computer network. An interior gateway protocol (IGP) is a type of protocol used for exchanging routing information between gateways (commonly routers) within a network, which may be any suitable type such as an autonomous system (AS). This routing information can then be used to route network-layer protocols like Internet Protocol (IP) packets. 
     Within IGP, there are different types of protocols such as a link-state routing protocol. The link-state routing protocol is performed by every switching node in the network (i.e., nodes that are prepared to forward packets; in the Internet, these are called routers). The basic concept of link-state routing is that every node constructs a map of the connectivity of the network, in the form of a graph, showing which nodes are connected to which other nodes. Each node then independently calculates the best, for example lowest cost, logical path or the best next hop interface from it to every possible destination in the network. Each collection of best paths will then form each node&#39;s routing table. Examples of link-state routing protocols include Open Shortest Path First (OSPF) routing protocol and Intermediate System to Intermediate System (IS-IS). OSPF is a standard routing protocol designated by the Internet Engineering Task Force (IETF). 
     OSPF uses Link State Advertisement (LSA) to exchange routing information between routers. IS-IS is a routing protocol standardized by the International Standards Organization (ISO). IS-IS uses Link State Protocol Data Unit (LSP) to exchange routing information between routers. For link-state routing protocols such as OSPF or IS-IS, control data is commonly flooded by each node sending such data on many and/or all links, with received duplicates of control data being discarded. This method of flooding control data can be wasteful in some cases. In a richly connected network, for example, a node will typically receive many copies (possibly even a hundred or more) of a link state update. As such, a flooding graph that reduces redundant transmission of control information may be used. 
     The construction or derivation of a distribution tree, flooding graph, or the like is usually implemented by the following steps: (a) select a root node from which to grow the tree/graph (the root node may be designated as layer zero); (b) select and add links from that root node to directly connected nodes (these links and directly connected nodes may be designated as layer one); (c) if there are remaining nodes that are not part of the tree/graph, select links that are not yet part of the tree from layer one nodes to nodes that are not yet part of the tree (these added links and nodes may be designated as layer two); and (d) in each subsequent step, if there are remaining nodes that are not part of the tree, select links that are not yet part of the tree from the nodes of the layer added by the previous step to nodes that are not yet part of the tree (these added links and nodes may be designated as the next higher numbered layer, e.g., layer three, layer four, etc.). For some types of sub-graphs, such as link state flooding sub-graphs, there may be one or more additional stages in which additional links are added to the sub-graph. However, a tree or subgraph might be constructed in other ways after the selection of a root node. For example, links could be added from remote nodes working towards the root rather than from the root outward. Alternatively, these techniques could be combined or a tree could be built in other ways with a selected root. 
     A tree may have multiple parallel physical links between a pair of nodes. When this situation is detected, (1) all but one of the links may be disabled for traffic; (2) the multiple links may be treated as a single link with traffic being split across the links; or (3) some combination of (1) and (2), e.g., with some of the parallel physical links being disabled while splitting traffic across those still enabled. In any case, all of these options may be treated as there being a single logical link between the nodes. 
     Links have a “cost” associated with them and the optimization of the path for data through a network is commonly thought of as minimizing the sum of the costs associated with the links over which that data passes. Most commonly the “cost” for a link is based on the reciprocal of the speed of that link. For example, the cost might be set to 20,000,000,000,000 (20 trillion) divided by the link speed in bits per second (bps). As another example, the cost could be based on reliability, monetary cost, delay, security, or any combination of these or other factors. Traditionally, the cost of a link is expressed as a positive integer. Costs are usually symmetric, meaning a link connecting nodes N 1  and N 2  would have the same cost from N 1  to N 2  as that from N 2  to N 1 . However, there can be asymmetric costs where the cost from N 1  to N 2  is different from the cost from N 2  to N 1 . 
     It is possible to use different definitions of link cost for different traffic. For example, traffic such as real-time gaming traffic might be very sensitive to delay, while bulk file transfers might be more sensitive to bandwidth or monetary cost. As such, different subgraphs may be constructed for such different traffic. For unicast routing applications, the goal is to minimize the cost of the path (sequence of links) over which data flows. 
     In a given tree, every node should have the same understanding of the tree&#39;s topology so that when receiving traffic on a link, the node can know what other links to send that data on. Constructing a subgraph of a network can be done in a distributed or centralized manner. For example, a distributed subgraph construction involves each node having sufficient information to compute how it fits into the subgraph. In contrast, a centralized subgraph construction involves one or more centralized controllers processing information to construct the subgraph and then sending that information to all of the nodes in the network. 
       FIG.  1 A  is a schematic diagram of a network  100  comprising a plurality of nodes n 1 , n 2  . . . , n 30  interconnected to one another via a plurality of links. In some embodiments, the links may be of varying bandwidths. In  FIG.  1 A , for example, the links include low bandwidth links  102  and high bandwidth links  104 , the latter of which are denoted by thicker and bolder lines. Although 4 high bandwidth links (i.e., n 1 -n 2 , n 1 -n 3 , n 1 -n 4 , and n 4 -n 6 ) are depicted in this example, the network  100  may include more or less high bandwidth links in other examples. 
     Every node n 1 , n 2  . . . , and n 30  in the network  100  should have the same understanding of the network&#39;s topology so that when receiving traffic on a link, the node can know what other links to send that data on. To this end, a subgraph of the network  100  may be constructed. Constructing a subgraph may take place in a distributed or centralized manner. For example, a distributed subgraph construction involves configuring every node n 1 , n 2  . . . , and n 30  with sufficient information to compute how it fits into the subgraph. In contrast, a centralized subgraph construction involves one or more centralized controllers processing information of the constructed subgraph and then sending that information to all nodes n 1 , n 2  . . . , and n 30  in the network  100 . 
     Regardless of the manner chosen, constructing a subgraph for the network  100  may begin with selecting a root node (e.g., n 1 , n 2  . . . , or n 30 ) from which the subgraph is to be constructed. One common selection method according to other approaches involves manually configuring a priority for a node to be selected as the root node. Alternatively, the root node may be automatically selected based on an identifier such as a serial number, an interface address (e.g., a medium access control (MAC) or Internet Protocol (IP) address of each node&#39;s port), an “order” or “degree” of a node (i.e., the number of other nodes to which it is directly connected by a link), or the like. 
     For example, a node having the lowest port MAC address or a node having the highest order node may be automatically selected as the root node. In some cases, a tiebreaking procedure may be implemented when the manual or automatic selection of a root node results in multiple root node candidates (e.g., if two or more nodes may have the same priority or order). In such cases, the tiebreaking procedure may be based on an arbitrary unique number associated with a node (e.g., built-in device serial number, the lowest or highest address of one of the node ports, or the like). 
     Using an example according to other approaches, assume that the highest numbered node is automatically selected as the root node for constructing a subgraph of the network  100 . Further assume the following: at each subsequent stage, the edge nodes of layer N are examined starting from the highest numbered layer N node to the lowest numbered layer N node; for each node examined, a link is added to each node to which it has a direct link if that node is not yet part of the subgraph in order to construct layer N+1 of the tree; and this same process is repeated for the next higher numbered layer until all nodes n 1 , n 2  . . . , and n 30  are part of the subgraph. A process of constructing a subgraph based on the foregoing example is further described with respect to  FIGS.  1 B- 1 H . 
     As shown in  FIG.  1 B , the process begins with automatically selecting node n 30  as the root node because n 30  is the highest numbered node in the network  100 . The selection of root node n 30  completes stage zero of constructing the subgraph. Note that each node to which the root node is connected in the following first stage may refer to a “layer one node.” Similarly, each node to which a layer one node is connected in the second stage may refer to a “layer two node,” each node to which a layer two node is connected in the third stage may refer to a “layer three node,” and so forth. 
     The first stage of constructing the subgraph involves connecting the root node n 30  to one or more other nodes in the network  100  that are not yet part of the subgraph. In this example, the root node n 30  has two available connections. Thus, the root node n 30  may be connected to 2 layer one nodes by adding one link from n 30  to n 25  and another link from n 30  to n 2  (the added links are shown via highlighted lines in  FIG.  1 C ). The addition of these two links completes the first stage. 
     The second stage involves connecting layer one nodes n 25  and n 2  to one or more layer two nodes. As shown in  FIG.  1 D , this stage begins with adding a link from n 25  to a layer two node n 1  before adding any links from n 2  because n 25  is a higher numbered node than n 2 . Since no other connection links are available for n 25 , the second stage ends with adding 4 links from n 2  to layer two nodes n 10 , n 11 , n 12 , and n 3 , such as shown in  FIG.  1 E . Note that although a link from n 2  to n 1  is available, this link is not added because n 1  has already been connected via the link from n 25 . Further, adding a link from n 2  to n 1  would result in a loop (i.e., between n 30 , n 25 , n 1 , and n 2 ), which can adversely impact data transmissions within the network  100  (e.g., when sending broadcast traffic or multicast data). 
     The third stage includes adding links from the layer two nodes (i.e., n 1 , n 10 , n 11 , n 12 , and n 3 ) to one or more nodes that not yet part of the subgraph. Note that no additional links are available from layer two nodes n 10  and n 11 . While a link is available for connecting n 12  to n 3 , this link is not added to the subgraph because n 3  is already connected to n 2 . Thus, the third stage may ignore layer two nodes n 10 , n 11 , and n 12  and proceed with adding links from n 1  and n 3 , beginning with the latter since n 3  is a high numbered node. As shown in  FIG.  1 F , the third stage is complete after adding 6 links from n 3  to layer three nodes n 13 , n 9 , n 8 , n 7 , n 6 , and n 4 , and then adding 2 links from n 1  to layer three nodes n 24  and n 5 . 
     The fourth stage commences with the highest numbered layer three node n 24 , which has one available connection to n 5 . However, a link is not added from n 24  to n 5  because n 5  has already been connected to n 1 . The second highest numbered layer three node is n 13 , but a link from n 13  to n 9  is not added for similar reasons. The third highest numbered layer three node is n 9 , which has 8 available connections. Thus, the fourth stage begins with adding 7 links from n 9  to layer four nodes n 14 , n 26 , n 27 , n 28 , n 29 , n 15 , and n 16 , but without adding an eighth link from n 9  to n 8  because n 8  has already been connected to n 3 . The next highest numbered layer three node is n 8 , but a link is not added from n 8  to n 16  because n 16  has already been connected to n 9 . The next highest numbered layer three node is n 7 , which has two available connections. Here, a link is added from n 7  to layer four node n 17 , but not to n 16 . Next, 2 links are added from n 6  to layer four nodes n 18  and n 20 , but not to n 17 . As shown in  FIG.  1 G , the fourth stage is complete after adding 2 links from n 5  to layer four nodes n 23  and  21 . 
     The fifth stage begins with adding a link from n 23  to layer five node n 22 , and ends with adding a link from n 20  to layer five node n 19 , thereby completing the subgraph. As shown in  FIG.  1 H , the constructed subgraph represents a complete acyclic tree spanning all nodes n 1 , n 2  . . . , and n 30  in the network  100 . Although the final results depend on the characteristics of the network  100 , it can be seen that constructing a subgraph according to other approaches (e.g., using the highest numbered node as a root node) can be less than optimal. 
     For example, the subgraph depicted in  FIG.  1 H  does not use any of the high bandwidth links (i.e., n 2 -n 1 , n 1 -n 3 , n 1 -n 4 , or n 4 -n 6 ) in the network  100 . Additionally, all traffic between the upper right area of the network  100  and the lower and left areas of the network  100  must pass through root node n 30  and multiple lower bandwidth links in the far upper left corner of the network  100 . Further, the path between some edge nodes can include as many as 9 hops (e.g., path between edge nodes n 22  and n 14 ). 
     An improved subgraph may be constructed using better connected and more powerful nodes as a root node. Different applications may favor different types of roots. For example, high bandwidth user traffic with many sources and sinks favors subgraphs premised on nodes with high bandwidth links. Heuristically, nodes with higher bandwidth links are also more capable and have lower latency than nodes with links of lower bandwidth. As such, nodes with higher bandwidth links tend to have more powerful hardware (e.g., to handle short inter-packet arrival times) and are likely more efficient in moving traffic from port to port. On the other hand, flooding graphs for lower bandwidth control traffic (e.g., link state information) favor nodes with many links in order to more rapidly disseminate control information to many other nodes. Thus, a better connected and more powerful node may depend on the presence of low-cost links and the number of links connected to that node. 
     Disclosed herein is a method of constructing a subgraph by prioritizing nodes for selection as a root node based on information local to that node. The method involves prioritizing nodes using a “node cost” for each node, where the node cost is calculated as the harmonic mean of link costs raised to a parametric power. The method further includes selecting as a root node the node based on the lowest node cost, which may be based on a weighting parameter to account for low-cost links and a quantity of connecting links. The method may be implemented without computing a global metric over an entire network/subgraph, the computation of which might require performing complex exponential or polynomial calculations of the number of nodes or total number of links in the network. Further, the method is applicable to routing applications, link-state flooding graphs, multicast/broadcast distribution trees, and related standards. These and other features are detailed below. 
       FIG.  2    illustrates a method  200  of selecting a root node for a to-be-constructed subgraph of a network such as the network  100  in  FIG.  1 A . The operations in the method  200  may be performed in the order shown, or in a different order. Further, two or more the operations of the method  200  may be performed concurrently instead of sequentially. In some implementations, the method  200  may be employed using a distributed tree calculation where every node (e.g., n 1 , n 2  . . . , and n 30 ) selects the same root node and computes the same subgraph of a network. In other implementations, the method  200  may be employed via one or more centralized controllers (e.g., a software-defined networking (SDN) controller) configured to select the root node, compute the subgraph, and provision all relevant network information to every node in the network. 
     At block  202 , the method  200  obtains costs of all links connected to nodes in a network, where it may be assumed that each node has one or more links to other nodes in the network. Using the network  100  in  FIG.  1 A , for example, a cost C of each link for a particular node may be denoted as C1, C2, . . . , Cm, where m is the quantity of links connected to that node. Thus, in  FIG.  1 A , the costs of links connected to node n 7  may be denoted as C1, C2, Cm, where Cm is C3 since node n 7  is connected to three links. In some embodiments, link costs may be based on bandwidth, where a cost C of a particular low or high bandwidth link may be set to a value divided by link speed, e.g., C=2*10 13 /bps. In other implementations, link costs may be based on one or more factors such as bandwidth, reliability, delay/latency, monetary cost per bit, or some combination thereof. 
     At block  204 , the method  200  selects a weighting parameter k to be used at block  206 . Additional details regarding the selection of weighting parameter k are discussed below with respect to Table 1. At block  206 , the method  200  calculates a node cost for each node n 1 , n 2 , . . . , and n 30  in the network. In an embodiment, the node cost may be set to a quotient produced by dividing the number of links connected to a particular node (e.g., n 1 , n 2 , . . . , or n 30 ) into the harmonic mean of the kth power of the costs of the links connected to the node. For example, the node cost may be derived mathematically via the formula below: 
     
       
         
           
             
               
                 
                   
                     Node 
                     ⁢ 
                         
                     Cost 
                   
                   = 
                   
                     
                       
                         HarmonicMean 
                         ( 
                         
                           
                             C 
                             ⁢ 
                             
                               1 
                               k 
                             
                           
                           , 
                           
                             C 
                             ⁢ 
                             
                               2 
                               k 
                             
                           
                           , 
                           
                             C 
                             ⁢ 
                             
                               3 
                               k 
                             
                           
                           , 
                           … 
                         
                             
                         ) 
                       
                       NumberOfLinks 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   
                     Equation 
                     ⁢ 
                         
                     1 
                   
                   ) 
                 
               
             
           
         
       
     
     The formula above may be rewritten using either of the formulas below, but each formula is otherwise the same as that above. Thus, unless stated otherwise, these three formulas are collectively referred to as Equation 1. 
     
       
         
           
             
               
                 Node 
                 ⁢ 
                     
                 Cost 
               
               = 
               
                 1 
                 
                   
                     1 
                     
                       C 
                       ⁢ 
                       
                         1 
                         k 
                       
                     
                   
                   + 
                   
                     1 
                     
                       C 
                       ⁢ 
                       
                         2 
                         k 
                       
                     
                   
                   + 
                   
                     1 
                     
                       C 
                       ⁢ 
                       
                         3 
                         k 
                       
                     
                   
                   + 
                   … 
                 
               
             
             , 
             or 
           
         
       
     
     
       
         
           
             
               Node 
               ⁢ 
                   
               Cost 
             
             = 
             
               1 
               
                 
                   C 
                   ⁢ 
                   
                     1 
                     
                       - 
                       k 
                     
                   
                 
                 + 
                 
                   C 
                   ⁢ 
                   
                     2 
                     
                       - 
                       k 
                     
                   
                 
                 + 
                 
                   C 
                   ⁢ 
                   
                     3 
                     
                       - 
                       k 
                     
                   
                 
                 + 
                 … 
               
             
           
         
       
     
     Note that that Equation 1 assumes that the link costs Cm are greater than zero. If the type of link costs being used permits a value of zero or a negative value, a constant may be added to assure positive costs. As an example using non-negative integer costs, assume a link cost is equal to zero, in which case link costs may be incremented by 1 before using Equation 1 to compute the Node Cost. 
     At block  208 , the method  200  selects a root node based on the node costs calculated in block  206 . In an embodiment, the node having the lowest node cost is selected as the root node. 
     Table 1 below includes a mapping between values of k and the effects of selecting different values of k. 
     
       
         
           
               
               
             
               
                 TABLE 1 
               
               
                   
               
               
                 Value of k 
                 Effect 
               
               
                   
               
             
            
               
                 k = 0 
                 The node cost is set to the order of the node, i.e., the 
               
               
                   
                 number of links connected to the node. 
               
               
                 0 &lt; k &lt; 1 
                 Cost is based on the number of links and on the low 
               
               
                   
                 cost of links connected to the node but, as k decreases, 
               
               
                   
                 the number of links is given greater weight and the cost 
               
               
                   
                 of links less weight. 
               
               
                 k = 1 
                 The number of links connected to the node and the low 
               
               
                   
                 cost of links are given equal weight. In the specific 
               
               
                   
                 case where cost is based on a reciprocal of the link 
               
               
                   
                 bandwidth, the node cost calculated with k = 1 will 
               
               
                   
                 order nodes by a reciprocal of the total bandwidth of 
               
               
                   
                 the links connected to a node. 
               
               
                 1 &lt; k 
                 Cost is based on the number of links and on the low 
               
               
                   
                 cost of links connected to the node but, as k increases, 
               
               
                   
                 the number of links is given less weight and the cost 
               
               
                   
                 of links greater weight. 
               
               
                   
               
            
           
         
       
     
     As can be seen from Table 1, setting k equal to zero has the effect of setting the node cost for a particular node equal to the reciprocal of the number of links connected to that node, while setting k equal to 1 has the effect of giving equal weight to the number of nodes connected to that particular node and the presence of low cost links. Generally speaking, this latter option may be a reasonable choice when little to no information is known about a to-be-constructed subgraph. Otherwise, setting k to a value greater or lesser than 1 may be more reasonable depending on the intended use. 
     For example, when constructing a general multicast traffic distribution tree or a spanning tree that carries a volume of unicast and multicast traffic, traffic to/from the various branch ends of the tree will tend to be concentrated in the middle of the tree. Thus, k may be set to a value greater than 1 in this case, as the cost of central links in the tree will affect most user traffic, so more weight should be given to the presence of low cost links. On the other hand, in applications with limited control traffic being flooded to nodes, having richer connectivity may be of higher priority (e.g., to get control information to more nodes faster). As such, k may be set to a value less than 1 such that more weight is given to selecting a root node having more links attached to the root node. 
       FIG.  3    depicts a chart  300  of Node Costs calculated for the nodes n 1 , n 2  . . . , n 30  in the network  100  of  FIG.  1 A . The node costs were calculated based on an example where the high bandwidth links (i.e., n 2 -n 1 , n 1 -n 3 , n 1 -n 4 , and n 4 -n 6 ) support speeds up to 100 megabits per seconds (mbps), while the other low bandwidth links support speeds up to 40 mbps. As shown in the chart  300 , the link cost of a high bandwidth link (Link HBW ) is set to 200,000, while the link cost for a low bandwidth link (Link LBW ) is set to 500,000. It should be understood that the high bandwidth link and/or the low bandwidth link have other costs in other implementations. To demonstrate the effect of selecting weight parameter k at block  204  of the method  200 , the node costs were calculated using different values of k as inputs to the formula disclosed above. It should be understood that other values of k may be used as input in other implementations. 
     The first column of the chart  300  specifies the node number corresponding to the nodes n 1 , n 2  . . . , n 30 , where Node Number  1  corresponds to n 1 , Node Number  2  corresponds to n 2 , and so forth. The second and third columns specify the number of high bandwidth and low bandwidth links attached to each node. For example, the chart  300  specifies that node n 1  is attached to three high bandwidth links (n 1 -n 2 , n 1 -n 3 , and n 1 -n 4 ) and three low bandwidth links (n 1 -n 25 , n 1 -n 24 , and n 1 -n 5 ), as depicted in  FIG.  1 A . The fourth, fifth, sixth, and seventh columns specify the Node Costs calculated using different values of k as inputs to Equation 1. 
     As previously mentioned, the method  200  may select a node having the lowest Node Cost as a root node. Thus, when k is set equal to 0.0, node n 9  may be selected as the root node because the corresponding Node Cost is 0.10, which is the lowest Node Cost calculated using Equation 1. Note that node n 9  has more links ( 10 ) attached to it than any other node. Thus, the Node Cost for node n 9  is consistent with Table 1 for k=0, which indicates that the Node Cost is set to the number of links connected to that node. The node having the second most links connected to it is node n 3 , which has a total of 9 links connected to it. Therefore, node n 3  has the second lowest Node Cost (0.11) when k is set to 0.0 as an input to Equation 1 for node n 3 . By comparison, nodes having only 1 connecting link (e.g., n 10  and n 14 ) have a Node Cost equal to 1.0, which is tenfold higher than the lowest Node Cost of node n 9 . 
     When k is set to 1.0 as an input to Equation 1, there are two nodes (n 1  and n 3 ) that may be selected as a root node because these nodes have the lowest Node Cost (47,619.05). In this case, a tiebreaking procedure may be implemented to select between nodes n 1  and n 3  as the root node. For example, node n 1  may be selected as the root node because n 1  is a lower numbered node than n 3 . Alternatively, node n 3  may be selected as the root node because n 3  is a higher numbered node than n 1 . As another example, node n 3  may be selected as the root node because n 3  is connected to more links than n 1 . As yet another example, node n 1  may be selected as the root node if the number of high bandwidth links is an important criterion. 
     Referring now  FIGS.  4 A- 4 D , a process of constructing a subgraph of a network  100  will now be described using similar principles discussed with respect to  FIGS.  1 B- 1 H , except a root node is selected using the method  200  disclosed herein. Additionally, this process will be described using an example in which k is set to 0.8 as an input to Equation 1. As shown in the chart  300 , node n 3  has the lowest Node Cost ( 3 , 594 . 64 ) when using k=0.8 as an input to Equation 1. Thus, the method  200  may select node n 3  as the root node in this case, as shown in  FIG.  4 A . This completes stage zero of the process. 
     The first stage of constructing the subgraph involves connecting the root node n 3  to one or more other nodes in the network  100  that are not yet part of the subgraph. In this example, the root node n 3  has 9 available connections. Thus, the root node n 3  may be connected to 9 layer one nodes to establish 8 low bandwidth links (n 3 -n 2 , n 3 - 12 , n 3 -n 13 , n 3 -n 9 , n 3 -n 8 , n 3 -n 7 , n 3 -n 6 , and n 3 -n 4 ) and 1 high bandwidth link (n 3 -n 1 ), as shown in  FIG.  4 B . 
     The second stage involves connecting layer one nodes n 2 ,  12 , n 13 , n 9 , n 8 , n 7 , n 6 , n 4 , and n 1  to one or more nodes, beginning with node n 13  because it is the highest numbered layer one node. Although node n 13  has one available connection to node n 9 , a link is not added from n 13  to n 9  because n 8  has already been connected to node n 3 . The second highest numbered layer one node is n 12 , but a link is not added for similar reasons. The third highest numbered layer one node is n 9 , which connects to layer two nodes n 14 , n 26 , n 27 , n 28 , n 29 , n 15 , and n 16 , but not nodes n 8  or n 13 . The process continues in a similar manner as previously described until the second stage is complete, the results of which are shown in  FIG.  4 C . 
       FIG.  4 D  depicts the results of the third and final stage of the process, where it can be seen that the constructed subgraph utilizes a high bandwidth link (n 3 -n 1 ) and has a shorter maximum path length between nodes than the previously described subgraph constructed according to other approaches. For example, there are no more than 6 hops between edge nodes in  FIG.  4 D  as compared to 10 hops between edge nodes in  FIG.  1 H . Additionally, the subgraph in  FIG.  4 D  was constructed in only three stages, meaning only 3 steps are necessary to reach every node in the network  100 . 
     Referring now  FIGS.  5 A-D , a process of constructing a subgraph of a network  100  will now be described using similar principles discussed with respect to  FIGS.  1 B- 1 H , except a root node is selected using the method  200  disclosed herein. Additionally, this process will be described using an example in which k is set to 1.25 as an input to Equation 1. As shown in the chart  300 , node n 1  has the lowest Node Cost ( 1 , 069 , 584 . 62 ) when using k=1.25 as an input to Equation 1. Thus, the method  200  may select node n 1  as the root node in this case, as shown in  FIG.  5 A . This completes stage zero of the process. 
     The first stage of constructing the subgraph involves connecting the root node n 3  to one or more other nodes in the network  100  that are not yet part of the subgraph. In this example, the root node n 1  has 6 available connections. Thus, the root node n 1  may be connected to 6 layer one nodes to establish 3 low bandwidth links (n 1 -n 25 , n 1 -n 24 , and n 1 -n 5 ) and 3 high bandwidth links (n 1 -n 2 , n 1 - 3 , and n 1 -n 4 ), as shown in  FIG.  5 B . 
     The second stage involves connecting layer one nodes n 25 ,  24 , n 5 , n 2 , n 3 , and n 4  to one or more nodes, beginning with node n 25  because it is the highest numbered layer one node and ending with layer one node n 2  because it is the lowest numbered layer one node.  FIG.  5 C  depicts the results of the second stage. 
     The third stage involves connecting layer two nodes to one or more nodes, beginning with node n 30  because it is the highest numbered layer two node and ending with node n 6  because it is the lowest numbered layer two node.  FIG.  5 D  depicts the results of this third and final stage of the process, where it can be seen that the constructed subgraph utilizes 4 high bandwidth links (n 1 -n 2 , n 1 -n 3 , n 1 - 4 , and n 4 -n 6 ) and has a shorter maximum path length between nodes than the previously described subgraph constructed according to other approaches. Accordingly, setting k to a value greater than 1 (e.g., k=1.25) may be appropriate for transmissions involving broadcast and multicast traffic. Like the subgraph in  FIG.  4 D , there are no more than 6 hops between edge nodes in  FIG.  5 D , and the subgraph was constructed in only three stages. 
     In some embodiments, costs of links in a network may be based on bandwidth, where the bandwidth of links from each node may be denoted as B1, B2, B3, and so forth. In such embodiments, selecting a node as the root node may involve selecting the node having the highest total bandwidth. The bandwidth for each node may be calculated as follows: Node Bandwidth=B1+B2+B3+ . . . . 
     In implementations where bandwidth may not be directly known or acquired, but the links are known to have costs C1, C2, C3, . . . , the bandwidth may be estimated based on link costs as follows: Node Bandwidth=1/C1+1/C2+1/C3+ . . . . 
     In such embodiments and implementations, a node having the highest node bandwidth in the network may be selected as the root node. If there are two or more nodes in the network with the same highest node bandwidth, the node with the highest node bandwidth and the most amount of connecting links may be selected as the root node. If there is still a tie, the node with the highest node bandwidth, the most amount of connecting links, and the highest (or lowest) node identifier (ID) or address may be selected as the root node. 
     In some implementations, costs between links can be asymmetric, where the cost from node one N 1  to node two N 2  is different from the cost from node two N 2  to node N 1 . In such implementations, the link cost used in the root selection method disclosed herein may be derived from the two different directional costs by computing the arithmetic, geometric, or harmonic mean of those cost or by selecting one in a systematic manner, such as selecting the highest or lowest of the two costs, or by any combination of these methods. 
     In some embodiments, the disclosed techniques may be employed to construct multiple distribution trees and/or flooding graphs for a particular network. That is, the disclosure is not limited to selecting a root node for a single tree/graph, as a network may comprise multiple trees/graphs at the same time, e.g., multiple trees/graphs may be in simultaneous use in a network. Therefore, multiple root nodes may be derived (e.g., using different values of k) to construct multiple trees/graphs, such that each tree/graph is tailored for certain applications (e.g., different types of traffic). For example, when a network is used for high bandwidth data transmissions, a root node may be derived to construct a tree/graph having low-cost links. As another example, when the network is used for transmitting control data with limited amounts of traffic, a root node may be derived to construct another tree/graph having many links (i.e., with less emphasis on link costs) to quickly distribute such control data. 
       FIG.  6    is a schematic diagram of a network device  600  according to an embodiment of the disclosure. The network device  600  is suitable for implementing the components described herein. The network device  600  comprises ingress ports  610  and receiver units (Rx)  620  for receiving data; a processor, logic unit, or central processing unit (CPU)  630  to process the data; transmitter units (Tx)  640  and egress ports  650  for transmitting the data; and a memory  660  for storing the data. The network device  600  may also comprise optical-to-electrical (OE) components and electrical-to-optical (EO) components coupled to the ingress ports  610 , the receiver units  620 , the transmitter units  640 , and the egress ports  650  for egress or ingress of optical or electrical signals. 
     In some embodiments, the network device  600  may connect to one or more bidirectional links. Moreover, at least one of the receiver units  620  may be integrated with at least one of the transmitter units  640 . Additionally or alternatively, at least one of the receiver units  620  may be replaced with at least one transceiver unit. Similarly, at least one of the transmitter units  640  may be replaced with at least one transceiver unit. Further, at least one of the ingress ports  610  may be integrated with at least one of the egress ports  650 . Additionally or alternatively, at least one of the ingress ports  620  may be replaced with at least one bi-direction port. Similarly, at least one of the egress ports  640  may be replaced with at least one bi-directional port. Accordingly, in such embodiments, the network device  600  may be configured to transmit and receive data over one or more bidirectional links via bi-directional ports  620  and/or  640 . 
     The processor  630  may be implemented by hardware and software. The processor  630  may be implemented as one or more CPU chips, cores (e.g., as a multi-core processor), field-programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and digital signal processors (DSPs). The processor  630  may be in communication with the ingress ports  610 , receiver units  620 , transmitter units  640 , egress ports  650 , and memory  660 . The processor  630  comprises a root node selection and subgraph construction module  670 . The module  670  may implement the disclosed embodiments described above. For instance, the module  670  may implement the method  200  of  FIG.  2    and processes discloses herein. The inclusion of the module  670  therefore provides a substantial improvement to the functionality of the device  600  and effects a transformation of the device  600  to a different state. Alternatively, the module  670  may be implemented as instructions stored in the memory  660  and executed by the processor  630 . 
     The memory  660  comprises one or more disks, tape drives, and solid-state drives and may be used as an over-flow data storage device, to store programs when such programs are selected for execution, and to store instructions and data that are read during program execution. The memory  660  may be volatile and non-volatile and may be read-only memory (ROM), random-access memory (RAM), ternary content-addressable memory (TCAM), and static random-access memory (SRAM). 
       FIG.  7    is a schematic diagram of an apparatus  700  for performing root node selection in a network according to various embodiments of the disclosure. The apparatus  700  comprises means  710  for obtaining link costs of links connecting a plurality of nodes in the network; means  720  for selecting a weighting parameter based at least partly on the link costs; means  730  for calculating node costs corresponding to each of the plurality of the nodes based on the link costs and the weighting parameter; and means  740  for selecting a node as the root node based on the node costs, wherein the root node is selected from the plurality of nodes. 
     In some embodiments, the network device  600  and/or the apparatus  700  may comprise a controller (e.g., a Software Defined Network (SDN) controller) in a network (e.g., network  100 ). In other embodiments, the network device  600  and/or the apparatus  700  may comprise other types of network components such as a node, router, or the like. 
     The disclosed embodiments may be a system, an apparatus, a method, and/or a computer program product at any possible technical detail level of integration. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present disclosure. The computer readable storage medium may be a tangible device that can retain and store instructions for use by an instruction execution device. 
     While several embodiments have been provided in the present disclosure, it should be understood that the disclosed systems and methods might be embodied in many other specific forms without departing from the spirit or scope of the present disclosure. The present examples are to be considered as illustrative and not restrictive, and the intention is not to be limited to the details given herein. For example, the various elements or components may be combined or integrated in another system or certain features may be omitted, or not implemented. 
     In addition, techniques, systems, subsystems, and methods described and illustrated in the various embodiments as discrete or separate may be combined or integrated with other systems, modules, techniques, or methods without departing from the scope of the present disclosure. Other items shown or discussed as coupled or directly coupled or communicating with each other may be indirectly coupled or communicating through some interface, device, or intermediate component whether electrically, mechanically, or otherwise. Other examples of changes, substitutions, and alterations are ascertainable by one skilled in the art and could be made without departing from the spirit and scope disclosed herein.