Virtual exterior gateway protocol and related methods

[0001] The present invention relates to communication networks and more particularly (but not exclusively) to communication interfaces between networks.

[0002] An autonomous system (AS), also sometimes referred to as a routing domain, is a network having a single defined Internet routing policy. The Internet may be described as a network-of-networks, that is, a network of ASes linked with one another via an exterior gateway protocol (EGP). The current EGP of the Internet is the Border Gateway Protocol version 4 (BGPv4). ASes of the Internet for the most part share stable, pair-wise interfaces. These interfaces usually occur across wire-based network infrastructures. A mobile ad hoc network (MANET) is an autonomous system of primarily mobile nodes, e.g., mobile routers, connected primarily by wireless links. In contrast to most other autonomous systems, MANETs can be extremely flexible and are often characterized by a significant amount of mobility and geographical movement.

[0003] Because MANET nodes are mobile, however, a topology of a MANET network nodes may change quickly and unpredictably. Connectivity may be intermittent between MANET nodes, and wireless links can create the appearance of rapid topology changes through signal intermittence, even if no movement is actually occurring. Rapid topology changes often detrimentally impact convergence of routing protocols, making these protocols less reliable. BGPv4 is designed to operate within a context of providing a stable, pair-wise interface between peer nodes in different ASes. This approach can break down when a pair-wise interface peer in one AS moves out of transmission range of its peer in another AS. BGPv4 can also break down when one peer dynamically establishes a new pair-wise relationship with a new peer that comes in range in the other AS. Thus, BGPv4 is not well-suited to support highly mobile environments.

[0004] The Internet protocol (IP) currently supports a hierarchical topology system according to which network interfaces of nodes are connected into subnetworks and subnetworks are connected into networks (ASes). Subnetworks may be connected into ASes by means of interior gateway protocols such as Open Shortest Path First (OSPF) and/or Intermediate System-Intermediate System (IS-IS). As previously mentioned, ASes may be connected via EGP protocols into the Internet.

[0005] ASes of very large entities often are limited in size because of IP scaling properties of IGP protocols. A very large entity network may be physically realized as a plurality of ASes linked together by EGP protocols, even though the ASes share a common security and quality-of-service (QoS) policy and common administrative and business attributes. Because EGP protocols provide only pair-wise relationships, segmenting a large entity network into a series of ASes connected by EGP generally constrains the flexibility of the network design and can create bottlenecks within the network communication paths.

[0006] The present invention, in one configuration, is directed to an aggregation of a plurality of networks. The aggregation includes a plurality of peer nodes of the networks, each node including a plurality of channels operating at a plurality of interior gateway protocol (IGP) routing levels configured to provide a mesh interface between at least two of the networks.

[0007] In another configuration, an aggregation includes first and second networks. A plurality of nodes include a plurality of hierarchical routing levels through which the first network is linked with the second network. Each node further includes a first channel through which the node is linked with the first network at a first of the routing levels, and a second channel through which the node is linked with the second network at a second of the routing levels.

[0008] In another configuration, an aggregated autonomous system (AS) includes a plurality of networks each having a backbone. A plurality of nodes of the backbones provide a plurality of hierarchical interfaces among the component networks.

[0009] In one implementation, the invention is directed to a method of communicating with a second network via a first network. A packet is routed from the first network to a meshed backbone that inter-connects the first network with a plurality of networks including the second network. The packet is received at a first IGP routing level. The packet is routed at a second IGP routing level to the second network. The receiving and routing steps are performed using a router of the backbone.

[0010] In yet another configuration, the invention is directed to a machine-readable medium for use with a processor having a memory. The machine-readable medium includes instructions to cause a router of a meshed backbone inter-connecting a plurality of networks including first and second networks to receive a packet from the first network at a first IGP routing level. Instructions also cause the router to route the packet to the second network at a second IGP routing level.

[0011] The features, functions, and advantages can be achieved independently in various embodiments of the present inventions or may be combined in yet other embodiments.

[0019] The following description of the preferred embodiment(s) is merely exemplary in nature and is in no way intended to limit the invention, its application, or uses. Although various configurations of the present invention are described with reference to a mobile ad-hoc network (MANET), the invention is not so limited. The invention can be practiced in connection with various network environments, wired and/or wireless. Configurations of the invention also can be appropriate for extremely large autonomous system environments and/or joint networks shared, for example, among businesses and/or other enterprises. Configurations also are contemplated with respect to networks, e.g., joint or coalition tactical military networks, shared by governmental entities.

