Method And System For Flooding And Multicast Routing In An Ad Hoc Network
Abstract:
A wireless ad-hoc multicast network including a plurality of nodes, each of the nodes being designated with a dynamically determined role, a plurality of the nodes being designated with the role of super-node and the remaining nodes being designated with the role of ordinary-node, the super-node designated nodes forming a routing backbone of the network, the nodes forming at (east one multicast group, each of the nodes including a transmitter, a receiver, a local topology processor, a network topology processor, a backbone multicast processor and a local multicast processor, the local topology processor being coupled with the transmitter and with the receiver, the network topology processor being coupled with the transmitter, the receiver and with the local topology processor, the backbone multicast processor being coupled with the transmitter, the receiver and with the network topology processor, the local multicast processor being coupled with the transmitter, the receiver, the backbone multicast processor and with the local topology processor, the transmitter transmitting packets and messages over a wireless medium, the receiver receiving packets and messages over the wireless medium, the local topology processor maintaining a local topology database, and dynamically determining the role of the node, the network topology processor being operative when the role of the node is designated with the role of super-node, for maintaining a network topology database, and for establishing and terminating a dedicated backbone routing link with one-hop super-node neighbors, the backbone multicast processor being operative when the node is designated with the role of super-node, for maintaining a backbone multicast registration table, for transmitting backbone multicast update messages and for forwarding multicast packets, the local multicast processor maintaining a local multicast registration table and transmitting local multicast update messages to each one-hop ordinary-node neighbor only when the node is designated with the rote of super-node, the local multicast processor being further
operative for transmitting a multicast group subscription message to a selected one-hop super-node neighbor when the node is designated with the role of ordinary-node, and forwarding a multicast packet to a one-hop super-node neighbor serving one of the multicast groups associated with the multicast packet, each of the nodes attempting to communicate with a minimal number of one-hop super-node neighbors.
Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence
ADVANCED TECHNOLOGY CENTER
HOF HACARMEL
P.O. BOX 539
31053 HAIFA.
Inventors
1. TEMELMAN, AVIV,
12 HAGANIM ST
MOSHAV TSOFIT 44925.
2. KODEL, OLEG,
11/17 HA'ATZMAOUT ST., ASHDOD 77452
Specification
METHOD AND SYSTEM FOR FLOODING AND MULTICAST ROUTING IN AN AD-HOC NETWORK
Aviv TEMELMAN and Oleg KODEL
FIELD OF THE DISCLOSED TECHNIQUE
The disclosed technique relates to networks in general,'and to methods and system for multicast transmission, in particular.
BACKGROUND OF THE DISCLOSED TECHNIQUE
Ad-hoc communications networks are known in the art. An ad-hoc network is a network in which the participants in the network, known as nodes, communicate between each other directly or via other nodes (i.e., a node performs the operation of a router). In ad-hoc networks. Nodes may ieave or join the network, Nodes may further be mobile, thus, the topoiogy of the network frequently changes. Consequently, routes, for transmitting messages between nodes, frequently vary.
In a communication network, each node has a unique identification representation associated therewith. This unique identification representation enables each node in the network, to send a message to another node in the network.
Reference is now made to Figure 1, which is a schematic illustration of a simple exemplary ad-hoc network generally referenced 10 which is known in the art. Network 10 includes nodes 12, 14, 16, 18 and 20. Each node has a maximal transmit range represented by circles R12, R14, R16, R18 and R20. Maximal transmit range may be the maximal radio coverage range of a node. Each of lines 22, between the two nodes, indicates that the nodes communicate with each other. A one-hop neighbor of a node is another node with which the node communicates
directly. A two-hop neighbor of a node is another node with which the node communicates via a third node. For example, Nodes 14, 16 and 18 are the one-hop neighbors of node 12, since they communicate directly with node 12. Node 20 is the two-hop neighbor of node 12 since node 20 communicates with node 12 via node 18.
In a communications network, a node may be required to forwards a packet to all of the nodes participating in the network (i.e., broadcast the message to all the nodes in a network wherein not all the nodes communicate directly with each other). The term "packet" refers hereinafter to a packet information transit through the network. A packet, destined to all of the nodes In the network, will be referred to hereinafter as a flood message. For example, with reference to Figure 1, node 14 is the source of a flood packet. Node 14 forwards the packet to node 12. Node 12 forwards the message to nodes 16 and 18 and node 18 forwards the packet to node 20.
In a communications network, a multiplicity of nodes may form a multicast group. A multicast group is a group of nodes, receiving packet associated only with that group. Each multicast group has a unique identification representation associated therewith. This unique multicast Identification representation enables a node in the network, to send a packet or packets, destine to other nodes, which are members of that multicast group. A packet, destinedjo a multicast group, will be referred to hereinafter as multicast packet. For example, with reference to Figure 1, nodes 20, 16 and 14 form a multicast group. Node 18, requires to transmit a multicast packet to all the nodes in the multicast group (i.e., node 16, node 14 and node 20). Therefore node 18 forwards the multicast message to node 20 and node 12. Node 12 forwards the message to node 14 and node 16. It is noted that, as the above example Illustrates, that a node that is not a member of a multicast group may send a message to the multicast group.
European patent application publication EP1,324,532A2 to Liu etal., entitled "Method and Apparatus for on Demand Multicast and Unicast" is directed to a technique wherein nodes, in a communications network are arrange in clusters. A node, in a cluster, is selected as a cluster head. The cluster head selects another cluster head as gateway. Each node in the network transmits a beacon status message to one-hop neighbors. These beacon status messages Include a unique identification code of the transmitting node, the one-hop neighbors of the node and the multicast groups the node wishes to join. Consequently, each node maintains a local database of one-hop neighbors and of two-hop neighbors. A cluster head stores a cluster head routing table and a gateway stores a gateway routing table.
A message source node may determine the next hop in a route of a message whose destination is a node, at most two-hop from the node, according to the local database. If a node in a cluster cannot locate a destination node, the node forwards the message to the cluster-head. A cluster head attempts to locate the destination node in the local database of the cluster head. If the destination node Is not in the local database of the cluster head the cluster head attempts to locate the destination node in a routing table stored in the cluster head. If the destination node is not in the routing table stored in the cluster head routing table, the cluster head forwards the message to a cluster head neighbor one-hop closer to the selected gateway. If eventually the message reaches the gateway and the gateway cannot find the destination node in the gateway routing table, the gateway attempts to discover a route to the destination node.
In the patent to Liu et al., transmitting a multicast message from a singly message source to a multiplicity of destinations is achieved by flooding the network with a controlled flood message. A controlled flood message a message that is flooded only by nodes that can potentially transmit the message to nodes that did not receive the message from
another node. The decision of a node to re-transmit a flood message is based on the topology information stored in the node.
The publication to Jaikaeo et al, entitled "Adaptive Backbone-Based Multicast for Ad Hoc Networks", directs to an adaptive multicast mechanism for ad hoc networks. The multicast mechanism, adopts a two-tier architecture, with an adaptive backbone infrastructure. Each node, once deployed, sets itself as a core (or backbone) node and broadcasts hello messages. Thus each node discovers the neighbors thereof and updates the neighbors table stored therein. Initially, each node sets itself as a core node. Each node decides whether it should remain a core node, or become a child of an existing cored node, according to a metric, dubbed height, such as power, link failure frequency or connectivity. The node with the highest height remains the core node of all the neighbors thereof. The other nodes select the node with the highest height as their parent node. Each core node constructs a core forwarding table with entries of nodes who can deliver a message to other core nodes.
In the publication to Jaikaeo et al, each node receives multicast packets from core nodes or multicast forwarders that forward a multicast message from and toward the core. A core node transmits the multicast message to all the other core nodes in the network. The core nodes forward the multicast packet to the multicast members.
U.S. patent 6,791,949, to Ryu et al, entitled "Network Protocol for Wireless Ad Hoc Networks", directs to a wireless ad hoc network wherein each node in the network is associated with a category or state. Backbone nodes are designated "black nodes". Nodes that are not part of the backbone but can communicate directly with one or more black nodes are labeled "green nodes". "White nodes" are nodes that can transmit and receive packets but do not reliably communicate with a black node. The network backbone represents a packet forwarding infrastructure, for exchange of packets between non-neighboring nodes. Each node
periodically transmits a signaling packet including a protocol support records such as transmitter status record. The transmitter status record includes the number of black neighbor nodes, the number of non-black neighbor nodes and next hop information record. Network backbone creation begins with a SELECTION process which is performed only by white nodes. The SELECTION process identifies an initial set of network backbone nodes. Once a white node communicates with a backbone node it becomes a green node. An EXPANSION process is also performed by category white nodes. EXPANSION is the process by which a white node "asks' a green neighbor to become a network backbone node. This will cause the category white node to become category green, since it now has a category black neighbor, Collectively, the SELECTION and EXPANSION processes, result in a network consisting of green and black nodes with varying degrees of backbone connectivity.
Each of the category black node maintains a multicast routing table consisting of a group address and a list of local group members. Each local group member is a direct neighbor of the black node and has joined the group or the closest upstream black node. Each category black node further maintains a list of downstream black nodes. A node, joining a new multicast group, sends a join request to a one-hop black node neighbor. The receiving black node registers the transmitting nodes as a multicast group member. The one-hop black node neighbor transmits the join request to all the black nodes. Thus, the forwarding black nodes become up stream nodes of the receiving black node. When another node request to join the multicast group, that node transmits a request to a one-hop hop black neighbor. The one-hop black neighbor transmits the request only to the up stream one-hop neighbor. Thus, the black node, receiving the request, becomes a down stream one-hop black neighbor of the transmitting black node. A black node with both up stream and down stream black neighbors, does not forward multicast join requests. Thus a
multicast tree is established. Multicast packets are forwarded according to the pertinent tree.
SUMMARY OF THE PRESENT DISCLOSED TECHNIQUE
It Is an object of the disclosed technique to provide a novel method and system for flooding and multicast routing in an ad-hoc network. ]n accordance with the disclosed technique, there is thus provided a wireless ad-hoc multicast network. The wireless ad-hoc multicast network includes a plurality of nodes. Each of the nodes is designated with a dynamically determined role. A plurality of the nodes are designated with the role of super-node and the remaining nodes are designated with the role of ordinary-node. The super-node designated nodes form a routing backbone of the network. The nodes form one or more multicast groups. Each of the nodes includes a transmitter, a receiver, a local topology processor, a network topology processor, a backbone multicast processor and a local multicast processor.
The local topology processor is coupled with the transmitter and with the receiver. The network topology processor is coupled with the transmitter, the receiver and with the local topology processor. The backbone multicast processor is coupled with the transmitter, the receiver and with the network topology processor. The local multicast processor is coupled with the transmitter, the receiver, the backbone multicast processor and with the local topology processor.
The transmitter transmits packets and messages over a wireless medium. The receiver receives packets and messages over the wireless medium. The local topology processor maintains a local topology database, and dynamically determines the role of the node. The network topology processor is operative when the role of the node is designated with the role of super-node. The network topology processor maintains a network topology database, and establishes and terminates a dedicated backbone routing link with one-hop super-node neighbors. The backbone multicast processor is operative when the node is designated with the role of super-node. The backbone multicast processor maintains a backbone multicast registration table, transmits backbone multicast update
messages and forwards multicast packets. The local multicast processor maintains a local multicast registration table, and transmits local multicast update messages to each one-hop ordinary-node neighbor only when the node is designated with the role of super-node.
The local multicast processor further transmits a multicast group subscription message to a selected one-hop super-node neighbor, when the node is designated with the role of ordinary-node, and forwards a multicast packet to a one-hop super-node neighbor, serving one of the multicast groups associated with the multicast packet. Each of the nodes attempts to communicate with a minimal number of one-hop super-node neighbors.
In accordance with another aspect of the disclosed technique, there is thus provided a method for updating stored multicast information in each of the nodes in a wireless ad-hoc multicast network. The network includes a plurality of nodes. Each of the nodes is designated with a dynamically determined role. A plurality of the nodes are designated with the role of a super-node and the remaining nodes are designated with the role of ordinary-nodes. The super-node designated nodes form a routing backbone of the network. The nodes form one or more multicast groups. Each of the nodes stores multicast information. The method includes the procedures of detecting an event in the one-hop neighborhood of a super-node designated node, transmitting a local multicast update message, determining if the subscribing subscriber is the first subscriber with the super-node designated node to one of the multicast groups. The method further includes the procedures of determining if the un-subscribing subscriber is the last remaining subscriber to one of the multicast groups, and updating a backbone multicast registration table.
The detected event is either an ordinary-node designated node joining the one-hop neighborhood, an ordinary-node designated node leaving the one-hop neighborhood, a subscriber subscribing with the super-node designated node to one of the multicast groups, or a
subscriber un-subscribing with the super-node designated node to either the same one or another one of the multicast groups. The local multicast update message is transmitted when the event is detected as an ordinary-node designated node joining the one-hop neighborhood or the super-node designated node. The subscriber is detected as the first subscriber with the super-node designated node to one of the multicast groups, when the event is detected as the subscriber subscribing with the multicast group. The un-subscribing subscnber is determined as the last remaining subscriber to one of the multicast groups, when the event is detected as the subscriber un-subscribing to either the same or another one of the multicast groups. The backbone multicast registration table is updated when the subscriber is either the last subscriber or the first subscriber, with the super-node designated node, to the multicast group
In accordance with a further aspect of the disclosed technique, there is thus provided a method for selecting a node for multicast subscription by another node in a wireless ad-hoc multicast network. The wireless ad-hoc multicast network includes a plurality of nodes. Each of the nodes is designated with a dynamically determined role. A plurality of the nodes are designated with the role of a super-node and the remaining nodes are designated with the role of ordinary-nodes. The super-node designated nodes form a routing backbone of the network. The nodes form one or more multicast groups. The node which selects a node for subscription, is an ordinary-node and the selected node is a super-node.
The method includes the procedures of determining a multicast group for subscription, detecting a one-hop super-node designated node neighbor, of the ordinary-node, serving the determined multicast group, and detecting the one-hop super-node designated node neighbors, of the ordinary-node. The method further includes the procedures of selecting one or more of the detected one-hop super-node designated node neighbors for multicast subscription, and transmitting a multicast subscription request message io the selected super-node designated
node neighbor. The one-hop super-node designated node neighbors, of the ordinary-node is detected when a one-hop super-node designated node neighbor, serving the determined multicast group. Is not detected.
In accordance with another aspect of the disclosed technique, there is thus provided a method for determining the next hop of a flood packet in a wireless ad-hoc multicast network. The wireless ad-hoc multicast network Includes a plurality of nodes. Each of the nodes Is designated with a dynamically determined role, a plurality of the nodes are designated with the role of a super-node and the remaining nodes are designated with the role of ordinary-nodes. The super-nodes designated node form a routing backbone of the network. The nodes form one or more multicast groups. The next hops are routing backbone next hops.
The method includes the procedures of receiving a flood packet or a flood message, producing a transmission list, producing an updated trailer list and transmitting the flood packet or the flood message to the one-hop super-node neighbors listed in the transmission list. The received flood packet or flood message includes a received trailer list. The transmitted flood packet or flood message includes the updated trailer list.
BRIEF DESCRIPTION OF THE DRAWINGS
The disclosed technique will be understood and appreciated more fully from the following detailed description taken in conjunction with the drawings in which:
Figure 1, which is a schematic illustration of a simple exemplary ad-hoc network generally referenced 10 which is known in the art;
Figures 2A, 2B, 20 and 2D which are a schematic illustration of an exemplary network generally referenced 100, in accordance with an embodiment of the disclosed technique;
Figure 3, which is a schematic illustration of a system, generally referenced 160, constructed and operative in accordance with another embodiment of the disclosed technique;
Figure 4, which is a schematic illustration of a method for operating a node in a wireless and cluster-less network, operative in accordance with a further embodiment of the disclosed technique;
Figure 5, which \B a schematic illustration of a method for updating the backbone multicast table, by a super-node, when an event in the one hop neighborhood of that super-node occurs, in accordance with another embodiment of the disclosed technique;
Figure 6, which is a schematic illustration of a method for prioritizing and selecting a super-node when an ordinary-node attempts to subscribe to a multicast group, operative in accordance with a further embodiment of the disclosed technique;
Figures 7A, 7B and 7C which are schematic illustrations of an exemplary network backbone, generally referenced 320, in accordance with another embodiment of the disclosed technique; and
Figure 8, which is a schematic illustration of a method for determining the next hops of a flood packet in the backbone of the network, according to a further embodiment of the disclosed technique.
DETAILED DESCRIPTION OF THE EMBODIMENTS
The disclosed technique overcomes the disadvantages of the prior art by providing a cluster-less communication network and a method and a system therefore, which enables multicast transmission between mobile nodes. In the network according to the disclosed technique some nodes, designated as super-nodes, form the routing backbone of the network and communicate between one another via a dedicated backbone routing link.
In a communication system according to the disclosed technique, each node in the network is a router {i.e., a node is capable of forwarding packets of information toward the destination of that packet). Each node may be coupled directly with one or more hosts. Each node may further be coupled with external routers (i.e., routers associated with external networks). These external routers provide routing services to the external networks. Each node provides routing services to hosts coupled directly to the node, or to the external routers coupled therewith. Each node transmits a node status message, which is received by one-hop neighbors of the node. Node status messages will be referred to hereinafter as "hello messages". A hello message includes the identification representation (e.g., MAC ID number) of the transmitting node, the role of the node (i.e., ordinary-node or super-node), and a list of the one-hop neighbors of the transmitting node and the role of each of these one-hop neighbors. Accordingly, each node receives hello messages from one-hop neighbors and these hello messages contain information relating to the two-hop neighbors of the receiving node (i.e., nodes which can be wirelessly accessed via the one-hop neighbor nodes). Consequently, a node acquires information about the identification and role of one-hop neighbors and two-hop neighbors thereof, and forms a local topology database based on that information. It is noted that the term message or messages refers to messages containing information
1
relating to the construction and maintenance of the network. These messages are transmitted between nodes. It is further noted that the term "packet" herein refers to packets of information transit through the network. These packets are forwarded between nodes participating in the network.
Each ordinary-node (i.e., a node that is not a super node) forms a two-hop local routing table. This local routing table includes Information relating to every node, which is no more than two-hops away (i.e., one-hop neighbors and two-hop neighbors). The local routing table includes entries of the one-hop neighbors and of the hosts, and external routers coupling external networks, coupled with the one-hop neighbor, to which packets are forwarded. Information associated with the routing table entries may include the unique network identification representation (e.g., IP address) assigned to each node, to each host or to each external router coupling an external network. The local routing table further includes entries of the two-hop neighbors, with the respective one-hop neighbors (i.e., there may be more than one one-hop neighbor which can relay packets from a specific source node to a specific destination node), and their unique routing identification representations. It is noted that the local routing table may further include entries of hosts and of routers coupling external networks, coupled with a two-hop neighbor. The routing identification representations, of the nodes in the local routing table, are derived from the hello messages sent by each node, The routing identification representations are derived from the node identification representation since there is a one-to-one correspondence between them. The routing identification representations of the hosts, coupled with the node, are obtained according to a routing protocol (e.g., RIP).
A super-node is a node with capabilities to direct packets to every node in the network, or hosts couple with the node (i.e., directly or via an external router coupling an external network). A super-node, stores a local routing table, including entries of the one-hop and two-hop
neighbors (i.e. entries to one-hop and two-hop ordinary-node neighbors, one-hop and two-hop super-node neighbors, and hosts and routers coupling external networks, coupled with one-hop neighbors). Each entry includes information of the unique network identification representation assigned to each node, to each host, or to each external router of an external network coupled with the one-hop ordinary-node neighbor. A super-node, further stores a network routing table. This network routing table includes entries to all the nodes, the hosts and external networks, with the respective one-hop super-node neighbor or neighbors, to which the super-node forwards a packet destined to these nodes, hosts, or netwof1 's still met, if that potentially redundant super-node was demoted to an ordinary-node, for all of the one-hop ordinary-node neighbors;
if the role of that super-node changes to ordinary-node, that
node will not exhibit an articulation node status.
When self redundancy is detected, then, the method proceeds to procedure 208. When self redundancy is not detected, then, the method returns to procedure 214. With reference to Figure 3, local topology processor 170 detects self-redundancy of the node and changes the role of the receiving node to an ordinary-node when self-redundancy Is detected.
In procedure 208, the role of the node is changed to an ordinary-node and dedicated backbone routing links, with one-hop super-node neighbors, are terminated. With reference to Figure 3, local topology processor 170 changes the role of the node to ordinary-node and terminates dedicated backbone routing links with one-hop super-node neighbors. After the completion of procedure 208, the method proceeds to procedures 214.
In procedure 210, self-articulation status is detected. Self articulation status is determined according to either one of the following criteria:
• A node that at least one of the one-hop super-node neighbors thereof, are not vertices of a continuous graph (i.e., communicate with each other according to the local topology database);
• Not all the one-hop ordinary-node neighbors are one-hop away from the continuous graph of super-nodes;
When the self-articulation status of the node is positive, then, the method proceeds to procedure 212. When the self-articulation status of the node is negative, then, the method proceeds to procedure 214. With reference to Figure 3, local topology processor 170 determines the self-articulation status of the node.
in procedure 212, the role of the node is changed to a super-node and dedicated backbone routing links are established with one-hop super-node neighbors. With reference to Figure 3, local topology processor 170 changes the role of the node to super-node and establishes dedicated backbone routing links with one-hop super-node neighbors. After the completion of procedure 212, the method proceeds to procedures 214.
In procedure 214, the number of one-hop super-node neighbors of the current node is identified. Each ordinary-node should have a minimal one-hop local super-node number, X\< <^^ one-hop super-node neighbors. Each super-node should have a minimal one-hop backbone super-node number, Xi- of one-hop super-node neighbors. When the number of one-hop super-node neighbors, is at least X, when the node is an ordinary-node, or at (east X^ when the node is a super-node, then, the
method returns to procedure 200. When the number of one-hop super-node neighbors is either smaller than X, when the node is an
ordinary-node or smaller than X2 ^^^^ the node is a super-node, then, the method proceeds to procedure 216. With reference to Figure 3, local topology processor 170 identifies the number of one-hop super-node number of the receiving node and determines if the minimal one-hop local super-node number or the minimal one-hop backbone super-node number is met.
In procedure 216, a candidate for super-node designation, is selected. When the role of the node is a super-node, the node selects a one-hop ordinary-node neighbor for super-node designation. When the role of the node is ordinary-node, the node may select itself for super-node designation as well. Furthermore, when a super-node receives a super-node designation message, from another node, that super-node elects itself for super-node designation. A node (i.e., a super-node or an
ordinary-node) may designate it self or another ordinary-node as a super-node according to, a static priority criterion {e.g., identification representation), a dynamic criterion, or a combination thereof. According to the static priority criterion the system selects the node with the highest static priority (e.g., lowest or the highest identification representation). According to the dynamic criteria, the node calculates a certain value for each node. The node designates the node with the highest value as a super-node. For example, the value may be the sum of the weighted connectivity (i.e. the measured power of received transmissions) and the weighted coverage of the node. When the role of the node is ordinary-node and the node selected Itself for super-node designation, then, the method proceeds to procedure 220. When the node (i.e., either an ordinary-node or a super-node) selected a one-hop ordinary-node neighbor for super-node designation, the method proceeds to procedure 218. With reference to Figure 3, local topology processor 170 selects an ordinary-node for super-node designation.
In procedure 218, a super-node designation message is transmitted to the selected ordinary-node. With reference to Figure 3, local topology processor 170 transmits via transmitter 174 a super-node designation message to the selected ordinary-node. After the completion of procedure 218, the method returns to procedure 200.
In procedure 220, the role of the node is changed to a super-node and dedicated backbone routing links, with one-hop super-node neighbors, are established. With reference to Figure 3, focal topology processor 1/0 changes the role of the node to super-node and establishes dedicated backbone routing links with one-hop super-node neighbors. After the completion of procedure 220, the method proceeds to procedures 200.
In the network according to the disclosed technique, each super-node maintains a coreless minimal shared spanning tree for each multicast group in the network. This minimal shared spanning tree should
Include at least all of the super-nodes, which serve the respective multicast group. Reference is now made back to Figure 2A, and to Figures 2B, 2C and 2D, which are a schematic illustration of exemplary network 100. As mentioned above, with reference to Figure 2A, ordinary-nodes 104, 108, 120 and 122 and super-node 110 are all members of the same multicast group. An exemplary minimum spanning tree of this multicast group includes super-nodes 102,110 and 116 {Figure 2B). However, in Figure 2C, dedicated backbone routing link 132, between super-node 110 and super-node 102 is lost. Consequently, node 108 changed Its role to a super-node (i.e., according to the articulation node status criterion, as mentioned above, in conjunction with Figure 4). Line 144 represents the dedicated backbone routing link between super-nodes 108 and 110. Line 146 represents the dedicated backbone routing link between super-nodes 108 and 112. Line 148 represents the dedicated backbone routing link between super-nodes 108 and 106. Line 150 represents the dedicated backbone routing link between super-nodes 108 and 102. According to these changes in the topology of the network, the minimum spanning tree of the multicast group including ordinary-nodes 104,120 and 122, and super-nodes 108 and 110 changed. Figure 2D illustrates an exemplary minimum spanning tree of this multicast group, after dedicated back routing link 132 (Figure 1A) was lost. This exemplary minimum spanning tree includes super-nodes 102, 108, 110, 116.
As mentioned above, according to the disclosed technique, a super-node floods the backbone with backbone multicast update messages. A super-node transmits these backbone multicast update messages every configurable time period or due to an event in the one-hop neighborhood thereof. These backbone multicast update messages include the multicast groups that that super-node serves and changes that occurred in the backbone multicast registration table.
Reference is now made to Figure 5, which is a schematic illustration of a method for updating the backbone multicast table, by a super-node, when an event in the one hop neighborhood of that super-node occurs, in accordance with another embodiment of the disclosed technique. In procedure 250, an event in the one-hop neighborhood of the super-node is detected. , As mentioned above, this event refers to an ordinary node joining or leaving the one-hop neighborhood of a super-node. The event further refers to an ordinary-node, or a host, subscribing or un-subscribing to or from a multicast group, that the super-node serves. When the detected event is an ordinary-node joining the one-hop neighborhood of the super-node, the method proceeds to procedures 252. When the detected event is an one-hop ordinary-node neighbor or a host, coupled with the super-node, subscribing to a multicast group that the super-node serves, then, the method proceeds to procedure 256. When the detected event is a one-hop ordinary-node neighbor leaving the one-hop neighborhood of the super-node, or a one-hop ordinary-node neighbor of the super-node, or a host coupled with the super-node, un-subscribing to a multicast group that the super-node serves, then, the method proceeds to procedure 254. With reference to Figure 3, Local topology processor 168 determines when an ordinary-node joins or leaves the one-hop neighborhood of the super-node. Local multicast processor 166 determines when an ordinary-node or a host coupled with the super-node subscribes or un-subscribes to a multicast group that the super-node serves.
In procedure 252, a local multicast update message is transmitted to the joining one-hop ordinary-node neighbor. This local multicast update message includes a list of all the multicast groups in the network, and which multicast group the super-node serves. With reference to Figure 3, local multicast processor 166 transmits via transmitter 171 a local multicast update message. After procedure 252 the method repeats from procedure 250.
In procedure 254, whether the subscriber is the last subscriber with the super-node to the pertinent multicast group, is determined. The event of an ordinary-node leaving the one-hop neighborhood of the super-node is similar to the ordinary-node un-subscrifaing to the pertinent multicast groups (i.e., those multicast groups that that ordinary-node is subscribed thereto). When the subscriber is not the last subscriber with the super-node to the pertinent multicast group, then, the method repeats from procedure 250. When the subscriber is the last subscriber with the super-node to the pertinent multicast group, then, the method proceeds to procedure 258. With reference to Figure 3, local multicast processor 166 determines if the subscriber is the last subscriber to the pertinent multicast group.
In procedure 256, whether the subscriber is the first subscriber with the super-node to the selected multicast group, is determined. The subscriber may be a one-hop ordinary-node neighbor requesting to subscribe to a selected multicast group. The subscriber may further be a host, coupled with the super-node, requesting to subscribe to a selected multicast group. When the subscriber is not the first subscriber with the super-node to the selected multicast group, then, the method repeats from procedure 250. When the subscriber is the first subscriber with the super-node to the selected multicast group, then, the method proceeds to procedure 258. With reference to Figure 3, local multicast processor 166 determines if the subscriber is the first subscriber to a selected multicast group.
In procedure 258, the backbone multicast registration table Is updated. With reference to Figure 3, backbone multicast processor 164 updates the backbone multicast update table.
In procedure 260, the backbone of the network is flooded with a backbone multicast update message. With reference to Figure 3, backbone multicast processor 164 floods the backbone with a backbone multicast update message via backbone flooding processor 162 and
TS
transmitter 174. After procedure 260 the method repeats from procedure 250,
In the networ[< according to the disclosed technique, a super-node may join or leave the one-hop neighborhood of an ordinary-node subscribed to a multicast group that that super-node serves. Consequently, the ordinary-node is required to update the local multicast table, stored in that ordinary-node. When an ordinary-node detects that a super-node is a new one-hop neighbor, the ordinary-node creates an empty entry of the joining super-node in the local multicast registration table stored therein, updates that entry with the local multicast update message received from the joining super-node. When the ordinary-nodes detects that a super-node, serving a pertinent multicast group, is no longer a one-hop neighbor, the ordinary-node deletes the entry associated with that leaving super-node, from the local multicast registration table stored therein . The node attempts to subscribe to the multicast group that the leaving super-node served, via another super-node, serving the same multicast group. An ordinary-node, attempting to subscribe to a multicast group, prioritizes the one-hop super-node neighbors thereof, selects the super-node with the highest priority, and transmits a multicast group subscription request to the selected super-node.
Reference is now made to Figure 6, which is a schematic Illustration of a method for prioritizing and selecting a super-node when an ordinary-node attempts to subscribe to a multicast group, operative in accordance with a further embodiment of the disclosed technique. In procedure 280, a multicast group is determined for subscription. A host coupled with an ordinary-node may require multicast services. When an ordinary-node receives such a request, that ordinary-node determines which multicast group that ordinary-node should subscribe with. With reference to Figure 3, local multicast processor 166 determines a multicast group for subscribing.
in procedure 282, one-hop super-node neighbors, subscribed to the determined multicast group are detected. A super-node is subscribed to a multicast group when that super-node provides multicast services to hosts coupled therewith. A super-node is also a subscriber to a multicast group when that super-node provides multicast services to one-hop ordinary-node neighbors. Therefore, when an ordinary-node receives a request to receive multicast services from a host coupled therewith, that ordinary-node detects the one-hop super-node neighbors subscribed to that same multicast group. The ordinary-node detects the one-hop super-node neighbors, subscribed to the determined multicast group, according to the local multicast registration table stored therein. When a one-hop super-node neighbor, subscribed to the determined multicast group, is detected, then, the method proceeds to procedure 286. When a one-hop super-node neighbor, subscribed to the determined multicast group, is not detected, then, the method proceeds to procedure 284. With reference to Figure 3, local multicast processor 166 detects the one-hop super-node neighbors that are subscribed to the determined multicast group.
In procedure 284, the one-hop super-node neighbors of the ordinary-node are detected. These one-hop super-node neighbors are not subscribed, and do not serve the determined multicast group. With reference to Figure 3, multicast processor 166 detects one-hop super-node neighbors.
In procedure 286, at least one of the detected one-hop super-node neighbors is selected for multicast subscription. With reference to Figure 3, multicast processor 166 selects at least one-hop super-node neighbor for multicast subscription.
(n procedure 288, a multicast group subscription request message is transmitted to the selected one-hop super-node neighbor. With reference to Figure 3, local multicast processor 166 transmits via
transmitter 174 a multicast group subscription request message to the selected one-hop super-node neighbor.
According to the disclosed technique, super-nodes flood the backbone of the network with network topology update messages and with messages including updates of the backbone multicast registration table. Furthermore, each ordinary-node is capable of flooding the network with a packet (i.e., that packet is directed to be received by every node in the network). However, when a message or a packet is flood through the network, each node may receive that message or packet a multiplicity of times (i.e., there is a redundancy of flood packet or flood message transmission). Therefore, in order to reduce that redundancy and reduce the bandwidth required to transmit flood messages, each flood packet includes a trailer list. This trailer list includes entries of the identification representations of at least some of the super-nodes that that flood message was sent to. The trailer list is managed as a First-ln-Firsf-Out (FIFO) buffer (i.e., a buffer wherein the entry which was the first to enter the buffer, is also the first to exit, when the buffer overspills). A super-node, receiving a flood packet, produces an updated trailer list, prior to forwarding that flood packet,
Reference is now made to Figures 7A, 7B and 7C which are schematic illustrations of an exemplary network backbone, generally referenced 320, in accordance with another embodiment of the disclosed technique. Network backbone 320 includes super-nodes 322, 324, 326, 328, 330, 332, 334 and 336. Bold line 338, represents the dedicated backbone routing link between super-node 322 and super-node 324. Bold line 340, represents the dedicated backbone routing link between super-node 322 and super-node 326. Bold line 342, represents the dedicated backbone routing link between super-node 322 and super-node 328. Bold line 34, represents the dedicated backbone routing link between super-node 324 and super-node 330. Bold line 346, represents the dedicated backbone routing link between super-node 324 and super-node 326. Bold
line 3435, represents the dedicated baci