Process for generating and updating a hierarchical tree in a MANET multicast routing protocol ad hoc network

• US 7,602,738 B2
• Filed: 05/11/2005
• Issued: 10/13/2009
• Est. Priority Date: 05/18/2004
• Status: Expired due to Fees

• Current Assignee: Alcatel SA (Nokia Corporation)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Preguica, Christophe
• Primary Examiner(s): JAIN, RAJ K
• Application Number:
  US11/126,293
• Publication Number:
  US 20050259595A1
• Time in Patent Office: 1,616 Days
• Field of Search: None
• US Class Current: 370/256
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

A MANET multicast proactive routing protocol ad hoc network is designed to implement a process dedicated to the generating and updating of a “child/parent” hierarchical tree. This process consists, if a “child” router (RR1) belonging to the network wishes to join a hierarchical tree associated with a source router (SR), of associating this child router (RR1) with a neighboring “parent” router (R1_NA) through the transmitting of a join message designating the source router (SR), in unicast mode, to the neighboring parent router (R1_NA).

Claims

1. A process for generating a “

child/parent”

hierarchical tree to carry out a point-to-multipoint routing in a Mobile Ad Hoc Network (MANET), wherein the process consists;

, each time that a “

child”

router (RR, R) of said network wishes to join the hierarchical tree associated with a source router (SR), said child router sends a join message that associates said child router with a neighboring “

parent”

router (R) of said child router in the network, wherein said child router uses its knowledge of a network topology to determine said parent router as a neighboring router better placed than said child router on a routing path to the source router,

said join message being transmitted by said child router to said neighboring parent router (R) in point-to-point mode, said join message denoting said source router (SR), and

(a) If said neighboring parent router is already associated with another child router of said network, said requesting child router is associated with said neighboring parent router, in order to join it to said tree, and a value of a state information representative of a number of child routers associated with said neighboring parent router is incremented by one unit,

(b) If said neighboring parent router is not already associated with another child router of said network, said requesting child router is associated with said neighboring parent router and said state information of said neighboring parent router is given the value “

one”

, and said neighboring parent router transmits a join message designating said source router (SR) in point-to-point mode, to another neighboring router in said network, which in its turn constitutes a parent for said neighboring parent router,

(c) Operation a) or operation b) is then repeated with said neighboring parent router receiving a join message according to whether or not it is already associated with another child router of said network.

2. A process according to claim 1, wherein:

if said child router (RR, R) no longer wishes to belong to said tree, said child router transmits a prune message to its neighboring parent router in point-to-point mode.

3. A process according to claim 2, wherein:

i. if said neighboring parent router is associated with at least two child routers of said network, said requesting child router is disassociated from said neighboring parent router, so that it no longer belongs to said tree, and the value of said neighboring parent router'"'"'s state information representative of the number of child routers associated with it is decremented by one unit,

ii. if said neighboring parent router is only associated with said requesting child router, said requesting child router is disassociated from said neighboring parent router and said state information of said neighboring parent router is given the value zero, and transmitting a request for pruning from said tree by said neighboring parent router, to its own neighboring parent router, in point-to-point mode,

iii. operation i) or operation ii) is then repeated with said neighboring parent router receiving a prune message according to whether it is associated with at least two child routers or with a single child router.

4. A process according to claim 1, wherein:

if a link embodying an association between said parent router and said child router is interrupted, said child router transmits a join message designating said source router (RS), in point-to-point mode, to another neighboring router of said network, in order to be associated with it, and this neighboring router then becomes a new neighboring parent router for said child router.

5. A process according to claim 4, wherein:

I) if said neighboring parent router is already associated with another child router of said network, said requesting child router is associated with its new neighboring parent router, in order to join it to said tree, and the value of said new neighboring parent router'"'"'s state information representative of the number of child routers associated with it is incremented by one unit,

II) if said new neighboring parent router is not already associated with another child router of said network, said requesting child router is associated with said new neighboring parent router and said state information of said new neighboring parent router is given the value “

one”

, and transmitting a join message designating said source router (SR) in point-to-point mode, by said new neighboring parent router, to another neighboring router of said network, which in its turn becomes a parent for said new neighboring parent router,

III) operation I) or operation II) is then repeated with said neighboring parent router receiving a join message according to whether or not it is already associated with another child router of said network.

6. A process according to claim 4, wherein:

if said link embodying an association between said parent router and said child router is interrupted, said parent router transmits a request for pruning from said tree to its neighboring parent router, in point-to-point mode.

7. A process according to claim 6, wherein:

a time elapsed since start of said link interruption is counted by said parent router, so that said prune request is only transmitted once a first chosen duration has elapsed.

8. A process according to claim 1, wherein:

at a level of each router of said tree an intensity of signals originating from its parent router is analyzed, then said intensities are compared with a chosen threshold, so that if an intensity below said threshold is detected by a child router on a link with its neighboring parent router, said child router transmits a request to join said tree to a neighboring router other than its neighboring parent router.

9. A process according to claim 8, wherein:

a time elapsed since said signal intensity first fell below the threshold is counted by said child router, so that said join request is only transmitted once a second chosen duration has elapsed.

10. A process according to claim 1, wherein:

said join message and/or a prune message includes a “

unicast”

address designating said source router and a “

multicast”

group address.

11. A process according to claim 1, wherein:

said MANET point-to-multipoint proactive routing protocol is chosen from a group containing at least the Topology Based and dissemination with Reverse Path Forwarding (TBRPF) and Optimized Link State Routing (OLSR) protocols.