Systems and methods for constructing a virtual model of a multi-hop, multi-access network

• US 7,983,239 B1
• Filed: 01/07/2004
• Issued: 07/19/2011
• Est. Priority Date: 01/07/2003
• Status: Active Grant

• Current Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Original Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Inventors: Shapiro, Jonathan, Rosenzweig, Vladimir, Weinstein, Joseph J., Castineyra, Isidro Marcos
• Primary Examiner(s): Nguyen; Hanh
• Application Number:
  US10/752,988
• Time in Patent Office: 2,750 Days
• Field of Search: 370/235, 370/236, 370/351, 370/389, 370/400, 370/238, 370/390, 370/419, 370/255, 370/352
• US Class Current: 370/351
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

A system constructs an OSPF-compatible virtual model of a multi-hop, multi-access packet radio network that includes a plurality of routers (120) and which includes its own private, internal routing system (150), in order to facilitate the incorporation of that packet radio network into an overall OSPF routing environment. The system determines a network graph identifying actual connectivity among the plurality of routers (120). The system constructs a virtual model (300) of the, wherein connectivity of the virtual model may be different than the actual connectivity of the network graph. The system represents the multi-hop, multi-access radio network in the virtual model as a set of multi-access links (305, 310), point-to-point links, AS-external routes, and area summary routes. The system employs the virtual model for routing purposes and advertises the virtual model to other OSPF routers for the same purpose.

Claims

1. A method preformed by a network device comprising:

acquiring information as to the internal topology of a sub-network that uses a private, internal routing system;

constructing a virtual model of the sub-network in terms of constructs comprehensible to a public, global routing system of a network, where the virtual model contains a link-state description of an idealized sub-network that represents an actual sub-network, where the idealized sub-network includes;

nodes of the sub-network that are also nodes of the network,

links among the nodes, where a connected path exists through the idealized sub-network between two nodes of the idealized sub-network if there exists a connected path between the two nodes through the actual sub-network, where a degree of the idealized sub-network is less than a degree of the actual sub-network, and where a set of links in the idealized sub-network changes less frequently than a set of links in the actual sub-network;

costs associated with the links, where a cost of a shortest connected path between two nodes of the idealized sub-network approximates a cost of a shortest connected path between the two nodes of the actual sub-network, and where costs associated with the links in the idealized sub-network change less frequently than costs associated with the actual sub-network,

employing the virtual model and public, global routing system together with the private, internal routing system of the sub-network for routing within the sub-network, where the virtual model and public, global routing system are used to select among two or more potential exit points from the sub-network for traffic that will exit or transit the sub-network, and where the private, internal routing system is used to select the internal route to the exit point;

distributing the virtual model to routers in the network for routing within the network, where the routers use the virtual model to select a preferred entry point to the sub-network from among two or more potential entry points for traffic that will enter or transit the sub-network.

2. The method of claim 1, where the network is at least one of an IPv4 network, an IPv6 network, or a derivative of an IPv4 or IPv6 network.

3. The method of claim 1, where the public, global routing system implements Open Shortest Path First (OSPF) or a derivative of OSPF.

4. The method of claim 1, where the private, internal routing system of the sub-network operates at a lower layer in a network protocol stack than the public, global routing system.

5. The method of claim 1, where the sub-network is a mobile ad-hoc network (MANET) that employs at least one of radio, sonar, optical, or other physical communications mechanisms.

6. The method of claim 1, where the private, internal routing system implements Open Shortest Path First (OSPF) or a derivative of OSPF.

7. The method of claim 1, where the private, internal routing system is a custom routing protocol intended to optimize routing within the sub-network.

8. The method of claim 1, where a topology of the sub-network may vary with time due to mobility of hosts and routers of the plurality of routers, due to changes in connectivity between the hosts and the routers of the plurality of routers, due to the entry or exit of routers of the plurality of routers from the sub-network, or due to other factors.

9. The method of claim 1, where the virtual model of the sub-network differs from an actual connectivity of the sub-network.

10. The method of claim 1, where the virtual model of the sub-network includes a plurality of multi-access links, point-to-point links, AS-external routes, and area-external summary routes.

11. The method of claim 1, where information as to the actual topology of the sub-network is acquired by messages generated by the private, internal routing system of the sub-network.

12. The method of claim 1, where the virtual model of the sub-network is constructed dynamically from information as to an actual connectivity of the sub-network.

13. The method of claim 1, where an actual route of a packet through the same network differs from a route as computed by a public, global routing protocol, with entrance and exit points to the sub-network being determined by the public, global routing protocol.

