Tree based wireless mesh for an OSPF network with intra-tree communication optimization

• US 7,720,010 B2
• Filed: 09/29/2006
• Issued: 05/18/2010
• 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: Ribiere, Vincent, Roy, Abhay, Thubert, Pascal, Wetterwald, Patrick
• Primary Examiner(s): Vu; Huy D
• Assistant Examiner(s): RENNER, BRANDON M
• Application Number:
  US11/537,298
• Publication Number:
  US 20080080401A1
• Time in Patent Office: 1,327 Days
• Field of Search: 307/256, 307/338, 307/351, 307/401
• 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;

in response to determining said depth, forming adjacencies with all routers at a same depth in said tree topology connected to said first routing system;

generating a connection advertisement message that includes prefixes learned from one or more child routing systems of said first routing system in said tree topology; and

transmitting said generated connection advertisement message from said first routing system to said parent routing system of said first routing system in the tree topology, while not sending the generated connection advertisement message to any of said one or more child routing systems of the first routing system in the tree topology.

2. The method of claim 1 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.

3. The method of claim 1 wherein said connection advertisement message is a link state advertisement.

4. 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.

5. The method of claim 1 further comprising:

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

6. 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;

circuitry configured to form adjacencies with all routers at a same depth in said tree topology connected to said first routing system in response to the determination of said depth;

circuitry configured to generate a connection advertisement message that includes prefixes learned from one or more child routing systems of said first routing system in said tree topology; and

circuitry configured to transmit said generated connection advertisement message from said first routing system to said parent routing system of said first routing system in the tree topology, while not sending the generated connection advertisement message to any of said one or more child routing systems of the first routing system in the tree topology.

7. The apparatus of claim 6 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.

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

9. The apparatus of claim 6 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.

10. The apparatus of claim 6 further comprising:

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

11. 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:

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

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;

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

form adjacencies with all routers at a same depth in said tree topology connected to said first routing system in response to the determination of said depth;

generate a connection advertisement message that includes prefixes learned from one or more child routing systems of said first routing system in said tree topology; and

transmit said generated connection advertisement message from said first routing system to said parent routing system of said first routing system in the tree topology, while not sending the generated connection advertisement message to one or more child routing systems of the first routing system in the tree topology.

12. The computer readable medium of claim 11 wherein the one more instructions further include instructions which executed by one or more processors, cause the one or more processors 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.

13. The computer readable medium of claim 11 wherein said connection advertisement message is a link state advertisement.

14. The computer readable medium of claim 11 wherein the one more instructions further include instructions which executed by one or more processors, cause the one or more processors to:

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

15. The computer readable medium of claim 11 wherein the one more instructions further include instructions which executed by one or more processors, cause the one or more processors to:

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

16. A method comprising:

receiving an interior gateway protocol message at a first routing system in a network;

determining a parent routing system of the first routing system in a tree topology defined for the network using the interior gateway protocol message, the tree topology having a plurality of levels, wherein each routing system in the tree topology, other than a base routing system, has a parent in a level immediately above the routing system in the tree topology;

determining a level in the tree topology of the first routing system;

determining other routing systems that are connected to the first routing system and are on a same level of the tree topology as the first routing system;

in response to the determining other routing systems that are connected to the first routing system and are on a same level of the tree topology as the first routing system, forming, by the first routing system, adjacencies with the other routing systems; and

limiting flooding of interior gateway protocol link state advertisement messages (LSAs) based upon the tree topology by generating LSAs at the first routing system that include prefixes learned from one or more child routing systems of the first routing system in the tree topology, and transmitting the generated LSAs only to the parent routing system of the first routing system in the tree topology, while not sending the generated LSAs to one or more child routing systems of the first routing system in the tree topology.

17. The method of claim 16 wherein the generated LSAs further include prefixes of interfaces of the first routing system.

18. The method of claim 16 wherein the generated LSAs are LSAs having link-local scoping.

19. The method of claim 16 wherein the interior gateway protocol is an Open Shortest Path First (OSPF) protocol.

20. A routing system comprising:

a plurality of ports;

a processing unit; and

a memory configured to store instructions configured to, when executed by the processing unit, determine a parent routing system of the routing system in a tree topology defined using a message received on at least one of the plurality of ports, the tree topology having a plurality of levels, wherein each routing system in the tree topology, other than a base routing system, has a parent in a level immediately above the routing system in the tree topology, determine a level in the tree topology of the routing system, determine other routing systems that are connected to the routing system and are on a same level of the tree topology as the routing system, form adjacencies with one or more other routing systems on the same level of the tree topology as the routing system, limit flooding of link state advertisement messages (LSAs) based upon the tree topology by generation of LSAs that include prefixes learned from one or more child routing systems of the routing system in the tree topology and transmission via at least one of the plurality of ports of the generated LSAs to the parent routing system of the routing system in the tree topology, while not sending the generated LSAs to any of the one or more child routing systems of the routing system in the tree topology.

21. The routing system of claim 20 wherein the generated LSAs further include prefixes of interfaces of the first routing system.

22. The routing system of claim 20 wherein the generated LSAs are LSAs having link-local scoping.

23. The routing system of claim 20 wherein the message and the LSAs are part of an Open Shortest Path First (OSPF) protocol.

24. The routing system of claim 20 wherein the instructions are further configured to, when executed by the processing unit, transmit via at least one of the plurality of ports, LSAs to the one or more other routing systems routing system on the same level of the tree topology as the routing system.