[0020] In one embodiment of the present invention, an aggregation of networks includes a plurality of peer nodes, e.g., radio routers, of the networks. The nodes have multi-channel capabilities and are configured to operate at a plurality of Interior Gateway Protocol (IGP) routing levels. The peer nodes can be used to provide a mesh interface among a plurality of the networks.

[0021] One configuration of an aggregation of networks is indicated generally in FIG. 1 by reference number 20. A plurality of networks 24 communicate via a plurality of nodes 28 which may be a subset of routers of the networks. Each node 28 includes a plurality of channels 30 allowing the node to simultaneously transmit and receive on at least two different IP subnetworks (not shown) of the aggregation 20. Each of the nodes 28 is configured with a plurality of instances of a hierarchical Internet IGP to define a plurality of routing levels. Each instance is associated with a physical channel 30. The IGP may be, for example, OSPF (Open Shortest Path First) protocol or IS-IS (Intermediate System-Intermediate System) protocol. The routing levels are organized such that an IGP instance operating at a lower level of abstraction within a node 28 locally provides aggregated routing information to an IGP instance operating at a higher level of abstraction in the node.

[0022] Generally, unless otherwise specified, various configurations of the present invention are described in terms of OSPF. The OSPF and IS-IS protocols operate in the same or a similar manner. Thus the various implementations should be easily understood in terms of IS-IS by one knowledgeable in the art.

[0023] A node 28 is shown in greater detail in FIG. 2. At least two transceivers 32 of the node 28 can simultaneously transmit and receive using at least two distinctly configured waveforms 36a and 36b such that the waveforms 36a and 36b operate on different IP subnetworks. Referring to the configurations shown in FIGS. 1 and 2, it is assumed for simplicity that the node 28 operates at two levels of abstraction: a lower level and a higher level. The waveform 36a is used for communication at the lower level of abstraction between and within the networks 24. The waveform 36b is used for communication among the nodes 28 at the higher level of abstraction. The nodes 28 thus form an IGP community operating at the higher level of abstraction.

[0024] An IGP routing table 40a is associated with an IGP instance operating at the lower level of abstraction and cumulatively defines a topology of the networks 24. The routing table 40a locally transfers a summary of its view of the topology of networks 24 to a routing table 40b that operates at the higher level of abstraction. The routing table 40b thereby obtains a complete summary view of the aggregation 20, in that the routing table 40b describes the nodes 28 which are local to one another, together with the networks 24 that include each of the nodes 28. The routing table 40b thus describes which node 28 provides a path to a given underlying network element (not shown) located within the networks 24.

[0025] Although the foregoing description is in relation to two IGP routing levels, it is possible to define more than two IGP routing levels. A number of levels could depend, for example, on the scale of networks being aggregated (e.g., a number of networked devices in such a system). It also is contemplated that nodes, e.g., radio-routers, could be used which include more than two transceivers and can simultaneously operate at more than two IGP routing levels.

[0026] Another embodiment of an aggregation is shown in an Internet environment indicated generally in FIG. 3 by reference number 50. An aggregation 100 includes a plurality of networks 124 and a plurality of nodes 128 using a plurality of IGP levels. A node 128a of the aggregation 100 provides a well-known BGPv4 interface between itself and another AS 130 in the traditional exterior gateway protocol (EGP) manner. Thus the aggregation 100 can operate as a distinct autonomous system (AS) with other ASes via pair wise interfaces via the Internet, indicated generally by reference number 134.

[0027] In Table 1, a known topology of the Internet and a new topology system in accordance with principles of the present invention are shown.

[0028]

TABLE 1
Internet Topology:	New Topology System:
Network-of-Networks (Internet)	Network-of-Networks (Internet)
	Aggregation
Network (AS)	Network (AS)
Subnetwork	Subnetwork
Node's IP Interface	Node's IP Interface

[0029] Referring to Table 1 and FIG. 3, the aggregation 100 forms a new type of entity between system boundaries of the traditional Internet topology model, that is, between a network and a network-of-networks (Internet). Generally, unless otherwise indicated, the term “network” is used to refer to an AS included in an aggregation such as the aggregation 100. A network 124 in the aggregation 100 does not maintain its own AS number, but uses a common AS number associated with the aggregation 100 and used by all networks 124 in the aggregation 100.