14. The method of claim 1, where the virtual model of the sub-network is employed by routers of a plurality of routers in the sub-network to determine a desired exit point from the sub-network, and the-private internal routing system of the sub-network is employed to determine a route through the sub-network to the determined exit point.

15. The method of claim 1, where the virtual model is distributed by routers of a plurality of routers in the sub-network to other routers in the network using mechanisms provided by the public, global routing system so as to maintain strict compatibility with off-the-shelf routers in the network implementing the public, global routing system.

16. A method of reducing routing overhead on a network containing a sub-network including a plurality of routers, comprising:

employing a public routing protocol on the network;

employing a separate, private routing protocol internal to the sub-network;

acquiring information as to an internal topology of the sub-network;

constructing a virtual model of the sub-network in terms of constructs comprehensible to the public, global routing protocol, where the virtual model contains a link-state description of an idealized sub-network that represents an actual sub-network, where the idealized sub-network includes;

nodes of the sub-network that are also nodes of the network,

links among the nodes, where a connected path exists through the idealized sub-network between two nodes of the idealized sub-network if there exists a connected path between the two nodes through the actual sub-network, where a degree of the idealized sub-network is less than a degree of the actual sub-network, and where a set of links in the idealized sub-network changes less frequently than a set of links in the actual sub-network;

costs associated with the links, where a cost of a shortest connected path between two nodes of the idealized sub-network approximates a cost of a shortest connected path between the two nodes of the actual sub-network, and where costs associated with the links in the idealized sub-network change less frequently than costs associated with the actual sub-network,

employing the virtual model and the public, global routing system together with the sub-network'"'"'s private, internal routing protocol for routing within the sub-network, where the virtual model and public, global routing system are used to select among two or more potential exit points from the sub-network for traffic that will exit or transit the sub-network, and the private, internal routing system is used to select the internal route to the exit point;

distributing the virtual model to other routers in the network for routing in that network, where routers use the virtual model to select a preferred entry point to the sub-network from among two or more potential entry points for traffic that will enter or transit the sub-network.

17. The method of claim 16, where the network is at least one of an IPv4 network, an IPv6 network, or a derivative of an IPv4 or an IPv6 network.

18. The method of claim 16, where the public routing protocol comprises an Open Shortest Path First (OSPF) routing protocol or a derivative of an OSPF routing protocol.

19. The method of claim 16, where the private, internal routing protocol of the sub-network operates at a lower layer in a network protocol stack than the public, global routing protocol.

20. The method of claim 16, where the sub-network is a mobile ad-hoc network (MANET) that employs at least one of radio, sonar, optical, or other physical communications mechanism.

21. The method of claim 16, where the private, internal routing protocol implements Open Shortest Path First (OSPF) or a derivative of OSPF.

22. The method of claim 16, where the private, internal routing protocol is a custom routing protocol intended to optimize routing within the sub-network.

23. The method of claim 16, where a topology of the sub-network varies with time due to mobility of hosts and routers of the plurality of routers, due to changes in connectivity between the hosts and the routers of the plurality of routers, due to the entry or exit of routers of the plurality of routers from the sub-network, or due to other factors.

24. The method of claim 16, where the virtual model of the sub-network differs from an actual connectivity of the sub-network.

25. The method of claim 16, where the virtual model of the sub-network includes a plurality of multi-access links, point-to-point links, AS-external routes, and area-external summary routes.

26. The method of claim 16, where information as to an actual topology of the sub-network is acquired by messages generated by the private, internal routing protocol of the sub-network.

27. The method of claim 16, where the virtual model of the sub-network is constructed dynamically from information as to an actual connectivity of the sub-network.

28. The method of claim 16, where an actual route of a packet through the network differs from a route as computed by the public, global routing protocol, with entrance and exit points to the sub-network being determined by the public, global routing protocol.

29. The method of claim 16, where the virtual model of the sub-network is employed by routers of the plurality of routers to determine a desired exit point from the sub-network, and the sub-network'"'"'s private internal routing protocol is employed to determine a route through the sub-network to the determined exit point.

30. The method of claim 16, where the virtual model is distributed by routers of the plurality of routers to other routers in the network using mechanisms provided by the public, global routing protocol, so as to maintain strict compatibility with off-the-shelf routers in the network implementing the public, global routing protocol.

31. A method performed by a network device, the method comprising:

determining, by the network device, a network graph identifying actual connectivity among a plurality of routers in a sub-network;

representing, by the network device, the sub-network as a set of links; and

