Methods and Apparatus for Distribution of IP Layer Routing Information in Peer-to-Peer Overlay Networks

BACKGROUND

00011. Field

0002The present application relates generally to the operation of overlay networks, and more particularly, to methods and apparatus for distribution of IP layer routing information in peer-to-peer overlay networks.

00032. Background

0004A network in which member nodes obtain services in the absence of server-based infrastructure is referred to herein as a “peer-to-peer” overlay network. In a peer-to-peer overlay, peer nodes co-operate with each other both to provide services and to maintain the network. Peer-to-peer overlay networks can be built on top of an underlying network, such as a network utilizing the Internet Protocol (IP).

0005Peer-to-peer networks based on Distributed Hash Tables (DHTs) use a form of key-based routing in which keys are randomly determined by a hash function. This means that two nodes which are adjacent in a peer-to-peer overlay may be in unrelated IP networks, may be behind Network Address Translation (NAT) technology or firewalls, or may have otherwise impaired reachability. One way to improve the routing available in those conditions is to configure tunnels that interconnect portions of the IP layer topology. Once a tunnel has been configured or the preferred route determined however, the information on its availability or the preference must be distributed. One way to distribute the information is to configure a separate service or attempt to re-use IP-layer routing announcements (e.g. BGP, RIP or Proxy ARP). However, these techniques usually are administratively prohibited or the information may be inappropriately propagated.

0006There are several traditional approaches to solving the above stated problems. One technique provides network topology information associated with an ISP or enterprise to peer-to-peer clients so as to minimize network traversal during media distribution. Such a distribution mechanism is external to the peer-to-peer network, however, and uses a polling mechanism for updates.

0007Therefore, it would be desirable to have a simple cost effective mechanism that operates to allow communication between nodes of disjoint subnets.

SUMMARY

0008In one or more aspects, a Multi-link Subnet Interchange (MSI) system is provided that operates to provide communications across disjoint IP subnets and/or private IP subnets. In various aspects, a node participating in an overlay network which wishes to make available information about IP-layer reachability creates searchable resources within the overlay to describe a new route (e.g. tunnel end point) or new information about an existing route. If the DHT permits, this information may also be “published” or “announced” as available, so that other nodes are aware of it. Whether published or searchable within an overlay context, this information allows participating nodes to establish routes to nodes which would otherwise have been unreachable or to establish better routes thereby avoiding having to configure a separate service or attempting to re-use IP layer routing announcements.

0009In an aspect, a method is provided for operating a provider node to provide communication between first and second disjoint networks. The method comprises transmitting an advertisement to a first subnet advertising the accessibility of one or more subnets, wherein for each of the one or more subnets the advertisement comprises an address and a unique subnet identifier, and wherein the unique subnet identifiers disambiguate overlapping addresses, and receiving a request from a first network comprising the first subnet to establish communications with a second network comprising the second subnet, wherein the request identifies the first and second subnets by their associated addresses and subnet identifiers. The method also comprises establishing a first tunnel with the second subnet and a second tunnel with the first subnet, and directing transmissions between the first and second tunnels based on policy information to allow communications between the first network comprising the first subnet and the second network comprising the second subnet.

0010In an aspect, an apparatus is provided for use at a provider node to provide communication between first and second disjoint networks. The apparatus comprises a transceiver configured to transmit an advertisement to a first subnet advertising the accessibility of one or more subnets, wherein for each of the one or more subnets the advertisement comprises an address and a unique subnet identifier, and wherein the unique subnet identifiers disambiguate overlapping addresses, the transceiver further configured to receive a request from a first network comprising the first subnet to establish communications with a second network comprising the second subnet, wherein the request identifies the first and second subnets by their associated addresses and subnet identifiers. The apparatus also comprises a processor configured to establish a first tunnel with the second subnet and a second tunnel with the first subnet and further configured to direct transmissions between the first and second tunnels based on policy information to allow communications between the first network comprising the first subnet and the second network comprising the second subnet.

0011In an aspect, an apparatus is provided for use at a provider node to provide communication between first and second disjoint networks. The apparatus comprises means for transmitting an advertisement to a first subnet advertising the accessibility of one or more subnets, wherein for each of the one or more subnets the advertisement comprises an address and a unique subnet identifier, and wherein the unique subnet identifiers disambiguate overlapping addresses, and means for receiving a request from a first network comprising the first subnet to establish communications with a second network comprising the second subnet, wherein the request identifies the first and second subnets by their associated addresses and subnet identifiers. The apparatus also comprises means for establishing a first tunnel with the second subnet and a second tunnel with the first subnet, and means for directing transmissions between the first and second tunnels based on policy information to allow communications between the first network comprising the first subnet and the second network comprising the second subnet.

0012In an aspect, a computer program product is provided for use at a provider node to provide communication between first and second disjoint networks. The computer program product comprises a computer-readable medium embodying codes executable to transmit an advertisement to a first subnet advertising the accessibility of one or more subnets, wherein for each of the one or more subnets the advertisement comprises an address and a unique subnet identifier, and wherein the unique subnet identifiers disambiguate overlapping addresses, and receive a request from a first network comprising the first subnet to establish communications with a second network comprising the second subnet, wherein the request identifies the first and second subnets by their associated addresses and subnet identifiers, The computer-readable medium also embodies codes executable to establish a first tunnel with the second subnet and a second tunnel with the first subnet, and direct transmissions between the first and second tunnels based on policy information to allow communications between the first network comprising the first subnet and the second network comprising the second subnet.

0013In an aspect, a method is provided for operating a node in at least one of a subnet and a peer-to-peer overlay network to communicate with disjoint networks. The method comprises receiving information identifying an address and a unique subnet identifier for each of one or more subnets in addition to identifying a provider node, wherein the unique subnet identifiers disambiguate overlapping addresses, and identifying a selected subnet for communications to a correspondent node, wherein the correspondent node is in a disjoint network that comprises the selected subnet. The method also comprises transmitting a request to the provider node, wherein the request identifies the selected subnet by its associated address and subnet identifier, establishing a tunnel to the provider node, and communicating with the correspondent node using the tunnel based on policy information.

0014In an aspect, an apparatus is provided for use at a node in at least one of a subnet and a peer-to-peer overlay network to communicate with disjoint networks. The apparatus comprises means for receiving information identifying an address and a unique subnet identifier for each of one or more subnets in addition to identifying a provider node, wherein the unique subnet identifiers disambiguate overlapping addresses, and means for identifying a selected subnet for communications to a correspondent node, wherein the correspondent node is in a disjoint network that comprises the selected subnet. The apparatus also comprises means for transmitting a request to the provider node, wherein the request identifies the selected subnet by its associated address and subnet identifier, means for establishing a tunnel to the provider node, and means for communicating with the correspondent node using the tunnel based on policy information.

0015Other aspects will become apparent after review of the hereinafter set forth Brief Description of the Drawings, Description, and the Claims.

BRIEF DESCRIPTION OF THE DRAWINGS

0016The foregoing aspects described herein will become more readily apparent by reference to the following Description when taken in conjunction with the accompanying drawings wherein:

0017<figref idrefs="DRAWINGS">FIG. 1</figref> shows a network that illustrates aspects of a MSI system;

0018<figref idrefs="DRAWINGS">FIG. 2</figref> shows an exemplary MSIS-P for use at a node in aspects of a MSI system;

0019<figref idrefs="DRAWINGS">FIG. 3</figref> shows an exemplary MSIS-R for use at a node in aspects of a MSI system;

0020<figref idrefs="DRAWINGS">FIG. 4</figref> shows exemplary advertisement messaging for use in aspects of a MSI system;

0021<figref idrefs="DRAWINGS">FIG. 5</figref> shows exemplary tunnel formation messaging for use in aspects of a MSI system;

0022<figref idrefs="DRAWINGS">FIG. 6</figref> shows an exemplary method for operating a MSIS-P to provide aspects of a MSI system;

0023<figref idrefs="DRAWINGS">FIG. 7</figref> shows an exemplary method for operating a MSIS-R to provide aspects of a MSI system;

0024<figref idrefs="DRAWINGS">FIG. 8</figref> shows an exemplary MSIS-P for use in aspects of an MSI system; and

0025<figref idrefs="DRAWINGS">FIG. 9</figref> shows an exemplary MSIS-R for use in aspects of an MSI system.

DESCRIPTION

0026The following description describes aspects of a MSI system that operates to provide communications across disjoint IP subnets. IP subnets are disjoint when it is not possible to route datagrams between them because they have an overlapping address space or other address ambiguities. Disjoint subnets may arise from using different link-layer technologies like Wi-Fi and Ethernet, Virtual Private Networks (VPNs) or NAT technology.

0027<figref idrefs="DRAWINGS">FIG. 1</figref> shows a network <b>100</b> that illustrates aspects of a MSI system. The network <b>100</b> comprises an Internet Protocol network. Although the network <b>100</b> is shown as a single entity, the network <b>100</b> may comprises any number or types of networks such as WANs, LANs, wireless networks or any other type of network.

