System and method for managing multicast group membership
First Claim
1. A computer-implemented method of adding a new node to a network multicast group, with a specified group membership status, wherein members of a corresponding routing tree route multicast messages among members of the group, the method comprising:
- selecting a minimum spanning tree of the network;
selecting the new node as the current node;
examining the routing tree membership statuses of nodes that are linked to the current node by links included in the minimum spanning tree;
until said examining is halted, selecting a peer node of the current node as the current node and repeating said examining;
halting the examining when a final node is examined if;
the final node is a Full member of the routing tree;
orthe final node is a SendOnly member of the routing tree and the specified group membership status of the new node is SendOnly; and
for each given node in the path from the new node to the final node, setting the routing tree membership status of the given node equal to the specified group membership status of the new node.
2 Assignments
0 Petitions
Accused Products
Abstract
A system and method for efficiently managing membership in a multicast communication group. The system may comprise any number of end nodes (e.g., channel adapters, network interface adapters) and routing nodes (e.g., switches), and the method may be implemented by a processor coupled to any node. Each node in a network may be a member of the multicast group and/or the multicast tree (MCT) that routes the group'"'"'s multicast communications. A node need not be a member of the group to be a member of the tree. Network links included in the multicast tree (MCT) are a subset of a network minimum spanning tree (MST). When a node is added to the group, the minimum spanning tree (MST) is searched from that node until a node within the multicast tree (MCT) is found. Each time a member is removed from the group, the multicast tree (MCT) is pruned to reduce unneeded communications.
13 Citations
23 Claims
-
1. A computer-implemented method of adding a new node to a network multicast group, with a specified group membership status, wherein members of a corresponding routing tree route multicast messages among members of the group, the method comprising:
-
selecting a minimum spanning tree of the network; selecting the new node as the current node; examining the routing tree membership statuses of nodes that are linked to the current node by links included in the minimum spanning tree; until said examining is halted, selecting a peer node of the current node as the current node and repeating said examining; halting the examining when a final node is examined if; the final node is a Full member of the routing tree;
orthe final node is a SendOnly member of the routing tree and the specified group membership status of the new node is SendOnly; and for each given node in the path from the new node to the final node, setting the routing tree membership status of the given node equal to the specified group membership status of the new node. - View Dependent Claims (2, 3, 4)
-
-
5. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of adding a new node to a network multicast group, with a specified group membership status, wherein members of a corresponding routing tree route multicast messages among members of the group, the method comprising:
-
selecting a minimum spanning tree of the network; selecting the new node as the current node; examining the routing tree membership statuses of nodes that are linked to the current node by links included in the minimum spanning tree; until said examining is halted, selecting a peer node of the current node as the current node and repeating said examining; halting the examining when a final node is examined if; the final node is a Full member of the routing tree;
orthe final node is a SendOnly member of the routing tree and the specified group membership status of the new node is SendOnly; and for each given node in the path from the new node to the final node, setting the routing tree membership status of the given node equal to the specified group membership status of the new node.
-
-
6. A computer-implemented method of adding a first node to a multicast group of network nodes, wherein members of a corresponding routing tree route multicast messages among members of the group, the method comprising:
-
(a) receiving a first request to include a first network node in a multicast group as one of a Full member and a SendOnly member; (b) setting a GroupStatus of the first node according to the first request, wherein said GroupStatus indicates a membership status in the multicast group; (c) selecting a minimum spanning tree of the network; (d) selecting the first node as the current node; (e) selecting a peer node of the current node, wherein a TreeStatus of the selected peer has not been examined since the first request was received, wherein said TreeStatus indicates a membership status in the routing tree; (f) performing one or more of the following examinations; (f1) determining if said TreeStatus of the selected peer is Full; (f2) determining if said TreeStatus of the selected peer is SendOnly and said GroupStatus of the current node is SendOnly; and (f3) determining if a network link coupling the current node to the selected peer is part of the selected minimum spanning tree; (g) repeating steps (e) to steps (g) until one of; (g1) at least one peer of the current node has been examined; and (g2) one of said step (f1) and said step (f2) determinations succeed; (h) if neither of said step (f1) and said step (f2) determinations has succeeded, setting a peer of the current node as the current node; (i) repeating steps (e) to steps (h) until one of; (i1) all nodes in the routing tree have been examined; and (i2) one of said step (f1) and said step (f2) determinations succeed; (j) for each given node in the minimum spanning tree, from the new node to the last peer examined, setting a TreeStatus of the given node equal to said GroupStatus of the new node. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of adding a first node to a multicast group of network nodes, wherein members of a corresponding routing tree route multicast messages among members of the group, the method comprising:
-
(a) receiving a first request to include a first network node in a multicast group as one of a Full member and a SendOnly member; (b) setting a GroupStatus of the first node according to the first request, wherein said GroupStatus indicates a membership status in the multicast group; (c) selecting a minimum spanning tree of the network; (d) selecting the first node as the current node; (e) selecting a peer node of the current node, wherein a TreeStatus of the selected peer has not been examined since the first request was received, wherein said TreeStatus indicates a membership status in the routing tree; (f) performing one or more of the following examinations; (f1) determining if said TreeStatus of the selected peer is Full; (f2) determining if said TreeStatus of the selected peer is SendOnly and said GroupStatus of the current node is SendOnly; and (f3) determining if a network link coupling the current node to the selected peer is part of the selected minimum spanning tree; (g) repeating steps (e) to steps (g) until one of; (g1) at least one peer of the current node has been examined; and (g2) one of said step (f1) and said step (f2) determinations succeed; (h) if at least one peer of the current node has been examined, setting a peer of the current node as the current node; (i) repeating steps (e) to steps (h) until one of; (i1) all nodes in the routing tree have been examined; and (i2) one of said step (f1) and said step (f2) determinations succeed; (j) for each given node in the minimum spanning tree, from the new node to the last peer examined, setting a TreeStatus of the given node equal to said GroupStatus of the new node.
-
-
12. A computer-implemented method of adding a new node to a network multicast group, with a specified group membership status, wherein members of a corresponding routing tree route multicast messages among members of the group, the method comprising:
-
identifying a minimum spanning tree of the network; selecting the new node as the current node; until a final node having a routing tree membership status greater than or equal to the specified group membership status of the new node is identified, repeating; examining the routing tree membership statuses of peer nodes of the current node; and selecting as current node a peer node of the current node that is coupled to the current node by a link included in the minimum spanning tree; and setting the routing tree membership status of each node in the minimum spanning tree, from the new node to the final node, to the specified group membership status of the new node. - View Dependent Claims (13)
-
-
14. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of adding a new node to a network multicast group, with a specified group membership status, wherein members of a corresponding routing tree route multicast messages among members of the group, the method comprising:
-
identifying a minimum spanning tree of the network; selecting the new node as the current node; until a final node having a routing tree membership status greater than or equal to the specified group membership status of the new node is identified, repeating; examining the routing tree membership statuses of peer nodes of the current node; and selecting as current node a peer node of the current node that is coupled to the current node by a link included in the minimum spanning tree; and setting the routing tree membership status of each node in the minimum spanning tree, from the new node to the final node, to the specified group membership status of the new node.
-
-
15. A computer-implemented method of removing a first node from a network multicast group, wherein members of a corresponding routing tree route multicast messages among members of the group, the method comprising:
-
queuing the first node in a queue; until the queue is empty, repeating the following, in order; (a) removing the most recently queued node to serve as the current node; (b) returning to step (a) if the group membership status of the current node is Full; (c) identifying a number of local ports of the current node that are on; (d) returning to step (a) if the number is greater than one; (e) if the number of local ports that are on is equal to zero; (e1) for each peer node having a local port to the current node on, turning off said peer node'"'"'s local port to the current node and adding said peer node to the queue; and (e2) setting the routing tree membership status of the current node to None; and (f) if the number of local ports that are on is equal to one; (f1) on a sole peer node coupled to the one local port, turning off the sole peer node'"'"'s local port to the current node if the sole peer'"'"'s local port to the current node is on; (f2) adding the sole peer node to the queue; (f3) if zero peer nodes have local ports to the current node on and the group membership status of the current node is None; turning off the one local port of the current node that is on; and setting the routing tree membership status of the current node to None; and (f4) otherwise, setting the routing tree membership status of the current node to SendOnly. - View Dependent Claims (16)
-
-
17. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of removing a first node from a network multicast group, wherein members of a corresponding routing tree route multicast messages among members of the group, the method comprising:
-
queuing the first node in a queue; until the queue is empty, repeating the following, in order; (a) removing the most recently queued node to serve as the current node; (b) returning to step (a) if the group membership status of the current node is Full; (c) identifying a number of local ports of the current node that are on; (d) returning to step (a) if the number is greater than one; (e) if the number of local ports that are on is equal to zero; (e1) for each peer node having a local port to the current node on, turning off said peer node'"'"'s local port to the current node and adding said peer node to the queue; and (e2) setting the routing tree membership status of the current node to None; and (f) if the number of local ports that are on is equal to one; (f1) on the sole peer node coupled to the one local port, turning off the sole peer node'"'"'s local port to the current node if the sole peer'"'"'s local port to the current node is on; (f2) adding the sole peer node to the queue; (f3) if zero peer nodes have local ports to the current node on and the group membership status of the current node is None; turning off the one local port of the current node that is on; and setting the routing tree membership status of the current node to None; and (f4) otherwise, setting the routing tree membership status of the current node to SendOnly.
-
-
18. A computer-implemented method of removing a first node from a multicast group of network nodes, wherein members of a corresponding routing tree route multicast messages among members of the group, the method comprising:
-
receiving a first request to remove a first network node from membership in a multicast group, wherein the first node was one of a Full member and a SendOnly member of the multicast group; setting a GroupStatus of the first node to one of None and SendOnly, wherein said GroupStatus indicates a membership status in the multicast group; queuing the first node in a queue; until the queue is empty, repeating; (a) dequeuing a node from the queue to be the current node; (b) determining if the GroupStatus of the current node is Full; (c)determining a number of local ports of the current node that are on; (d) if the number of local ports is equal to zero; (d1) for each peer of the current node with a local port to the current node turned on; (d1′
) setting the local port of the peer to off; and(d2″
) adding the peer to the queue; and(d2) setting a TreeStatus of the current node to None, wherein said TreeStatus indicates a membership status in the routing tree; and (e) if the number is equal to one; (e1) on the one peer coupled to the one local port of the current node, setting the local port of the one peer to the current node to off; (e2) adding the one peer to the queue; (e3) if the GroupStatus of the current node is None and zero peers of the current node have a local port to the current node on; (e3′
) turning off the one local port of the current node; and(e3″
) setting the TreeStatus of the current node to None; and(e4) otherwise, setting the TreeStatus of the current node to SendOnly. - View Dependent Claims (19)
-
-
20. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of removing a first node from a multicast group of network nodes, wherein members of a corresponding routing tree route multicast messages among members of the group, the method comprising:
-
receiving a first request to remove a first network node from membership in a multicast group, wherein the first node was one of a Full member and a SendOnly member of the multicast group; setting a GroupStatus of the first node to one of None and SendOnly, wherein said GroupStatus indicates a membership status in the multicast group; queuing the first node in a queue; until the queue is empty, repeating; (a) dequeuing a node from the queue to be the current node; (b) determining if the GroupStatus of the current node is Full; (c) determining a number of local ports of the current node that are on; (d) if the number is equal to zero; (d1) for each peer of the current node with a local port to the current node turned on; (d1′
) setting the local port of the peer to off; and(d1″
) adding the peer to the queue; and(d2) setting a TreeStatus of the current node to None, wherein said TreeStatus indicates a membership status in the routing tree; and (e) if the number is equal to one; (e1) on the one peer coupled to the one local port of the current node, setting the local port of the one peer to the current node to off; (e2) adding the one peer to the queue; (e3) if the GroupStatus of the current node is None and zero peers of the current node have a local port to the current node on; (e3′
) turning off the one local port of the current node; and(e3″
) setting the TreeStatus of the current node to None; and(e4) otherwise, setting the TreeStatus of the current node to SendOnly.
-
-
21. A system for managing membership in a multicast group and a corresponding routing tree for routing multicast messages within the multicast group, the system comprising:
-
a network node coupling the system to a network; a subnet administrator configured to receive requests to change the membership of the multicast group; a subnet manager configured to update network nodes'"'"' routing tables when the routing tree is modified in response to a change in membership of the multicast group; and a subnet management coordinator configured to; make a non-member into a Full or SendOnly member of the multicast group by; setting the group membership status of the non-member to the group membership status specified in a request that was received to make the non-member a member of the multicast group; identifying a minimum spanning tree of the network; selecting the non-member as the current node; until a final node having a routing tree membership status greater than or equal to the group membership status of the non-member is identified, repeating; examining the routing tree membership statuses of peer nodes of the current node; and selecting as current node a peer node of the current node that is coupled to the current node by a link included in the minimum spanning tree; setting the routing tree membership status of each node in the minimum spanning tree, from the non-member to the final node, to the specified group membership status of the new node; make a Full or SendOnly member into a non-member of the multicast group; and update the membership of the routing tree in response to a change in the membership of the multicast group. - View Dependent Claims (22, 23)
-
Specification