constructing, by the network device, a virtual model of the sub-network from the actual connectivity of the network graph, where connectivity of the virtual model is different than the actual connectivity of the network graph, where the virtual model is represented using constructs of a routing protocol that is different from a private, routing protocol employed on the sub-network, and where the virtual model incorporates a plurality of network nodes representing multi-access links so as to minimize an average network degree of the virtual model and minimize overhead involved in distributing the virtual model.

32. A method performed by a network device, the method comprising:

determining, by the network device, a network graph identifying actual connectivity among a plurality of routers in a sub-network;

representing, by the network device, the sub-network as a set of links; and

constructing, by the network device, a virtual model of the sub-network from the actual connectivity of the network graph, where connectivity of the virtual model is different than the actual connectivity of the network graph, where the virtual model is represented using constructs of a routing protocol that is different from a private, routing protocol employed on the sub-network, and where the virtual model hides most changes to the internal topology of the sub-network so as to minimize a frequency with which the virtual model is redistributed and minimize the overhead involved in distributing the virtual model.

33. A method performed by a network device, the method comprising:

determining, by the network device, a network graph identifying actual connectivity among a plurality of routers in a sub-network;

representing, by the network device, the sub-network as a set of links; and

constructing, by the network device, a virtual model of the sub-network from the actual connectivity of the network graph, where connectivity of the virtual model is different than the actual connectivity of the network graph, where the virtual model is represented using constructs of a routing protocol that is different from a private, routing protocol employed on the sub-network; and

incorporating a hysteresis check to limit a rate at which the virtual model of the sub-network may change in time in response to changes in a topology of the sub-network so as to minimize a frequency with which the virtual model is redistributed and minimize the overhead involved in distributing the virtual model.

34. A method, performed by a network device, the method comprising:

determining, by the network device, a desired exit point from a sub-network that uses a private, internal routing protocol based upon a different public, global routing protocol of a network, where the public, global routing protocol routes in accordance with a virtual model of the sub-network, where the virtual model contains a link-state description of an idealized sub-network that represents an actual sub-network, where the idealized sub-network includes;

nodes of the sub-network that are also nodes of the network,

links among the nodes, where a connected path exists through the idealized sub-network between two nodes of the idealized sub-network if there exists a connected path between the two nodes through the actual sub-network, where a degree of the idealized sub-network is less than a degree of the actual sub-network, and where a set of links in the idealized sub-network changes less frequently than a set of links in the actual sub-network, and

costs associated with the links, where a cost of a shortest connected path between two nodes of the idealized sub-network approximates a cost of a shortest connected path between the two nodes of the actual sub-network, and where costs associated with the links in the idealized sub-network change less frequently than costs associated with the actual sub-network; and

determining, by the network device, a next-hop destination to reach the desired exit point based upon the private, internal routing system.

35. The method of claim 34, where the public, global routing protocol is Open Shortest Path First (OSPF) or a derivative of OSPF.

36. A method, performed by a network device, the method comprising:

determining, by the network device, a desired exit point from a sub-network that uses a private, internal routing protocol based upon a different public, global routing protocol of a network, where the public, global routing protocol routes in accordance with a virtual model of the sub-network, where the determined desired exit point chosen is a same as that selected by the public, global routing protocol as a next-hop destination by applying its standard routing computation to the virtual model of the sub-network, where the virtual model contains a link-state description of an idealized sub-network that represents an actual sub-network, where the idealized sub-network includes;

nodes of the sub-network that are also nodes of the network,

links among the nodes, where a connected path exists through the idealized sub-network between two nodes of the idealized sub-network if there exists a connected path between the two nodes through the actual sub-network, where a degree of the idealized sub-network is less than a degree of the actual sub-network, and where a set of links in the idealized sub-network changes less frequently than a set of links in the actual sub-network, and

costs associated with the links, where a cost of a shortest connected path between two nodes of the idealized sub-network approximates a cost of a shortest connected path between the two nodes of the actual sub-network, and where costs associated with the links in the idealized sub-network change less frequently than costs associated with the actual sub-network; and

determining, by the network device, a next-hop destination to reach the desired exit point based upon the private, internal routing system.

37. A method, performed by a network device, the method comprising:

determining, by the network device, a desired exit point from a sub-network that uses a private, internal routing protocol based upon a different public, global routing protocol of a network, where the desired exit point is determined by searching along a route selected by the public, global routing protocol to find an actual point at which the route exits the sub-network as known to the public, global routing protocol, and where the search terminates before reaching the actual desired exit point from the network due to incomplete routing information, leading to a choice of an intermediate router as the exit point; and

determining, by the network device, a next-hop destination to reach the desired exit point based upon the private, internal routing protocol.