0028The network <b>100</b> comprises subnet A <b>102</b> and subnet B <b>104</b>, which are disjoint subnets. For example, the nodes of subnet A are not reachable by the nodes of subnet B, and vice versa, which is indicated by the arc <b>126</b>. Each subnet may comprise one or more peer-to-peer overlay networks that include a subset of nodes of the network <b>100</b>. For example, node <b>106</b> is configured for communications in a disjoint network that comprises subnet A. Similarly, node <b>108</b> is configured for communications on a disjoint network that comprises subnet B. Node <b>110</b> also operates on the network <b>100</b> and is configured for communications with both subnet A and subnet B.

0029As part of the MSI system, the node <b>110</b> comprises MSI system provider (MSIS-P) <b>112</b>, which has multiple and simultaneously usable interfaces allowing it to communicate with multiple subnets. For example, the MSIS-P <b>112</b> comprises interfaces allowing simultaneous communication with subnets A and B. In another part of the MSI system, the node <b>106</b> comprises MSI system requestor (MSIS-R) <b>114</b> that is configured to allow the node <b>106</b> to request the services of the MSIS-P <b>112</b> to communicate with nodes of disjoint subnets. In addition, the node <b>108</b> comprises MSI system correspondent (MSIS-C) <b>116</b> that is configured to allow the node <b>106</b> to receive the services of the MSIS-P <b>112</b> to communicate with nodes of disjoint subnets. It should also be noted that a node may have both the MSIS-R <b>114</b> and MSIS-C <b>116</b> and that the MSIS-R <b>114</b> and MSIS-C <b>116</b> may also be combined into a single logical unit. Thus, for the purpose of this description, the node <b>106</b> will be referred to as comprising the MSIS-R <b>114</b> but it should also be noted that the node <b>106</b> may also comprise the MSIS-C <b>116</b>. The same is true of node <b>108</b>.

0030In various aspects, the MSI system operates to tunnel and forward packets between disjoint subnets to increase reachability and increase network access. To do this, the MSI system allows nodes in one subnet to learn of overlays in MSIS-reachable subnets and subsequently join those overlays.

0031The MSI system comprises a protocol for interaction between the MSIS-R <b>114</b>, MSIS-P <b>112</b>, and MSIS-C <b>116</b>. This protocol comprises two parts, namely; MSIS Advertisement protocol and MSIS Tunneling protocol. The MSIS-P <b>112</b> uses the MSIS Advertisement protocol to advertise its capabilities to enable nodes to join overlays in disjoint subnets. The MSIS-P <b>112</b> uses the MSIS Tunneling protocol to establish tunnels to encapsulate the datagrams communicated between nodes of disjoint networks.

Example of MSIS Operation

0032The following is an example illustrating the operation of the MSIS-P <b>112</b> to utilize the advertising and tunneling protocols to provide operations of the MSI system.

0033It will be assumed that the MSIS-P <b>112</b> is coupled to communicate with nodes of the two subnets (A and B). It will further be assumed that the node <b>106</b> of subnet A wants to join an overlay network on subnet B. The interface addresses of MSIS-P <b>112</b> on the subnets A and B are MSIS-P-AddrA and MSIS-P-AddrB, respectively.

Obtaining Subnet Identifiers

0034The MSIS-P <b>112</b> operates to obtain subnet identifiers and maintain a database comprising the subnet identifier information. For example, the MSIS-P <b>112</b> listens for any possible MSIS advertisements (as indicated at <b>118</b>) received through any of its interfaces before using its interfaces to transmit its own advertisements. This ensures that multiple MSIS-Ps will likely name each available subnet with the same overlay subnet identifier (OverlaySubnetId). Hence, these identifiers are universally unique identifiers. It should also be noted that it is possible for the same subnet to be assigned different OverlaySubnetIds by different MSIS-Ps. It is also possible to have multiple overlays in the same subnet as well as overlays spanning multiple subnets.

0035The MSI system operates so that the IP addresses used in the MSIS protocol will be disambiguated by the subnet identifiers. For example, the MSIS-P <b>112</b> can identify an IP address of a node in subnet B as OverlaySubnetB:IPX and advertise it on subnet A through MSIS-P-AddrA. Nodes in subnet A can then contact MSIS-P-AddrA to communicate with OverlaySubnetB:IPX. These overlay subnet identifiers represent two subnets from the point of view of the MSIS-P <b>112</b>, but are in the context of the overlays that span all of network <b>100</b>. These identifiers can equivalently be called subnet disambiguating identifiers. An overlay identifier or a concatenation of the overlay identifiers can also be used as a disambiguating identifier. The MSI system addresses the fact that multiple subnets having conflicting IP addresses may exist. Therefore, the disambiguation is used to route packets correctly. In an aspect, the MSIS-P <b>112</b> operates to assign the identifiers. However, the system may be extended so that another entity, which provides services across subnets, operates to provide the overlay subnet identifiers through advertisements. Regardless of which entity does the assignment, data structures and fields are defined to store overlay subnet identifiers along with IP addresses.

0036In the MSI system, GRE tunneling is used for encapsulating packets intended for transmission between subnets sent through the MSIS-P <b>112</b>. Setting up the GRE tunnel requires a tunnel setup mechanism. Policy routing is used after the tunnel setup mechanism so that a combination of the incoming GRE interface and the destination IP address can be used to determine the outgoing GRE interface. The state associated with the interface is created by a tunnel setup protocol performed by the MSIS-P <b>112</b>.

0037The MSIS system described herein is in the context of overlays, since the MSIS-R <b>114</b> joins various overlays through MSIS-P <b>112</b>. However, the system can easily be extended to provide services through MSIS-P <b>112</b>, whereby the MSIS advertisement contains information about the services available on overlay subnet B and a node (MSIS-C <b>116</b>) which provides the services. The MSIS-R <b>114</b> can request MSIS-P <b>112</b> to form a tunnel to communicate with MSIS-C <b>116</b> and thereby use the services offered by MSIS-C <b>116</b>.

MSIS Advertisement

0038The MSIS-P <b>112</b> starts by advertising (as indicated at <b>120</b>) the availability of overlays and the services it can provide from one disjoint subnet to the other. If the MSIS-P <b>112</b> is not implementing any startup mechanism, it can send an AdvertiseMSIS messages periodically at an interval called Minimum Advertisement Time Window. This parameter is configurable and may typically have an upper bound of fifteen seconds. The format of the advertisements is provided in another section of this document.

0039The AdvertiseMSIS messages contain an overlay description list (OverlayDescriptionList) data structure as the payload, which contains overlay description data structures. The overlays whose descriptions are being sent will be all of (or a subset of) the overlays in a Known Overlay Table for the subnet which is being made reachable. There may also be an additional requirement on each overlay description data structure to have either the fields of an Enrollment Server or the Bootstrap peers present.

0040The MSIS-P <b>112</b> advertises even if the OverlayDescriptionList is empty, so that the nodes on each of the subnets it is connected to are informed of their respective overlay subnet identifiers. For example, the MSIS-P <b>112</b> sends out the AdvertiseMSIS messages as illustrated at <b>120</b>. The AdvertiseMSIS messages also contain the OverlaySubnetId qualified IP address of MSIS-P's interface at which it should be contacted to contact the advertised overlays through it. This serves the purpose of communicating the subnet identifier to the MSIS-R <b>114</b>. For example, if the AdvertiseMSIS message <b>120</b> contains OverlaySubnetA:MSIS-P-AddrA, then OverlaySubnetA is the subnet identifier of the subnet in which MSIS-R <b>114</b> belongs. The MSIS-R <b>114</b> then knows it does not need to use MSI to connect to another address it learns from an overlay that resides in OverlaySubnetA.

0041Before sending a MSIS Advertisement through an interface, the MSIS-P <b>112</b> listens for some random time, at least for 15 seconds (upper bound of Minimum Advertisement Time Window). If it hears of other MSIS Advertisements (i.e., <b>118</b>) that name the subnet that the interface is connected to as some OverlaySubnetId, it chooses the same OverlaySubnetId for the subnet on which the advertisement is being sent out. If it doesn't hear any Advertisement, it randomly generates an OverlaySubnetId (which in one implementation is at least 128 bits long to ensure virtually no conflicts) and uses that as the subnet identifier. For example, the subnet identifiers are generated in accordance with ISO/IEC 11578:1996. The same mechanism is used to name the subnet that is being made reachable. The uniqueness of the identifiers is used for communicating unambiguously to nodes on the other subnet.

0042On receipt of a MSIS Advertisement, the information from the message is also used to create entries in a Known Overlay Table. This is similar to the action taken on receipt of an Overlay Advertisement. The only difference is that in the case of MSIS Advertisement, the Advertiser_Address in the Known Overlay Element is filled using a third field (OverlaySubnetA:MSIS-P-AddrA) of the message as described in another section below.

MSIS Tunneling