[0030] It is possible to define a plurality of tiers of networks in accordance with principles of the present invention. For example, another aggregation in accordance with one embodiment of the present invention is indicated generally in FIG. 4 by reference number 200. The aggregation 200 includes a plurality of networks (i.e., ASes) 224. A network 224 includes one or more OSPF areas 226 (or, alternatively, one or more IS-IS areas) including one or more IP subnetworks (not shown in FIG. 4). A network 224 may have one or more local routers 236.

[0031] A plurality of routers 228 having interfaces 230 relative to the networks 224 are logically joined together in a separate backbone network 234. The backbone network 234 may be referred to as an “upper network”. The networks 224 linked together by the backbone network 234 may be referred to as “lower networks”. In the configuration shown in FIG. 4, three lower networks 238a-c are linked to the upper network 234.

[0032] Generally, in various embodiments of the present invention, hierarchical interior gateway protocols (IGPs) such as OSPF and/or IS-IS can be used to provide mesh relationships between networks, including but not limited to mobile networks, in a manner that appears to an IGP instance in a network node as being an exterior gateway protocol (EGP). There is no requirement that an upper or lower network use the same hierarchical IGP as another network. For example, an upper network could use IS-IS and lower networks could use OSPF. Alternatively, some lower networks could use IS-IS and other lower networks could use OSPF.

[0033] Referring again to FIG. 4, the lower networks 238a-c do not directly access each other except through the upper network 234. The routers 228 have interfaces 230 within Areas 0 (i.e., network backbones) of the networks 234 and 238. An OSPF instance operating in a router 228 views that router as being an autonomous system boundary router (ASBR). External routing information that is shared by the routers 228 is locally leaked to one OSPF link state database (LSDB) of a router 228 from another OSPF LSDB maintained on that router.

[0034] Similar to OSPF area border routers (ABRs) and ASBRs, the routers 228, which physically link the upper network 234 with lower networks 238, simultaneously include interfaces to entities within a plurality of networks 224. In such manner, a network, e.g., a MANET, including a plurality of tiers can be combined with other networks to form an aggregation having a backbone network infrastructure that functions in the same or similar manner as an Area 0 of hierarchical OSPF and/or backbone of IS-IS. A router 228 uses link state advertisement (LSA) 5 connections into Area 0 and/or backbone. Networks thus can form mesh relationships with one another in order to form a larger aggregated network construct. Such relationships are in contrast to those of BGP, which uses only pair-wise relationships between network entities.

[0035] Additionally, an aggregation of networks can operate as an autonomous system (AS). For example, an aggregation can communicate with other autonomous systems not included in the aggregation via an exterior gateway protocol (EGP) such as BGP using a single AS number for the aggregation. In the present exemplary configuration inter-AS relationships between the aggregation 200 and other ASes (not shown) is supported from Area 0 of the upper network 234.

[0036] A configuration of a node is indicated generally in FIG. 5 by reference number 300. The node 300 includes an upper OSPF link state database (LSDB) 304 relative to upper interfaces 308 in an Area 0 (numbered as 312) of an upper network 316. The node 300 also includes a lower OSPF LSDB 320 relative to lower interfaces 324 in an Area 0 (numbered as 328) of a lower network 332. Summary topology information in the lower and upper LSDBs 324 and 308 may be exchanged, e.g., locally leaked, between the LSDBs on a periodic basis, for example, dependent on events and/or timers. In one configuration, information is leaked every sixty (60) seconds. In another configuration, topology information in the lower and upper LSDBs 324 and 308 may be exchanged via link state advertisements (LSAs).

[0037] LSA information leaked by the LSDB 304 is a summary of topology information known about the upper network 316 within its associated Area 0 (numbered as 312). Such information is obtained from Type 1 LSAs, Type 2 LSAs, and/or Type 3 ABR Summary LSAs for the upper network 316. LSA information leaked by the LSDB 320 is a summary of topology information known about the lower network 332 within its associated Area 0 (numbered as 328). Such information is obtained from Type 1 LSAs, Type 2 LSAs, and/or Type 3 ABR Summary LSAs for the lower network 332. In the foregoing manner, upper and lower network routing information is exchanged.

[0038] Leaked information becomes announced by the appropriate IGP instance in the node 300 to the appropriate network 316 or 332 as a whole. Specifically, a local IGP instance relating to the lower network 332 distributes information about the upper network 316 via Type 5 LSA announcements to the lower network 332. Similarly, a local IGP instance relating to the upper network 316 distributes information about the lower network 332 via Type 5 LSA announcements to the upper network 316.

