Independent-tree ad hoc multicast routing

• US 7,035,937 B2
• Filed: 04/11/2002
• Issued: 04/25/2006
• Est. Priority Date: 04/25/2001
• Status: Expired due to Fees

• Current Assignee: Cornell Research Foundation Incorporated (Cornell University)
• Original Assignee: Cornell Research Foundation Incorporated (Cornell University)
• Inventors: Haas, Zygmunt J., Sajama, S.
• Primary Examiner(s): SALAD, ABDULLAHI ELMI
• Application Number:
  US10/120,190
• Publication Number:
  US 20030005149A1
• Time in Patent Office: 1,475 Days
• Field of Search: 709238-239, 709227-228, 379227-228, 370/238, 370/216, 714/47
• US Class Current: 709/239
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/1877 Measures taken prior to transmission
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04W 4/06 Selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS]; Services to user groups; One-way selective calling services
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

A routing protocol for a multicasting network, such as an ad hoc network, employs alternate tree or path computation algorithms that continually compute backup trees or paths that can be employed to replace failed trees or paths. The sets of alternate multicast trees or paths are preferably pre-calculated before a first tree or path fails to minimize delay in replacing a failed tree or path. Preferably, the algorithms are designed to compute the alternate multicast trees or paths in such a manner that they are maximally independent of the original set of trees and paths to minimize correlation between the original trees or paths and the replacement trees or paths and to possibly increase the useful time of the calculated trees. This helps insure that the replacement trees or paths will not be likely themselves to fail soon after failure of the original trees or paths.

Claims

1. A method of operating a multicasting communications network comprising the steps of:

a) providing a multicasting communications network formed of a plurality of nodes and links connecting said nodes to facilitate communication among said nodes;

b) calculating a first multicast routing scheme, said multicast routing scheme defining, for each of said nodes, a plurality of paths for facilitating communication with each of said other nodes in said network, said paths each being formed by one or more of said links;

c) calculating one or more alternate multicast routing schemes to be employed if said first multicast routing scheme fails due to failure of one or more of said links or nodes;

b) implementing multicasting communications between said nodes in said network by interconnecting said nodes in accordance with said first multicast routing scheme; and

d) interconnecting said nodes in accordance with one of said alternate multicast routing schemes if said first multicast routing scheme fails;

e) estimating a time at which a probability of said one or more alternate multicast routing schemes failing exceeds a predetermined threshold;

f) employing said estimated time to determine a time at which calculation of one or more additional alternate multicast routing schemes should begin; and

,

g) calculating one or more additional alternate multicast routing schemes at said determined time.

2. The method of claim 1, wherein said first multicast routing scheme comprises a first set of routing trees that define how each of said nodes is connected to one or more of said other of said nodes using said links, and said one or more alternate multicast routing schemes comprise one or more set of backup trees.

3. The method of claim 2, wherein said sets of alternate multicast backup trees are calculated using an algorithm that maximizes the independence of said alternate multicast trees relative to said first set of multicast trees by minimizing the number of said nodes and links that are employed in said first set of trees.

4. The method of claim 1, wherein said first multicast routing scheme comprises a first set of multicast routing trees that define how each of said nodes is connected to one or more of said other of said nodes using said paths, and said alternate multicast routing schemes comprise one or more sets of backup paths to be used if one or more of said paths in said first set of multicast routing trees fails.

5. The method of claim 4, wherein said one or more sets of backup paths are calculated using an algorithm that maximizes the independence of said backup paths relative to the paths employed in said first set of multicast trees.

6. A multicasting communications network comprising:

a) a plurality of communications nodes; and

b) a plurality of links connecting said nodes to facilitate communication among said nodes;

wherein, each of said nodes includes;

1) a transceiver for receiving communications from and transmitting communications to other of said nodes in said network

2) a processor for controlling operation of said transceiver, said processor being programmed to calculate a first multicast routing scheme, said multicast routing scheme defining, for each of said nodes, a plurality of paths for facilitating multicast communication with each of said other nodes in said network, said paths each being formed by one or more of said links, and one or more alternate multicast routing schemes to be employed if said first routing scheme fails due to failure of one or more of said links or nodes;

said processor also being programmed to estimate a time at which a probability of said one or more alternate multicast routing schemes failing exceeds a predetermined threshold, employ said estimated time to determine a time at which calculation of one or more additional alternate multicast routing schemes should begin, and calculate one or more additional alternate multicast routing schemes at said determined time; and

3) a database for storing said first and one or more alternate multicast routing schemes.

7. The network of claim 6, wherein said first routing scheme comprises a first set of multicast routing trees that define how each of said nodes is connected to one or more of said other of said nodes using said links, and said one or more alternate multicast routing schemes comprise one or more set of backup trees.

8. The network of claim 7, wherein said processor is programmed to calculate said sets of alternate backup multicast trees using an algorithm that maximizes the independence of said alternate multicast trees relative to said first set of multicast trees by minimizing the number of said nodes and links that are employed in said first set of multicast trees.

9. The network of claim 6, wherein said first routing scheme comprises a first set of multicast routing trees that define how each of said nodes is connected to one or more of said other of said nodes using said paths, and said alternate multicast routing schemes comprise one or more sets of backup paths to be used if one or more of said paths in said first set of multicast routing trees fails.

10. The network of claim 9, wherein said processor is programmed to calculate said one or more sets of multicast backup paths using an algorithm that maximizes the independence of said multicast backup paths relative to the paths employed in said first set of trees.

11. The network of claim 6, wherein said network is an ad-hoc network.