0043The MSIS Tunneling protocol presented here provides for GRE tunnels to be formed to route packets into disjoint networks. There is a tunnel setup and refresh protocol that is used by the MSIS-R <b>114</b> to setup and maintain tunnels.

0044One of the goals of the MSI system is to provide packet forwarding without support from the connectivity layer of the protocol stack. The connectivity layer is the layer containing tunneling support and is involved in the tunnel formation process. This immediately precludes the use of IP-IP tunneling since same the IP addresses in different subnets cannot be disambiguated. In an aspect, GRE is used as the tunneling mechanism so that virtual interfaces can be created in conjunction with OverlaySubnetId's to provide enough information in the routing table for correct packet forwarding. To achieve this goal, the MSIS-P <b>112</b> maintains policy routing state in its IP routing table. Although the MSIS-P <b>112</b> operates to forward packets from one subnet to the other, it is much more than a router since it makes disjoint subnets reachable at a higher level by providing access to services through overlays.

0045The MSIS-R <b>114</b> requests GRE tunnels to communicate with MSIS-C <b>116</b> through MSIS-P <b>112</b>. Specifically, the connectivity layer initiates tunnel formation whenever any communication is initiated with an OverlaySubnetId qualified IP address. This results in creation of a first tunnel <b>122</b> between the MSIS-P <b>112</b> and the MSIS-C <b>116</b> and a second tunnel <b>124</b> between the MSIS-R <b>114</b> and the MSIS-P <b>112</b>. The tunnels are maintained using Tunnel Refresh messages sent by MSIS-R <b>114</b> which refresh the two GRE tunnels (<b>122</b>, <b>124</b>) together.

0046In an aspect, the Connection Table is modified at the connectivity layer to include an additional field called tunnel identifier (TunId). This is an index to an additional data structure called the TunnelTable maintained by the connectivity layer. Every GRE tunnel maintained at a node will be assigned a Tunnel Identifier and every connection will be associated with a TunId. For the connections that do not use GRE tunnels, the TunId will be ‘invalid’ (for example, a value of 0). ‘Valid’ TunId's will be assigned locally from a pool of TunId's, presumably non-zero natural numbers.

0047In an aspect the system provides a way to create a connection identifier (ConnectionId). A call CreateConnection( ) is provided, which in its simplest form will choose a ConnectionId from a pool of available identifiers and return the ConnectionId while creating a new entry in its ConnectionTable and initializing the TunId to 0 or the ‘invalid value’. This API can be modified as CreateConnection(TunId) which would insert the TunId supplied as an argument into the corresponding field in the ConnectionTable when it creates an entry for the connection.

0048After MSIS-R <b>114</b> joins the Overlay and wishes to make connections with other nodes in the overlay, it utilizes any suitable rendezvous mechanism, such as ICE. The ambiguity of IP addresses causes ICE candidates to be ambiguous. To avoid this, the MSIS-R <b>114</b> adds another ‘tunneled’ ICE candidate OverlaySubnetIdA:MSIS-R-AddrA to its ICE candidates list. The tunneled candidate uses the overlay subnet identifier of the subnet to which MSIS-R-AddrA belongs. The node still uses the host candidate and assigns it a higher priority than the tunneled candidate. This ensures that if a direct connection to a node is available, it would be used first rather than going through the MSIS-P <b>112</b>. It is also worth noting that even if the MSIS-C's <b>116</b> IP exists in OverlaySubnetA when MSIS-R <b>114</b> does ICE checks on the host candidate, the ICE checks will not succeed as the node with MSIS-C's <b>116</b> IP won't have a valid fingerprint (nonce) attribute. Whenever ICE connectivity checks happen at node B to a Tunneled Candidate, say OverlaySubnetIdX:NodeY, node B sends a request to the MSIS-P <b>112</b> for a tunnel to OverlaySubnetIdX:NodeY using the tunnel formation mechanism explained below. The MSIS-P <b>112</b> is the one that had advertised the OverlaySubnetIdX as a subnet which it can make reachable and this information can be found by looking up the Known Overlay Table. The tunnel once formed is used for connectivity checks which should succeed if no errors have been encountered in the tunnel formation process.

0049Thus, the MSI system operates to provide communications across disjoint IP subnets, thereby providing a means for packets from nodes in one subnet to reach nodes in a disjoint subnet in an easy and efficient manner.

0050<figref idrefs="DRAWINGS">FIG. 2</figref> shows an exemplary MSIS-P <b>200</b> for use at a node in aspects of a MSI system. For example, the MSIS-P <b>200</b> is suitable for use as the MSIS-P <b>112</b> shown in <figref idrefs="DRAWINGS">FIG. 1</figref>. The MSIS-P <b>200</b> comprises processor <b>202</b>, memory <b>204</b>, and transceiver <b>206</b> all coupled to communicate over data bus <b>208</b>. It should be noted that the MSIS-P <b>200</b> is just one implementation and that other implementations are possible.

0051The transceiver <b>206</b> comprises hardware and/or hardware executing software that operates to allow the MSIS-P <b>200</b> to receive advertisements or other information about available subnets on a first communication channel <b>210</b>. For example, the first communication channel <b>210</b> may be a WLAN channel that allows the MSIS-P <b>200</b> to receive advertisement about available subnets on an IP network. The advertisement may include universally unique subnet identifiers.

0052The transceiver <b>206</b> also comprises hardware and/or hardware executing software that operates to provide a plurality of interfaces <b>212</b> over which the MSIS-P <b>200</b> can communicate with a plurality of subnets. For example, the transceiver <b>206</b> utilizes the interfaces <b>212</b> to communicate with the subnets using WiFi, Bluetooth, cellular transmission or any other type of communication technology. In an aspect, the transceiver <b>206</b> is operable to transmit advertisements to various subnets and receive messaging from the various subnets utilizing the interfaces <b>212</b>. The interfaces <b>212</b> are operable further to provide tunnels between the transceiver <b>206</b> and the various subnets. For example, the tunnels may be GRE tunnels or other suitable types of tunnels.

0053The memory <b>204</b> comprises any suitable storage device operable to store a subnet database <b>216</b> comprising information identifying and/or associated with one or more subnets that the MSIS-P <b>200</b> is aware of.

0054The memory <b>204</b> also comprises MSI module <b>214</b> which comprises one or more modules comprising instructions or codes executable by the processor <b>202</b> to provide the functions of the MSI system described herein.

0055The processor <b>202</b> comprises at least one of a CPU, processor, gate array, hardware logic, memory elements, and/or hardware executing software. In an aspect, the processor <b>202</b> operates to execute instructions of the MSI module <b>214</b> to control the MSIS-P <b>200</b> to perform the functions of the MSI system described herein. A more detailed description of the operation of the MSIS-P <b>200</b> is provided in other sections of this document.

0056During operation the MSIS-P <b>200</b> performs one or more of the following functions. <ul><li id="ul0001-0001" num="0057">1. Identify subnets (i.e., receive advertisements through channel <b>210</b>).</li><li id="ul0001-0002" num="0058">2. Generate disambiguating subnet identifiers associated with each subnet.</li><li id="ul0001-0003" num="0059">3. Generate advertisements identifying known subnets and their associated subnet identifiers.</li><li id="ul0001-0004" num="0060">4. Transmit advertisements to subnets (using interfaces <b>212</b>)</li><li id="ul0001-0005" num="0061">5. Receive requests to form tunnels between nodes of disjoint subnets (using interfaces <b>212</b>).</li><li id="ul0001-0006" num="0062">6. Establish the requested tunnels (using interfaces <b>212</b>).</li><li id="ul0001-0007" num="0063">7. Setup policy associated with the requested tunnels.</li><li id="ul0001-0008" num="0064">8. Receive and forward packets between tunnels based on the policy.</li></ul>

0065In an aspect, the MSI system comprises a computer program product having one or more program instructions (“instructions”) or sets of “codes” stored or embodied on a machine-readable medium. When the codes are executed by at least one processor, for instance, the processor <b>202</b>, their execution causes the MSIS-P <b>200</b> to provide the functions of the MSI system described herein. For example, the machine-readable medium comprises a floppy disk, CDROM, memory card, FLASH memory device, RAM, ROM, or any other type of memory device or machine-readable medium that interfaces to the MSIS-P <b>200</b>. In another aspect, the sets of codes may be downloaded into the MSIS-P <b>200</b> from an external device or communication network resource. The sets of codes, when executed, operate to provide the functions of a MSI system as described herein.

0066<figref idrefs="DRAWINGS">FIG. 3</figref> shows an exemplary MSIS-R <b>300</b> for use at a node in aspects of a MSI system. For example, the MSIS-R <b>300</b> is suitable for use as the MSIS-R <b>114</b> shown in <figref idrefs="DRAWINGS">FIG. 1</figref>. The MSIS-R <b>300</b> comprises processor <b>302</b>, memory <b>304</b>, and transceiver <b>306</b> all coupled to communicate over data bus <b>308</b>. It should be noted that the MSIS-R <b>300</b> is just one implementation and that other implementations are possible.

