Systems and methods for constructing a virtual model of a multi-hop, multi-access network
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
37 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
-
-
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; andincorporating 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. - View Dependent Claims (35)
-
-
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.
-
Specification