[0039] Autonomous systems may be configured as aggregations in various ways. One exemplary aggregation is indicated generally in FIG. 6 by reference number 400. The aggregation 400 may be, for example, a MANET in communication with a remote AS (not shown). Two lower networks 424 of the aggregation 400 each include a local backbone 428 linking one or more subnets 432. The backbones 428 are hierarchically meshed with a backbone 436 of an upper network 440. Each of a plurality of nodes in the backbones 428 and 436 includes a plurality of channels as previously discussed with reference to FIG. 2 to provide a plurality of channel interfaces 438. Each interface 438 is associated with a corresponding LSDB as previously discussed with reference to FIG. 5. The MANET 400 communicates via a BGPv4 interface 442 with the remote AS (not shown).

[0040] Another exemplary aggregation is indicated generally in FIG. 7 by reference number 500. The aggregation 500 may be, for example, aggregated MANET networks in communication with a remote AS (not shown). Three lower networks 524 each include a local backbone 528 linking one or more subnets 532. The local backbones 528 are meshed with a joint backbone 536 of an upper network 540 such that any one of the lower networks can communicate with any other lower network 524 via the joint backbone 536 and channel interfaces 542. The MANET 500 communicates via a BGPv4 interface 544 with the remote AS.

[0041] The aggregation 500 provides more backbone interfaces 542 and associated LSDB instances than the aggregation 400 (shown in FIG. 6). Compared to nodes (not shown in FIG. 6) of the backbone 436, nodes (not shown in FIG. 7) of the backbone 536 have greater channel capabilities to support the interfaces 542. Thus, although the aggregations 500 and 400 both include upper and lower networks, more networks can be linked together in the aggregation 500 than in the aggregation 400.

[0042] It is not necessary for all backbone 536 nodes to provide IP interfaces, with associated IGP instances, to all linked backbone 528 nodes. Where each backbone 536 node has an IP interface link to the joint backbone 536 subnetwork, then a given backbone 536 node can have links to fewer than all backbones 528. Thus, in the present exemplary configuration, backbone nodes 536 cumulatively, but not necessarily individually, have links to all of the connected backbones 528 and 536.

[0043] It also should be understood that at least some routers (not shown in FIG. 7) of a given backbone 528 function in the same or a similar manner as an OSPF ABR relative to one or more subnets 532 within other areas (not shown in FIG. 7) of the network 524 that includes the given backbone 528. Such routers may or may not be nodes configured as described with reference to FIG. 5. Where a router is configured in both of the foregoing ways, it operates the same as or similar to an OSPF ABR only with respect to one network 524 but can operate as described with reference to FIG. 5 with respect to a plurality of networks 524.

[0044] Generally, the present concept of upper and lower networks is a logical concept that occurs locally within each node configured as described with reference to FIG. 5. Therefore, it is possible to define mesh topologies in which a single network is a lower network relative to a second network and an upper network relative to a third network. An aggregation configured in accordance with the foregoing discussion is indicated generally in FIG. 8 by reference number 600. The aggregation 600 may be, for example, a MANET or a wired network in communication with a remote AS (not shown). Three networks 624a-c each include a backbone 628 linking one or more subnets 632. The network 624b is a lower network relative to the network 624c and is an upper network relative to the network 624a. The network 624a is a lower network relative to both networks 624b and 624c.

[0045] The backbones 628 are fully meshed with one another. Therefore the aggregation 600 is less subject to communication bottleneck occurrences than the aggregations 400 and 500. Additionally, the aggregation 600 includes a plurality of BGPv4 interfaces 640 with the remote AS located in different backbones, in contrast to the aggregation 500 (shown in FIG. 7) in which BGP interfaces are associated solely with the joint backbone 536. Each BGP interface 640 is associated with a different network 624. Therefore no single point of failure exists in the aggregation 600 with respect to communication with the remote AS (not shown). That is, if one interface 640 were to fail, another interface 640 could be used.