0067The transceiver <b>306</b> comprises hardware and/or hardware executing software that operates to allow the MSIS-R <b>300</b> to receive advertisements or other information about available subnets on a first communication channel <b>310</b>. For example, the first communication channel <b>310</b> may be a WLAN channel that allows the MSIS-R <b>300</b> to receive advertisement about available subnets on an IP network.

0068The transceiver <b>306</b> also utilizes the communication channel <b>310</b> to communicate with a host on a disjoint subnet. For example, the transceiver <b>306</b> utilizes the communication channel <b>310</b> to communicate with the disjoint subnet using a tunnel between the transceiver <b>306</b> and a host comprising MSIS-P, such as the MSIS-P <b>200</b> shown in <figref idrefs="DRAWINGS">FIG. 2</figref>. The tunnel may be a GRE tunnel or other suitable type of tunnel.

0069The memory <b>304</b> comprises any suitable storage device operable to store a subnet database <b>312</b> comprising information identifying and/or associated with one or more subnets that the MSIS-R <b>300</b> is aware of For example, the MSIS-R <b>300</b> may receive advertisements over the channel <b>310</b> that provide information about available subnets.

0070The memory <b>304</b> also comprises MSI module <b>314</b> which comprises one or more modules comprising instructions or codes executable by the processor <b>302</b> to provide the functions of the MSI system described herein.

0071The processor <b>302</b> comprises at least one of a CPU, processor, gate array, hardware logic, memory elements, and/or hardware executing software. In an aspect, the processor <b>302</b> operates to execute instructions of the MSI module <b>314</b> to control the MSIS-R <b>300</b> to perform the functions of the MSI system described herein. A more detailed description of the operation of the MSIS-R <b>300</b> is provided in other sections of this document.

0072During operation the MSIS-R <b>300</b> performs one or more of the following functions. <ul><li id="ul0002-0001" num="0073">1. Receive advertisements from MSIS-P identifying disjoint subnets and associated disambiguating identifiers (through channel <b>310</b>).</li><li id="ul0002-0002" num="0074">2. Identify a selected subnet to which communication is desired.</li><li id="ul0002-0003" num="0075">4. Transmit request to MSIS-P to establish tunnel to the selected subnet (using channel <b>310</b>)</li><li id="ul0002-0004" num="0076">4. Receive indication that the requested tunnel has been established (using channel <b>310</b>).</li><li id="ul0002-0005" num="0077">5. Set up policy for tunnel use.</li><li id="ul0002-0006" num="0078">6. Communicate with the selected subnet using the tunnel based on the policy.</li></ul>

0079In an aspect, the MSI system comprises a computer program product having one or more program instructions (“instructions”) or sets of “codes” stored or embodied on a machine-readable medium. When the codes are executed by at least one processor, for instance, the processor <b>302</b>, their execution causes the MSIS-R <b>300</b> to provide the functions of the MSI system described herein. For example, the machine-readable medium comprises a floppy disk, CDROM, memory card, FLASH memory device, RAM, ROM, or any other type of memory device or machine-readable medium that interfaces to the MSIS-R <b>300</b>. In another aspect, the sets of codes may be downloaded into the MSIS-R <b>300</b> from an external device or communication network resource. The sets of codes, when executed, operate to provide the functions of a MSI system as described herein.

MSI System Messages

0080The following is a description of message types used in various aspects of the MSI system. For example, the messages types described below are transmitted between the MSIS-R <b>114</b>, MSIS-P <b>112</b> and MSIS-C <b>116</b> shown in <figref idrefs="DRAWINGS">FIG. 1</figref> to provide the various aspects of the MSI system. It should be noted that the message list described below is not exhaustive and that additional messages types may be used. It should also be noted that the described message may be suitably modified to comprise more or less parameters within the scope of the various aspects.

AdvertiseMSIS( ) Message

0081AdvertiseMSIS messages are sent by MSIS-P <b>112</b> to advertise the availability of subnets, overlays and services that it can provide access to. For example, an AdvertisMSIS message is sent to the MSIS_R <b>114</b> and has the following fields. <ul><li id="ul0003-0001" num="0082">1. TunMechanism: The Tunneling Mechanism that will be used for a requestor (i.e., MSIS-R <b>114</b>) to exchange messages with nodes in other subnet through MSIS-P <b>112</b>. In this description, GRE is used as the tunneling mechanism.</li><li id="ul0003-0002" num="0083">2. OverlayDescriptionList: This contains multiple OverlayDescription data structures which describe the overlays and services available on Subnets that MSIS-P <b>112</b> knows about (i.e., subnet B). One implementation is that each OverlayDescription data structure should have either an Enrollment Server or a Bootstrap peer present. This field can be empty if no overlays are present on one of the subnets to which MSIS-P <b>112</b> is connected.</li><li id="ul0003-0003" num="0084">3. OverlaySubnetA:MSIS-P-AddrA: This is the IP address and port of MSIS-P <b>112</b> on subnet A. To use the MSI system and contact nodes in a disjoint overlay, MSIS-R <b>114</b> should contact MSIS-P-AddrA. The address is also qualified with the subnet identifier OverlaySubnetA. This identifier will be used by the nodes which hear this Advertisement to infer that they are in OverlaySubnetA as advertised by MSIS-P <b>112</b>.</li></ul>

RequestTunnel( ) Message

0085A RequestTunnel message is sent by a requestor (i.e., MSIS-R <b>114</b>) to an MSIS-P (i.e., MSIS-P <b>112</b>) that prompts the MSIS-P <b>112</b> to initiate tunnel formation with another node (Secondary Requestee) and create a tunnel between the MSIS-R <b>114</b> and MSIS-P <b>112</b> if none exists. The message has the following fields. <ul><li id="ul0004-0001" num="0086">1. OverlaySubnetId:RequestorAddress: This is the source address of the message, for example OverlaySubnetA:MSIS-R-AddrA.</li><li id="ul0004-0002" num="0087">2. OverlaySubnetId:RequesteeAddress: This is the destination address of the message, for example OverlaySubnetA:MSIS-P-AddrA.</li><li id="ul0004-0003" num="0088">3. OverlaySubnetId:SecondaryRequesteeAddress: This field gives information about the node to which the Requestee Node should establish a tunnel. The IP address of the ‘tunnel destination’ should be qualified with a disambiguating overlay subnet identifier, i.e., OverlaySubnetId.</li><li id="ul0004-0004" num="0089">4. Options: This field indicates possible options that can be included for the tunnel formation. For example, it can include authentication information that would enable the Requestee to verify if the sender of this message is authorized to request setting up the tunnel.</li></ul>

TunnelGranted( ) Message

0090A TunnelGranted message is sent by MSIS-P <b>112</b> to MSIS-R <b>114</b> in response to the RequestTunnel message. This message is sent after MSIS-P <b>112</b> has created a tunnel with OverlaySubnetId: SecondaryRequesteeAddress. <ul><li id="ul0005-0001" num="0091">1. OverlaySubnetId:RequestorAddress: This is the address of the node which requested the tunnel and hence the destination address of the message. For example, this field can be OverlaySubnetA:MSIS-R-AddrA.</li><li id="ul0005-0002" num="0092">2. OverlaySubnetId:RequesteeAddress: This is the address of the node which granted the tunnel request and hence is the source address of the message. For example, this field can be OverlaySubnetB:MSIS-P-AddrA.</li><li id="ul0005-0003" num="0093">3. OverlaySubnetId: SecondaryRequesteeAddress: This will be the end node with which the Requestee has set up a tunnel. For example, this can be the Bootstrap peer (BP).</li><li id="ul0005-0004" num="0094">4. TunnelIdentifyingInfo: This field contains some identifying information about the tunnel between the Requestor and the Requestee so that the Requestor can setup this tunnel at its end. The tunnel between the Requestor and Requestee may be preexisting or may be granted by this message. The identifying information can be the GRE key. The GRE key to be selected for a new tunnel may be predetermined or chosen randomly by the Requestee and sent to the Requestor.</li><li id="ul0005-0005" num="0095">5. Options: This field indicates possible options that can be included for the tunnel formation. This may be some authentication related information.</li></ul>

RequestGRETunnel( ) Message

0096A RequestGRETunnel message sent from a source node to a destination node explicitly requests a GRE Tunnel to be setup between the two nodes. For example, the MSIS-P <b>112</b> sends the message to the MSIS-C <b>116</b> to request formation of a GRE tunnel. The message has the following fields. <ul><li id="ul0006-0001" num="0097">1. OverlaySubnetId:RequestorAddress: This is the address of the node which requested the tunnel and the source address of the message.</li><li id="ul0006-0002" num="0098">2. OverlaySubnetId:RequesteeAddress: This is the address of the node which is being requested to create the tunnel and the destination address of the message.</li><li id="ul0006-0003" num="0099">3. OverlaySubnetId:OnBehalfofAddress: This is the address of the node on behalf of which this RequestGRETunnel message is being sent, i.e. this is the address of the node which will be sending packets to OverlaySubnetId:DestinationAddress using this GRE tunnel if the setup completes successfully. Sending this address in the message also sends the UniqueOverlaySubnetId implicitly.</li><li id="ul0006-0004" num="0100">4. Options: This field indicates possible options that can be included for the tunnel formation. For example, it can include authentication information that would enable the Requestee to verify if the sender of this message is authorized to request setting up the tunnel.</li></ul>

