SYSTEMS AND METHODS FOR SCALABLE MULTICAST COMMUNICATION USING SELF-ROOTED FORWARDING TREES
First Claim
1. A method for multicasting a data packet through a network including a plurality of wireless links between nodes, comprising:
- maintaining at a first node a self-rooted forwarding tree which indicates the routing path from the first node to each node in the network;
identifying, at the first node, members of a multicast group to which the data packet is targeted;
determining, using the maintained self-rooted forwarding tree at the first node, metadata including a set of next-hop nodes to receive the data packet and a subset of the multicast group members to which each of such next-hop nodes is responsible for forwarding the data packet;
processing the metadata at the first node to reduce a number of bits necessary to convey the metadata over the network;
augmenting the data packet with the processed metadata at the first node; and
broadcasting, at the first node, the augmented data packet over the network.
2 Assignments
0 Petitions
Accused Products
Abstract
Systems and methods are disclosed herein for multicasting a data packet through a wireless network. The method includes a packet metadata which maintains a set of next-hop nodes on the routing path as well as the assigned destination nodes of the packet. In addition, each node maintains only a single self-rooted forwarding tree for determining the routing path. By using the metadata in conjunction with a single forwarding tree at each node, the method introduces a highly scalable alternative to multicast protocols based on link state routing source-based trees while substantially reducing the processor load. Furthermore, the method does not require a consistent view of the network topology, making it useful in mobile scenarios. Also included is a mechanism to minimize the packet metadata size for minimal impact to performance while supporting arbitrarily large multicast group sizes.
14 Citations
24 Claims
-
1. A method for multicasting a data packet through a network including a plurality of wireless links between nodes, comprising:
-
maintaining at a first node a self-rooted forwarding tree which indicates the routing path from the first node to each node in the network; identifying, at the first node, members of a multicast group to which the data packet is targeted; determining, using the maintained self-rooted forwarding tree at the first node, metadata including a set of next-hop nodes to receive the data packet and a subset of the multicast group members to which each of such next-hop nodes is responsible for forwarding the data packet; processing the metadata at the first node to reduce a number of bits necessary to convey the metadata over the network; augmenting the data packet with the processed metadata at the first node; and broadcasting, at the first node, the augmented data packet over the network. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A device for forwarding data throughout a network including a plurality of wireless links between nodes, the device comprising:
-
a communications device for receiving and transmitting data packets; a memory for storing information including a self-rooted forwarding tree, a list of multicast group memberships; and a processor configured to; maintain a self-rooted forwarding tree which indicates a routing path from a first node to a plurality of nodes in the network; determine, using the maintained forwarding tree, metadata including a set of next-hop nodes to receive a data packet and a subset of multicast group members to which each of such next-hop nodes is responsible for forwarding the data packet; process the determined metadata to reduce a number of bits necessary to convey the metadata over a network; augment the data packet with the processed metadata; and broadcast the augmented data packet over a network. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
Specification