[0046] It is possible to configure nodes to include interfaces to two or more networks. The term “coalition network” is used to refer to a domain that includes a plurality of defined routing policies, i.e., a plurality of networks sharing similar policies (e.g., similar security and QoS policies) under the same high-level authority (e.g., a governmental entity). It is possible to configure coalition networks as aggregations having more than two tiers. One such aggregation is indicated generally in FIG. 9 by reference number 700. The aggregation 700 includes a plurality of networks 724 configured hierarchically as a plurality of tiers 728, three of which are shown. The tiers 728 are formed as described with reference to FIGS. 1-8. It should be understood that although the tiers 728 are referred to in FIG. 9 as “first”, “second” and “third” tiers, other tiers could be present in the aggregation 700 although not shown in FIG. 9.

[0047] Generally, OSPF Area IDs (AIDs) of networks within an aggregation are disjoint. That is, AIDs are local to a network and are not visible outside of that network within the aggregation. At a base routing level of IGP abstraction within a node, an IGP instance operates in the same or similar manner as IGP as implemented and deployed in known Internet environments.

[0048] Within an aggregation in accordance with principles of the invention, each network address (i.e., each Internet Protocol (IP) address) is global within that aggregation and belongs to the same IP address space. For example, all addresses operate at the same classification level. Network address translators (NATs) do not exist in one configuration of an aggregation. In an alternative configuration, NATs may be deployed in such a manner that their existence is transparent to the aggregation. Aggregated networks share a single AS number. That is, an aggregation forms a single AS and thus has its own AS number. BGPv4 operates in the traditional manner with respect to an aggregation and with respect to ASes outside the aggregation.

[0049] Embodiments of aggregations may be used to provide mesh relationships among networks sharing similar QoS (quality of service) and security policies. Configurations of aggregations can be used in various Internet configurations, including but not limited to IPv6. Operation of aggregations is transparent from the standpoint not only of BGPv4, but also from the standpoint of various EGPs that could be used to provide Internet connections, including but not limited to Multi-protocol Border Gateway Protocol (MBGP).

[0050] When implemented in connection with mobile networks, configurations of the present invention can make it possible for such networks to continue operating during dynamic network redefinition. Embodiments of the present invention can provide a mechanism by which highly mobile networks can be flexibly combined into larger network groupings that support comparatively dynamic mesh interfaces with each other. Multiple peers can be defined between networks that can maintain communications between the networks whenever any communicating peer in one network is within transmission range of any peer in the other network.

[0051] BGPv4 requires that all communications between ASes occur across a small set of (often one or two) well-known, pair wise interfaces. This requirement can result in both a single point of failure and a communications bottleneck for highly mobile environments. In a tactical military environment, effects of attrition (i.e., destruction) of such interfaces could result in communication failure between ASes. However, such events can also occur through movement or signal attenuation or loss. For this reason, pair-wise interfaces generally are inappropriate to link highly mobile environments together. Aggregations and mesh configurations can alleviate these vulnerabilities and can prevent communication bottlenecks.

[0052] The foregoing mesh configurations can alleviate a multi-homing problem currently associated with BGPv4. When an AS connects to two different Internet Service Providers (ISPs), the AS is said to be “multi-homed” because there are two different paths by which remote entities may communicate with the AS (i.e., through either of the connecting ISPs). Multi-homing is performed so that communications to the AS may continue in the event of a network failure within one of its supporting ISPs. Unfortunately, problems can arise within highly mobile environments, such as MANET networks, where network relationships are potentially continually changing. These problems can be resolved by establishing mesh interfaces between AS entities, potentially including multiple autonomous systems that perform ISP-like services (e.g., satellite networks).

[0053] The foregoing aggregations and mesh interfaces provide a solution that supports both stable (e.g., wire line networks) and highly mobile (e.g., wireless MANET networks) environments, permitting the two to cleanly interoperate together. Configurations of the invention provide a solution to avoid rapid redefinition of a mobile AS when changing signal receptivity causes the network to segment or recombine and to thereby alter mobile network memberships.

[0054] The foregoing aggregations and mesh configurations free a MANET from being required to operate either as a standalone network or as a stub network within a larger infrastructure in order to operate efficiently. A MANET operating as a stub previously was constrained to operate via a few well-defined pair-wise interfaces, and routing information had a high probability of being lost should any of the interfaces move out of range of each another. Now, however, a MANET can be un-tethered and can grow extremely large when implemented in accordance with principles of the present invention.

[0055] While various preferred embodiments have been described, those skilled in the art will recognize modifications or variations which might be made without departing from the inventive concept. The examples illustrate the invention and are not intended to limit it. Therefore, the description and claims should be interpreted liberally with only such limitation as is necessary in view of the pertinent prior art.