GRETunnelGranted( ) Message

0101A GRETunnelGranted message is sent from a node in response to RequestGRETunnel message if it agrees to setup a GRE tunnel. For example, the MSIS-C <b>116</b> sends the message to the MSIS-P <b>112</b> granting the formation of a GRE tunnel. The message has the following fields. <ul><li id="ul0007-0001" num="0102">1. OverlaySubnetId:RequestorAddress: This is the address of the node which requested the tunnel and hence the destination address of the message.</li><li id="ul0007-0002" num="0103">2. OverlaySubnetId:RequesteeAddress: This is the address of the node which granted the tunnel request and hence is the source address of the message.</li><li id="ul0007-0003" num="0104">3. OverlaySubnetId:OnBehalfofAddress: This is the address of the node on behalf of which this tunnel was requested by OverlaySubnetId:RequestorAddress. This field is copied from the corresponding field in the RequestGRETunnel message. This also sends the UniqueOverlaySubnetId implicitly to the Requestor.</li><li id="ul0007-0004" num="0105">4. TunnelIdentifyingInfo: This field contains some identifying information about the tunnel between the Requestor and the Requestee so that the Requestor can setup this tunnel at its end. The identifying information can be the GRE key. The GRE key to be selected for a new tunnel may be predetermined or chosen randomly by the Requestee and sent to the Requestor.</li><li id="ul0007-0005" num="0106">5. Options: This field indicates possible options that can be included for the tunnel formation acknowledgment. For example, it can include authentication related information.</li></ul>

TunnelRefresh( ) Message

0107TunnelRefresh Messages are sent by MSIS-R <b>114</b> to refresh the tunnels that have been formed using RequestTunnel message. This directly causes the tunnel between MSIS-R <b>114</b> and MSIS-P <b>112</b> to be refreshed. It also leads to the refresh of the tunnel between MSIS-P <b>112</b> and MSIS-C <b>116</b> indirectly when MSIS-P <b>112</b> sends GRETunnelRefresh Message. The message has the following fields. <ul><li id="ul0008-0001" num="0108">1. OverlaySubnetId:RequestorAddress: This is the source address of the message. For example, this field can be OverlaySubnetA:MSIS-R-AddrA.</li><li id="ul0008-0002" num="0109">2. OverlaySubnetId:RequesteeAddress: This is the destination address of the message. For example, this field can be OverlaySubnetA:MSIS-P-AddrA.</li><li id="ul0008-0003" num="0110">3. OverlaySubnetId:SecondaryRequesteeAddress: This field gives information about the node with which the Requestee Node has have a tunnel with. The IP address of the ‘tunnel destination’ should be qualified with a disambiguating overlay subnet identifier, OverlaySubnetId.</li><li id="ul0008-0004" num="0111">4. Options: This field indicates possible options that can be included for the tunnel formation. For example, it can include authentication information that would enable the Requestee to verify if the sender of this message is authorized to send the refresh messages.</li></ul>

GRETunnelRefresh( ) Message

0112A GRETunnelRefresh message is sent by a MSIS-P <b>112</b> when it receives a TunnelRefresh message from MSIS-R <b>114</b>. This message refreshes the tunnel that was formed between MSIS-P <b>112</b> and MSIS-C <b>116</b>. The message has the following fields. <ul><li id="ul0009-0001" num="0113">1. OverlaySubnetId:RequestorAddress: This is the source address of the message.</li><li id="ul0009-0002" num="0114">2. OverlaySubnetId:RequesteeAddress: This is the destination address of the message.</li><li id="ul0009-0003" num="0115">3. OverlaySubnetId:OnBehalfofAddress: This is the address of the node on behalf of which this GRE Tunnel Refresh message is being sent. Sending this address in the message also sends the UniqueOverlaySubnetId implicitly.</li><li id="ul0009-0004" num="0116">4. Options: This field indicates possible options that can be included for the tunnel formation. For example, it can include authentication information that would enable the Requestee to verify if the sender of this message is authorized to send the refresh messages.</li></ul>

Call Flow

0117This section describes the call flow for calls utilizing the MSI system to provide for tunnel formation. If the functionality to connect to any node in an overlay is successfully implemented, then other overlay functions like putting/getting data from the overlay and maintaining fingers can proceed as usual using overlay routing.

AdvertiseMSIS Messaging

0118<figref idrefs="DRAWINGS">FIG. 4</figref> shows exemplary advertisement messaging <b>400</b> for use in aspects of a MSI system. In an aspect, the MSIS-P <b>112</b> sends out AdvertiseMSIS messages and the impact of those messages on the nodes of two subnets is illustrated

0119The MSIS-P <b>112</b> sends out AdvertiseMSIS messages through each of its two interfaces. For example, the MSIS-P <b>112</b> has a first interface to MSIS-R <b>114</b> and a second interface to MSIS-C <b>116</b>. Before doing so, it waits for some amount of time (random time slightly greater than upper bound of Minimum Advertisement Time Window) to receive any AdvertiseMSIS messages to learn of any OverlaySubnetId's of the subnets it is connected to using the two interfaces. It reuses the OverlaySubnetIds, if any are determined from received MSIS Advertisements. Otherwise, MSIS-P <b>112</b> generates a random OverlaySubnetId for each subnet and uses that in the advertisements it sends out. The AdvertiseMSIS messages that are sent include OverlayDescriptionLists (A or B) representing the set of overlays that are reachable through the MSIS-P <b>112</b> on subnet (A or B). Also, the MSIS-P <b>112</b> includes its interface address where it can be reached using the tunnel mechanism identified in the AdvertiseMSIS messages. The interface addresses are qualified by using overlay subnet identifier which will be used by nodes at either end to learn this identifier.

0120The MSIS-R <b>114</b> on receiving the AdvertiseMSIS message stores state in the Known Overlay Table storing a tuple MSIS-R-OverlayDescriptionListB:InterfaceA-Current_Time-OverlaySubnetA:MSIS-P-AddrA in the table. Here, MSIS-R-InterfaceA is the IP address of the interface of MSIS-R (in Subnet A) on which the advertisement was received.

0121A tuple comprising at least the following information is stored. <ul><li id="ul0010-0001" num="0122">1. Service name (e.g. Address Family Interchange Service);</li><li id="ul0010-0002" num="0123">2. Publishing node;</li><li id="ul0010-0003" num="0124">3. Route destination (expressed in CIDR notation):</li><li id="ul0010-0004" num="0125">4. Destination network identifier (used to disambiguate networks using the same IP address ranges, such as private network as defined in IETF-RFC 1918);</li><li id="ul0010-0005" num="0126">5. Next hop (IF address and port of new tunnel endpoint, or the route for which metadata is being provided); and</li><li id="ul0010-0006" num="0127">6. Any metadata (e.g. rate of ECN messages received via this path). Whether published or searchable within an overlay context, this information allows participating nodes to establish routes to nodes which would otherwise have been unreachable or establish better routes.</li></ul>

Tunnel Formation Process

0128<figref idrefs="DRAWINGS">FIG. 5</figref> shows exemplary tunnel formation messaging <b>500</b> for use in aspects of a MSI system. The tunnel formation messaging is illustrated using the MSIS-R <b>114</b> attempting to contact an enrollment server on Subnet B (MSIS-C <b>116</b>) through the MSIS-P <b>112</b>. The tunnel formation process is set in motion when an application at the MSIS-R <b>114</b> desires to access an overlay advertised in the Known Overlay Table, and uses overlay middleware to assemble a CreateTunnel request to forward an ENROLL packet to the enrollment server reachable through the MSIS-P <b>112</b> Thus, the application calls the CreateTunnel API having the following format. <ul><li id="ul0011-0001" num="0000"><ul><li id="ul0012-0001" num="0129">CreateTunnel(OverlaySubnetId:RequestorAddress, <ul><li id="ul0013-0001" num="0130">OverlaySubnetId:RequesteeAddress,</li><li id="ul0013-0002" num="0131">OverlaySubnetId:SecondaryRequesteeAddress, Options).</li></ul></li></ul></li></ul>

0132The qualified IP addresses imply that a MSIS-P <b>112</b> has advertised this overlay and the MSIS-R <b>114</b> has determined from the Known Overlay Table which MSIS-P has advertised the OverlaySubnetId.

0133Tunnel formation can also be initiated when the MSIS-R <b>114</b> wants to contact a Bootstrap peer on OverlaySubnetB or when ICE connectivity checks are being done for a tunneled candidate. In the latter case, the following design stays the same, except for renaming of MSIS-R and ES with the two nodes that want to do ICE connectivity checks using tunneled candidate.

