TREE BASED WIRELESS MESH FOR AN OSPF NETWORK WITH INTRA-TREE COMMUNICATION OPTIMIZATION

• US 20080080401A1
• Filed: 09/29/2006
• Published: 04/03/2008
• Est. Priority Date: 09/29/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Roy, Abhay, Thubert, Pascal, Wetterwald, Patrick, Ribiere, Vincent
• Granted Patent: US 7,720,010 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 76/10 Connection setup
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 88/16 Gateway arrangements
• CPC Class Codes: H04W 92/24 between backbone network devices

Abstract

A system for providing a tree topology for a network having an interior gateway protocol. A first router receives a hello message from all connected routers in the network. The hello messages include tree topology information. The first router then uses the tree topology information to determine a parent of the router. The first router then establishes connections with directly connected routers at the same level in the tree topology. The first router also generates link messages that include all of the prefixes for children of the first router and broadcasts the link messages.

Claims

1. A method for providing a tree topology in an interior gateway protocol to reduce network traffic comprising:

receiving a discovery message from each routing system connected to a first routing system wherein each discovery message includes tree topology level information;

determining a parent routing system of said first routing system in said tree topology of said network from said tree topology level information in each said discovery message received from each said routing system;

determining a depth in said tree topology of said network of said first routing system and said parent of said first routing system; and

forming adjacencies with all routers at a same depth in said tree topology connected to said first routing system.

5. The method of claim 1 further comprising:

establishing a default route from said first routing system to said parent routing system responsive to a determination of said parent routing system.

6. The method of claim 1 further comprising:

hiding all routes learned by said first routing system from said parent routing system.

2. The method of claim 2 further comprising:

generating a connection advertisement message wherein said advertisement message includes all prefixes from each child routing system of said first routing system in said tree topology; and

transmitting said connection advertisement message from said first routing system to said parent routing system.

3. The method of claim 2 further comprising:

transmitting said connection advertisement message from a first routing system to all routing systems in said network having a same tree depth in said tree topology as said first routing system.

4. The message of claim 2 wherein said connection advertisement message is a link state advertisement.

7. An apparatus for providing a tree topology of a network using an interior gateway protocol to reduce network traffic comprising:

circuitry configured to receive a discovery message from each routing system connected to a first routing system wherein each discovery message includes tree topology level information;

circuitry configured to determine a parent routing system of said first routing system in said tree topology of said network from said tree topology level information in each said discovery message received from each said routing system;

circuitry configured to determine a depth in said tree topology of said network of said first routing system and said parent of said first routing system; and

circuitry configured to form adjacencies with all routers at a same depth in said tree topology connected to said first routing system.

8. The apparatus of claim 7 further comprising:

circuitry configured to generate a connection advertisement message wherein said advertisement message includes all prefixes from each child routing system of said first routing system in said tree topology; and

circuitry configured to transmit said connection advertisement message from said first routing system to said parent routing system.

9. The apparatus of claim 8 further comprising:

circuitry configured to transmit said connection advertisement message from a first routing system to all routing systems in said network having a same tree depth in said tree topology as said first routing system.

10. The apparatus of claim 8 wherein said connection advertisement message is a link state advertisement.

11. The apparatus of claim 7 further comprising:

circuitry configured to establish a default route from said first routing system to said parent routing system responsive to a determination of said parent routing system.

12. The apparatus of claim 7 further comprising:

circuitry configured to hide all routes learned by said first routing system from said parent routing system.

13. A computer readable medium carrying one or more instructions for providing a tree topology over a network having an interior gateway protocol, the one more instructions including instructions which executed by one or more processors, cause the one or more processors to perform a method comprising:

receiving a discovery message from each routing system connected to a first routing system wherein each discovery message includes tree topology level information;

determining a parent routing system of said first routing system in said tree topology of said network from said tree topology level information in each said discovery message received from each said routing system;

determining a depth in said tree topology of said network of said first routing system and said parent of said first routing system; and

forming adjacencies with all routers at a same depth in said tree topology connected to said first routing system.

14. The method of claim 13 further comprising:

generating a connection advertisement message wherein said advertisement message includes all prefixes from each child routing system of said first routing system in said tree topology; and

transmitting said connection advertisement message from said first routing system to said parent routing system.

15. The method of claim 14 further comprising:

transmitting said connection advertisement message from a first routing system to all routing systems in said network having a same tree depth in said tree topology as said first routing system.

16. The message of claim 14 wherein said connection advertisement message is a link state advertisement.

17. The method of claim 13 further comprising:

establishing a default route from said first routing system to said parent routing system responsive to a determination of said parent routing system.

18. The method of claim 13 further comprising:

hiding all routes learned by said first routing system from said parent routing system.