0134It should be noted that the tunnel formation process presented in this section can be extended to form a TCP connection between the MSIS-R <b>114</b> (Requestor) and MSIS-C <b>116</b> (Secondary Requestee). The RequestTunnel message can include the SYN message, the TunnelGranted message can include the SYN-ACK, and an ACK can be sent through the tunnel that has been formed. This section assumes that no tunnels exist between these nodes due to past interactions.

0135Referring now to <figref idrefs="DRAWINGS">FIG. 5</figref>, the following operations occur in the tunnel formation process.

0136At reference <b>502</b>, the MSIS-R <b>114</b> decides to join one of the overlays it knows about from the Known Overlay Table. It looks up the entry to find the IP address of the MSIS-P <b>112</b> which advertised the Overlay. In this case the address is OverlaySubnetA:MSIS-P-AddrA. The MSIS-R <b>114</b> then sends a RequestTunnel message to MSIS-P-AddrA as follows; <ul><li id="ul0014-0001" num="0000"><ul><li id="ul0015-0001" num="0137">RequestTunnel(OverlaySubnetA:MSIS-R-AddrA,OverlaySubnetA:MSIS-P-AddrA, OverlaySubnetB:ES, Options) <br /> where ES represents the address of the Enrollment Server for the particular overlay MSIS-R <b>114</b> want to join in subnet B and Options can include authentication information. </li></ul></li></ul>

0138It is important to note that this RequestTunnel message is sent even if a tunnel exists between MSIS-R <b>114</b> and OverlaySubnetA:MSIS-P-AddrA. This is because MSIS-P <b>112</b> uses this message to create a tunnel with OverlaySubnetB:ES. Any tunnels that exist between MSIS-R <b>114</b> and MSIS-P <b>112</b> with OverlaySubnetB as the UniqueOverlaySubnetId, and between MSIS-P <b>112</b> and ES <b>116</b> with OverlaySubnetA as the UniqueOverlaySubnetId will be reused.

0139At reference <b>504</b>, the MSIS-P <b>112</b> receives the RequestTunnel message and extracts the SecondaryRequesteeAddress which is OverlaySubnetB:ES. It then looks up its Tunnel Table to see if a tunnel already exists from itself to OverlaySubnetB:ES with OverlaySubnetA as the UniqueOverlaySubnetId. If yes and the request is already properly authenticated, the call flow proceeds to reference <b>508</b>, otherwise, MSIS-P <b>112</b> sends a RequestGRETunnel message as follows; <ul><li id="ul0016-0001" num="0000"><ul><li id="ul0017-0001" num="0140">RequestGRETunnel(OverlaySubnetA:MSIS-R-AddrA, OverlaySubnetB:MSIS-P-AddrB, OverlaySubnetB:ES, Options) <br /> where MSIS-P-AddrB is the address of the interface of MSIS-P <b>112</b> on Subnet B. </li></ul></li></ul>

0141The MSIS-P <b>112</b> also creates an entry in the Requested Tunnel Table with the OverlaySubnetA:MSIS-R-AddrA as the OverlaySubnetId:RequestingAddr and OverlaySubnetB:ES as the OverlaySubnetId:TunDestAddr and OverlaySubnetA as the UniqueOverlaySubnetId.

0142At reference <b>506</b>, the ES at MSIS-C <b>116</b> receives the RequestGRETunnel message and based on the options field (or other criteria) decides whether or not to grant the GRE tunnel. If the Enrollment Server grants the GRE Tunnel, it creates an entry in its Tunnel Table generating a new TunId and associating it with the tuple comprising OverlaySubnetB:ES as OverlaySubnetId:TunnelSrc and OverlaySubnetB:MSIS-P-AddrB as OverlaySubnetId:TunnelDest and OverlaySubnetA as the UniqueOverlaySubnetId and Network Interface as a new GRE interface say G<b>1</b>.

0143A corresponding GRE interface G<b>1</b> is also created at the GRE layer with its unique key and other associated identifiers. The ES at MSIS-C <b>116</b> then sends a GRETunnelGranted message to the MSIS-P-AddrB through regular IP routing as follows; <ul><li id="ul0018-0001" num="0000"><ul><li id="ul0019-0001" num="0144">GRETunnelGranted(OverlaySubnetA:MSIS-R-AddrA, OverlaySubnetB:MSIS-P-AddrB,OverlaySubnetB:ES, TunnelIdentifier, Options)</li></ul></li></ul>

0145If the ES refuses to grant the GRE Tunnel, it sends a Tunnel Refusal Message to MSIS-P <b>112</b>, which will be propagated back to MSIS-R <b>114</b>.

0146At reference <b>508</b>, the MSIS-P <b>112</b> receives the GRETunnelGranted message and it matches the fields in that message with Tunnel Requested Table. Specifically, it matches OverlaySubnetId:OnBehalfofAddress in the message with OverlaySubnetId:RequestingAddr in the table and OverlaySubnetId:RequesteeAddress in the message with OverlaySubnetId:TunDestAddr in the table and OverlaySubnetId of OverlaySubnetId:OnBehalfofAddress in the message with UniqueOverlaySubnetId in the table. If an entry is found, the MSIS-P <b>112</b> now knows that MSIS-R <b>114</b> requested this tunnel to be setup and a tunnel has been formed to satisfy the request.

0147Assuming a tunnel already exists between OverlaySubnetB:MSIS-P-AddrB and OverlaySubnetB:ES; then to remember this, the MSIS-P <b>112</b> creates an entry in its Tunnel Table, generating a locally unique TunId to identify the tunnel and storing the tuple TunId; OverlaySubnetB:MSIS-P-AddrB; OverlaySubnetB:ES; OverlaySubnetA; G<b>1</b>; in the Tunnel Table. Here G<b>1</b> is the virtual interface of the GRE tunnel created. The information about this interface (like the GRE key) is stored at the GRE layer so that the interface G<b>1</b> can be used in the future. MSIS-P <b>112</b> also deletes the corresponding entry from the Tunnel Requested Table.

0148The MSIS-P <b>112</b> then looks up the Tunnel Table to see if a Tunnel exists from its OverlaySubnetA interface (OverlaySubnetA:MSIS-P-AddrA) to OverlaySubnetA:MSIS-R-AddrA with OverlaySubnetB (extracted from Requestee address) as the unique OverlaySubnetId. If MSIS-P <b>112</b> discovers a tunnel exists between OverlaySubnetA:MSIS-P-AddrA and OverlaySubnetA:MSIS-R-AddrA, it notes the interface information (GRE key) say G<b>2</b> for communication in a TunnelGranted message. If the tunnel does not exist, it creates a new GRE key and creates a virtual GRE interface G<b>2</b>.

0149The MSIS-P <b>112</b> then creates policy entries in the routing table to be able to forward packets from one tunnel to the other. The entries are as follows. <ul><li id="ul0020-0001" num="0150">a. If a packet comes on interface G<b>2</b> and is destined to ES, then send the packet through interface G<b>1</b>.</li><li id="ul0020-0002" num="0151">b. If a packet comes on interface G<b>1</b> and is destined to MSIS-R-AddrA, then send the packet through interface G<b>2</b>.</li></ul>

0152It should be noted that the MSIS-P <b>112</b> creates the policy entries whether or not a tunnel already existed. Likewise, these policies are refreshed just like the tunnels themselves. For instance, two different MSIS-R nodes (R<b>1</b> and R<b>2</b>) may have tunnels arranged through an MSIS-P node for the same MSIS-C node. If MSIS-R<b>1</b> does not refresh its tunnel, the tunnel between it and the MSIS-P goes away. The policy that routes packets between that tunnel and the shared tunnel between MSIS-P and MSIS-C should go away. The tunnel between MSIS-P and MSIS-C remains because MSIS-R<b>2</b> still uses that tunnel.

0153At reference <b>510</b>, the MSIS-P <b>112</b> then sends a TunnelGranted Message to MSIS-R <b>114</b> with the following fields: OverlaySubnetA:MSIS-R-AddrA as OverlaySubnetId:RequestorAddress and OverlaySubnetA:MSIS-P-AddrA as the OverlaySubnetId:RequesteeAddress and OverlaySubnetB:ES as the OverlaySubnetId:SecondaryRequesteeAddress and GRE key (of G<b>2</b>) as the Tunnel Identifying Info and possibly other authentication related fields in the Options field.

0154At reference <b>512</b>, the TunnelGranted message arrives at MSIS-R <b>114</b>. The MSIS-R <b>114</b> then uses the information sent in the message to set up a GRE interface say G<b>2</b>. It creates an entry in its Tunnel Table, generating a locally unique TunId to identify the tunnel and storing the following tuple in the Tunnel Table. <ul><li id="ul0021-0001" num="0000"><ul><li id="ul0022-0001" num="0155">TunId; OverlaySubnetA:MSIS-R-AddrA; OverlaySubnetA:MSIS-P-AddrA; OverlaySubnetB; G<b>2</b></li></ul></li></ul>

Example of MSI System Operation Between Overlay Nodes

0156In an aspect, the Tunnel Formation Process can be enhanced when the MSI system requestor and correspondent nodes are in the greater networks that comprise the subnets adjacent to the provider. The correspondent obtains the subnet and provider contact information from the overlay. The correspondent publishes the provider's contact information in the disjoint subnets to the overlay. The request learns of that contact information through the overlay. This includes the subnet identifier that the correspondent's network comprises, the address and subnet identifier for the provider in the remaining subnets that the provider is connected to. The requestor starts the tunnel formation process using a subnet identifier and provider address that the requestor's network comprises. This may be known as a result of previous successful connections or learned experimentally through attempting to setup a tunnel. The tunnel setup process progresses as documented in the tunnel formation process above.

Connectivity Layer (CL)

0157The Connectivity Layer includes in the following data structures for supporting the MSI system.

Connection Table

0158The Connection table is maintained by the CL. In an aspect, a new field referred to as “TunId” is added. The fields of the Connection Table are provided as follows. <ul><li id="ul0023-0001" num="0159">1. Connection Id: The Identifier identifying the connection</li><li id="ul0023-0002" num="0160">2. Connection Tuple: This contains source and destination IPv4 or IPv6 addresses, ports, and protocol.</li><li id="ul0023-0003" num="0161">3. Network Interface: The interface of the node on which to send packets for this connection.</li><li id="ul0023-0004" num="0162">4. TunId: The tunnel identifer associated with this connection. It may be an invalid identifier (e.g. 0 or a negative value) if no Tunnel is associated with the connection identified by Connection Id.</li></ul>

Tunnel Table

0163The Tunnel Table is the table that indicates the nodes to which tunnels exist. The fields of the Tunnel Table are provided as follows. <ul><li id="ul0024-0001" num="0164">1. TunId: The Identifier that refers to this entry.</li><li id="ul0024-0002" num="0165">2. OverlaySubnetId:TunnelSrc: The Address (IP Address and Port number qualified with Overlay Subnet Identifier) of the source of the tunnel. This address should be same as one of the interface addresses of the node on which this tunnel table is stored.</li><li id="ul0024-0003" num="0166">3. OverlaySubnetId:TunnelDest: The Address (IP Address and Port number) of the destination of the tunnel.</li><li id="ul0024-0004" num="0167">4. UniqueOverlaySubnetId: The overlay subnet id (different than the overlay subnet id of TunnelSrc and TunnelDest) for which this tunnel is unique. For example, a tunnel between OverlaySubnetA:MSIS-R-AddrA and OverlaySubnetA:MSIS-P-AddrA can have OverlaySubnetB as the UniqueOverlaySubnetId. However, if MSIS-P also advertises overlays on OverlaySubnetC, and MSIS-R wants to communicate with those overlays, then another tunnel would be needed between OverlaySubnetA:MSIS-R-AddrA and OverlaySubnetA:MSIS-P-AddrA with OverlaySubnetC as the UniqueOverlaySubnetId.</li><li id="ul0024-0005" num="0168">5. Network Interface: The interface of MSIS-R on which to send out a packet when sending the packet through the tunnel (Should be the same as the ‘Network Interface’ field in the Connection Table of any connection that uses this tunnel). This is expected to be a GRE tunnel interface that has been created using the tunnel formation mechanism above.</li><li id="ul0024-0006" num="0169">6. TunMechanism: The Tunneling Mechanism used for the Tunnel. This is expected to be GRE but may be any other suitable tunneling mechanism.</li></ul>

Requested Tunnel Table

0170The Requested Tunnel Table stores information about the tunnels that this node has been requested to setup but the setup hasn't completed yet. The fields of the Requested Tunnel Table are provided as follows. <ul><li id="ul0025-0001" num="0171">1. OverlaySubnetId:RequestingAddr: The address of the node that has requested this tunnel to be setup by the current node qualified with the overlay subnet identifier. For example, at the MSIS-P <b>112</b>, this address is expected to be OverlaySubnetA:MSIS-R-AddrA.</li><li id="ul0025-0002" num="0172">2. OverlaySubnetId:TunDestAddr: The address of the node with which the tunnel has been requested i.e. the proposed tunnel destination (or endpoint). For example, at the MSIS-P <b>112</b>, this address is expected to be OverlaySubnetB:ES</li><li id="ul0025-0003" num="0173">3. UniqueOverlaySubnetId: The overlay subnet identifier for which this tunnel is uniquely bridging to TunDestAddr. In an aspect, this identifier is the same as in field 1 above.</li><li id="ul0025-0004" num="0174">4. Options: Other options contained in the RequestTunnel message that need to be stored in this table. The time when the request came can also be stored to purge stale requests.</li></ul>

Overlay Network Layer

Known Overlay Table

0175The Known Overlay Table keeps track of the Overlays that have been advertised through Overlay Advertisements which this node has heard about. It also associates the advertisement received with the interface on which it was received. Storing information about all the overlays that a node knows about in this table is required for MSIS-P; however it is recommended that all MSIS nodes keep track of at least some overlays that have been advertised.

0176The Known Overlay Table has one or more instances of KnownOverlayElement comprising the following tuple as provided below. <ul><li id="ul0026-0001" num="0177">1. OverlayDescriptionList:Interface:Time:Advertiser_Address: This tuple stores the local interface ID (which can be the IP address) linked with the OverlayDescriptionList data structure that can be the complete or partial OverlayDescriptionList data structure that has been received through that interface. The descriptions are also linked with the address of the node that advertised this list of overlays (Advertiser_Address) and the address may or may not be qualified with an OverlaySubnetId. In the case of MSIS-R in Subnet A, the Advertiser_Address will be OverlaySubnetA:MSIS-P-AddrA. These descriptions are also linked in with the time when they are advertised to allow for stale advertisements to be purged and new advertisements to replace old ones.</li></ul>

0178The entries in Known Overlay Table which are created due to MSIS Advertisements are purged after a reasonable time period (at least the upper bound on Minimum Advertisement Time Window). This happens because the Overlays learned as a result of the MSI system are transient because the MSIS-P <b>112</b> may only provide forwarding services for a certain time interval. Thus, the entries are purged if not refreshed by MSIS Advertisements. It is also important to note that the IP addresses in the OverlayDescriptionList may or may not be qualified with Overlay Subnet Identifiers depending upon whether the advertisement comes from a MSIS-P or not.

0179<figref idrefs="DRAWINGS">FIG. 6</figref> shows an exemplary method <b>600</b> for operating a MSIS-P at a node to provide aspects of a peer-to-peer overlay network discovery system. For clarity, the method <b>600</b> is described below with reference to the MSIS-P <b>200</b> shown in <figref idrefs="DRAWINGS">FIG. 2</figref>. In an aspect, the processor <b>202</b> executes one or more sets of codes provided by the MSI module <b>214</b> to control the MSIS-P <b>200</b> to perform the functions described below.

0180At block <b>602</b>, (N) subnets available for use by the MSI system are identified. For example, the processor <b>202</b> acquires information about the N subnets by receiving advertisements on an underlying network.

0181At block <b>604</b>, unique subnet identifiers are determined for each subnet. In one case, the unique subnet identifiers are received from other MSIS-Ps in AdvertiseMSIS messages. In another case, the processor <b>202</b> operates to generate the unique subnet identifiers. The subnet information is maintained in the subnet database <b>216</b>.

0182At block <b>606</b>, advertisements are generated to advertise accessibility to the subnets. In an aspect, the processor <b>202</b> operates to generate the advertisements to identify the available subnets using the unique subnet identifiers and to provide an unambiguous address that can be used to establish communication with each subnet.

0183At block <b>608</b>, the advertisements are transmitted to N-1 subnets that have been identified. In an aspect, the processor <b>202</b> controls the transceiver <b>206</b> to transmit the advertisements on the available interfaces <b>212</b> in one or more AdvertiseMSIS messages. For example, an advertisement is transmitted to a first subnet advertising the accessibility of one or more subnets, wherein for each of the one or more subnets the advertisement comprises an address and a unique subnet identifier, and wherein the unique subnet identifiers disambiguate overlapping addresses

0184At block <b>610</b>, a request is received from an MSIS-R to connect to an ES at an MSIS-C. In an aspect the request is a RequestTunnel message that includes the unique subnet identifier of the MSIS-C that the connection is addressed to. In an aspect the transceiver <b>206</b> receives the request and passes it to the processor <b>202</b>. For example, the request is received from a first network comprising the first subnet to establish communications with a second network comprising the second subnet, wherein the request identifies the first and second subnets by their associated addresses and subnet identifiers.

0185At block <b>612</b>, a request is transmitted to the MSIS-C to establish a tunnel with the MSIS-C. For example, the processor <b>202</b> generates a GRETunnelRequest message that is transmitted to the MSIS-C by the transceiver <b>206</b>.

0186At block <b>614</b>, a grant is received from the MSIS-C to allow a tunnel to be established between the MSIS-P and the MSIS-C. In an aspect, the grant is received by the transceiver <b>206</b> in a GRETunnelGranted message from the MSIS-C and passed to the processor <b>202</b>.

0187At block <b>616</b>, tunnel setup is performed to establish a first tunnel with the MSIS-C. In an aspect, the processor <b>202</b> operates to set up the first tunnel. A determination is made as to whether a tunnel already exists. If so, the processor utilizes this tunnel to set up policy to forward packets to the MSIS-C. In another aspect, the tunnel does not already exist and so the processor <b>202</b> operates to set up the first tunnel and set up the policy accordingly. For example, the policy is set up as described above.

0188At block <b>618</b>, a grant is transmitted to the MSIS-R granting the request to establish a tunnel. In an aspect, the processor <b>202</b> generates a TunnelGranted message that the transceiver <b>206</b> transmits to the MSIS-R.

0189At block <b>620</b>, transmissions are directed between tunnels using the policy information. For example, packets received from the MSIS-R over the second tunnel are forwarded to the MSIS-C using the first tunnel. In addition, packets received from the MSIS-C over the first tunnel are forwarded to the MSIS-R using the second tunnel. In another aspect, transmissions are directed between the first and second tunnels based on policy information to allow communications between the first network comprising the first subnet and the second network comprising the second subnet. This allows a node in a network comprising subnet A to communicate with overlays in a disjoint network comprising subnet B in a fast and efficient manner.

0190Therefore, the method <b>600</b> is performed by MSIS-P <b>200</b> operating at a node to provide aspects of a MSI system. It should be noted that the method <b>600</b> is just one implementation and that the operations of the method <b>600</b> may be rearranged or otherwise modified within the scope of the various aspects. Thus, other implementations are possible.

0191<figref idrefs="DRAWINGS">FIG. 7</figref> shows an exemplary method <b>700</b> for operating a MSIS-R at a node to provide aspects of a MSI system. For clarity, the method <b>700</b> is described below with reference to the MSIS-R <b>300</b> shown in <figref idrefs="DRAWINGS">FIG. 3</figref>. In an aspect, the processor <b>302</b> executes one or more sets of codes provided by the discovery module <b>314</b> to control the MSIS-R <b>300</b> to perform the functions described below.

0192At block <b>702</b>, information is received identifying available subnets and includes unique subnet identifiers. In an aspect, the advertisements comprise AdvertiseMSIS messages received from a MSIS-P. For example, the transceiver <b>306</b> receives the advertisements and passes them to the processor <b>302</b>. In another aspect, the information is received in a MSIS-relayed network address. The available subnets are associated with unique subnet identifiers and represent subnets that are disjoint from the subnet in which the MSIS-R belongs. For example, the information identifies an address and a unique subnet identifier for each of one or more subnets in addition to identifying a provider node, wherein the unique subnet identifiers disambiguate overlapping addresses.

0193At block <b>704</b>, a database is maintained of available subnets and associated subnet identifiers. In an aspect, the processor <b>302</b> maintains the subnet information in the database <b>312</b>.

0194At block <b>706</b>, a determination is made as to whether there is an application that desires a connection to a (MSIS-C) having a subnet identifier that is in the database of subnet identifiers. If there is an application that desires a connection, a selected subnet for communications to a correspondent node is identified, wherein the correspondent node is in a disjoint network that comprises the selected subnet. The method proceeds to block <b>708</b>. If there is no application desiring a connection, the method proceeds to block <b>702</b>.

0195At block <b>708</b>, a request for a tunnel is transmitted to the MSIS-P that transmitted the advertisement associated with the selected subnet. In an aspect, the processor <b>302</b> generates a TunnelRequest message that is transmitted by the transceiver <b>306</b> to the MSIS-P. The TunnelRequest message specifies the MSIS-C to connect to which a connection is desired.

0196At block <b>710</b>, a tunnel grant response is received indicating a tunnel from the MSIS-P to the selected subnet has been established. In an aspect, a TunnelGranted message is received by the transceiver <b>306</b> and passed to the processor <b>302</b>.

0197At block <b>712</b>, a tunnel is set up to the MSIS-P and associated policies are established. In an aspect, the processor <b>302</b> sets up the tunnel and associated policies to allow the application to communicate with the MSIS-C using the tunnel.

0198At block <b>714</b>, the application is allowed to communicate with the MSIS-C using the tunnel and associated policies. For example, communications with the correspondent node can be performed using the tunnel based on policy information.

0199Therefore, the method <b>700</b> is performed by MSIS-R <b>300</b> at a node to provide aspects of a MSI system. It should be noted that the method <b>700</b> is just one implementation and that the operations of the method <b>700</b> may be rearranged or otherwise modified within the scope of the various aspects. Thus, other implementations are possible with the scope of the various aspects described herein.

0200<figref idrefs="DRAWINGS">FIG. 8</figref> shows an exemplary MSIS-P <b>800</b> for use in aspects of a MSI system. In an aspect, the MSIS-P <b>800</b> is implemented by at least one integrated circuit comprising one or more modules configured to provide aspects of a MSI system as described herein. For example, in an aspect, each module comprises hardware and/or hardware executing software.

0201The MSIS-P <b>800</b> comprises a first module comprising means (<b>802</b>) for transmitting an advertisement to a first subnet advertising the accessibility of one or more subnets, wherein for each of the one or more subnets the advertisement comprises an address and a unique subnet identifier, and wherein the unique subnet identifiers disambiguate overlapping addresses, which in an aspect comprises the transceiver <b>206</b>. The MSIS-P <b>800</b> also comprises a second module comprising means (<b>804</b>) for receiving a request from a first network comprising the first subnet to establish communications with a second network comprising the second subnet, wherein the request identifies the first and second subnets by their associated addresses and subnet identifiers, which in an aspect comprises the transceiver <b>206</b>. The MSIS-P <b>800</b> also comprises a third module comprising means (<b>806</b>) for establishing a first tunnel with the second subnet and a second tunnel with the first subnet, which in an aspect comprises the processor <b>202</b>. The MSIS-P <b>800</b> also comprises a fourth module comprising means (<b>808</b>) for directing transmissions between the first and second tunnels based on policy information to allow communications between the first network comprising the first subnet and the second network comprising the second subnet, which in an aspect comprises the processor <b>202</b>.

0202<figref idrefs="DRAWINGS">FIG. 9</figref> shows an exemplary MSIS-R <b>900</b> for use in aspects of a MSI system. In an aspect, the MSIS-R <b>900</b> is implemented by at least one integrated circuit comprising one or more modules configured to provide aspects of an overlay network discovery system as described herein. For example, in an aspect, each module comprises hardware and/or hardware executing software.

0203The MSIS-R <b>900</b> comprises a first module comprising means (<b>902</b>) for receiving information identifying an address and a unique subnet identifier for each of one or more subnets in addition to identifying a provider node, wherein the unique subnet identifiers disambiguate overlapping addresses, which in an aspect comprises the transceiver <b>306</b>. The MSIS-R <b>900</b> also comprises a second module comprising means (<b>904</b>) for identifying a selected subnet for communications to a correspondent node, wherein the correspondent node is in a disjoint network that comprises the selected subnet, which in an aspect comprises the processor <b>302</b>. The MSIS-R <b>900</b> also comprises a third module comprising means (<b>906</b>) for transmitting a request to the provider node, wherein the request identifies the selected subnet by its associated address and subnet identifier, which in an aspect comprises the transceiver <b>306</b>. The MSIS-R <b>900</b> also comprises a fourth module comprising means (<b>908</b>) for establishing a tunnel to the provider node, which in an aspect comprises the processor <b>302</b>. The MSIS-R <b>900</b> also comprises a fifth module comprising means (<b>910</b>) for communicating with the correspondent node using the tunnel based on policy information, which in an aspect comprises the processor <b>302</b>.

0204The various illustrative logics, logical blocks, modules, and circuits described in connection with the aspects disclosed herein may be implemented or performed with a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general-purpose processor may be a microprocessor, but, in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

0205The steps of a method or algorithm described in connection with the aspects disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, a hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor, such that the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC. The ASIC may reside in a wireless communication device. In the alternative, the processor and the storage medium may reside as discrete components in a wireless communication device.

0206The description of the disclosed aspects is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these aspects may be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other aspects, e.g., in an instant messaging service or any general wireless data communication applications, without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the aspects shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein. The word “exemplary” is used exclusively herein to mean “serving as an example, instance, or illustration.” Any aspect described herein as “exemplary” is not necessarily to be construed as preferred or advantageous over other aspects.

0207Accordingly, while aspects of a MSI system have been illustrated and described herein, it will be appreciated that various changes can be made to the aspects without departing from their spirit or essential characteristics. Therefore, the disclosures and descriptions herein are intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.