System with a plurality of interconnected sub-networks

The networks like the Internet allow interconnection of many private (sub-)networks. By means of tunneling different sub-networks can be coupled to form a virtual private network, wherein the devices from these different sub-networks can send messages to each other as if they were connected to a single private network. "Tunneling" means that messages are transmitted via the Internet (or other interconnecting networks) in a way wherein the addresses of the messages that are used in the sub-networks are not used as address during transmission via the Internet. A virtual private network is realized for example by coupling each sub-network to the Internet via a residential gateway. In each sub-network messages with destination addresses for devices in the other sub-network are detected and transmitted over the Internet between the residential gateways of the sub-networks, inserted in messages addressed to the residential gateway of the other sub-network. The residential gateway of the other sub-network, in turn, forwards the messages to devices connected to the other sub-network.

Such tunneled virtual private networks are described for example in US patent application No. 2004/0148439, US 2003/0214955 and 2004/0258074. A major issue in these patent applications is the assignment of local addresses to devices that are connected to different sub-networks. These addresses should make it possible to refer to any device in the virtual private network without ambiguity. Conventionally, devices are assigned addresses to avoid ambiguity within each sub-network. This can be done with a DHCP (Dynamic Host Configuration Protocol) server for example. But when each sub-network has its own DHCP server it is not excluded that the same address is assigned to different devices in different sub-networks that may form a virtual private network. In theory, this problem can be avoided by assigning each device an Internet wide unique address, but this is impractical and inefficient in view of the large and variable number of devices that is connected to subnetworks of the Internet, the vast majority of which will never give rise to addressing problems.

US patent application No 2004/0148439 describes various solutions to the problem of assignment of addresses for virtual private networks. The primary solution is the use of address translation. In this solution two addresses are assigned to each device that has to be visible in a virtual private network that comprises a first and second sub-network. A first address is the native address of the device in the sub-network to which the device is locally coupled. The second address is assigned to the device in the other sub-network when the virtual private network is formed. The first and second address are translated from one to the other when messages pass between the two sub-networks. This method has the disadvantage that the interface between the sub-networks has to "know" the locations of all addresses in messages. This is only feasible if address use in all interface protocols, of all interface layers, is limited to predefined forms of use, e.g. only as destination address. It may be difficult for example to provide translation of addresses that are embedded in documents. US patent application No 2004/0148439 also mentions the possibility of using the "native" address of devices in both of the sub-networks that form a virtual private network. This may mean that devices have to be assigned new addresses when a virtual private network is formed (so as to eliminate addresses assigned different devices in the respective sub-networks), but it eliminates the need to be able to perform translation. US patent application No 2004/0148439 mentions that this requires coordination, wherein coordinated disjoint address spaces are claimed for the respective sub-networks for use to assign addresses. The document notes the problem that if a sub-network forms virtual private networks with a plurality of other sub-networks the disjoint address spaces need to be coordinated among all connected sub-networks. The document proposes no solution for this.

Among others, it is an object of the invention to provide for coordination of addresses between sub-networks that are joined to form virtual networks.

A system according to claim 1 is provided. This system provides for a storage arrangement for storing first information identifying relations between pairs of sub-networks between which tunneled communication is supported and second information identifying respective sets of reserved addresses for respective ones of the sub-networks, for use by devices in these respective ones of the sub-networks. The storage arrangement preferably comprise respective storage devices coupled to respective ones of the sub-networks, each storing the first information about the relations for that sub-network and the second information about the set of reserved addresses for that sub-network. Alternatively the

storage arrangement may comprise a server outside the sub-networks to store the first and second information for a group of sub-networks, or separate storage units for the first and second information.

The second information in the storage arrangement, about the reserved sets of addresses is updated incrementally, each time when a relation is added. When a relation between a first one of the sub-networks and a second one of the sub-networks is added it is tested whether a first overlap exists between the reserved set of addresses for the first one of the sub-networks and any set of reserved addresses for each further one of the sub-networks that is identified in a relation with said second one of the sub-networks, or a second overlap exists between the sets of reserved addresses for devices in the first one of the sub-networks and the reserved set of addresses for the second one of the sub-networks, and the set of reserved addresses for devices in the first one of the sub-networks is changed to eliminate the second overlap when the first or second overlap exists. The changed set of reserved addresses is used subsequently until a change is made necessary by the addition of another relation. In this way, only limited changes need to be made when a relation is added, merely requiring testing of sets of reserved addresses for the newly related sub-networks and their direct relations. This suffices to avoid address conflicts when the sub-networks of a relation form a virtual private network wherein the same respective address is used for each respective device in messages in both sub-networks. Preferably, when the first one of the sub-networks already has related subnetworks, overlap with the reserved address ranges of those sub-networks is also tested if a change is made in the reserved set of addresses for the first one of the sub-networks.

In an embodiment information about the reserved ranges of address is acquired for said testing by transmitting queries to the sub-networks involved. Thus, up to date information, including the result of previous changes is obtained. Alternatively, cached information may be always be used, or in the case when a further one of the sub-networks does not respond. Thus, the amount of communication can be limited.

In an embodiment the devices test whether their reserved set of addresses has an overlap by submitting that set as a proposal to the other involved sub-networks, the overlap being tested in another sub-network, which returns an acceptance or denial of the proposal. This is repeated for different proposals until full acceptance is achieved. In this way, full information about reserved sets of addresses can be kept private to each subnetwork.

These and other objects and advantages will become apparent from a description of exemplary embodiments, by reference to the following figures.

Fig. 1 shows a networked system, Fig. 2 shows an address selection device,

Figs. 3-5 show flow-charts of address space reservation

Figure 1 shows a networked system. The system comprises a main network interconnection circuitry 10 (e.g. the Internet) and a plurality of sub-networks each with its own sub-network interconnection circuitry 12 and a number of devices 14,16 (only some referenced explicitly by way of example) coupled to the sub-network interconnection circuitry 12. It should be understood that "interconnection circuitry" is used herein includes to refer to both wired and/or wireless connections, as well as optical connections and associated devices for transporting and routing messages if present. The devices 14, 16 in each sub-network include a gateway device 16 coupled between the main network interconnection circuitry 10 and the sub-network interconnections 12.

In operation devices 14, 16 transmit messages via interconnections 10, 12. Each message typically contains a destination address, which identifies a receiving device 14, 16 for which the message is destined.

Part of the devices 14, 16, for example the gateway devices 16, may have predetermined globally unique addresses, selected so that no other device 14, 16 coupled to main network interconnections 10 has the same address. In the Internet (IP version 4) environment, such addresses are typically represented a series of four numbers separated by dots. Another part of the devices 14, 16 are locally assigned devices 14, 16 that have locally assigned addresses, which are assigned to the locally assigned devices 14, 16 by an assigning device.

Messages with locally assigned addresses of devices 14, 16 that are connected to the sub-network interconnections 12 of the sub-network wherein these messages are initially transmitted are detected by these devices 14, 16 and received. Messages addressed to devices 14, 16 with a globally unique address on main network interconnections 10 are forwarded by gateway device 16 to their destination.

In addition, virtual networks may be defined, wherein at least a first and second one of the sub-networks are coupled. Information about such virtual networks may be

stored for example in gateway device 16 of the sub-networks that are part of such a virtual network. The information may include for example a list of addresses of devices 14, 16 in the other sub-network, or an identification of one or more ranges of addresses reserved for such devices. When a message is detected in the first network that has a locally assigned address addressed to a device 14, 16 in the second sub-network, gateway device 16 of the first subnetwork transmits the message to the second sub-network. Typically such a message is encapsulated in a further message that is addressed to a device (e.g. the gateway device 16) in the second sub-network that has a globally unique address. In the second network the message is converted back to the original message with its locally assigned address. These messages are then detected by local devices 14, 16 and received.

Local assignment of addresses may be performed for example by the gateway device 16 that is connected between the locally assigned device 14, 16 and the main network interconnections 10. Alternatively, another device 14, 16 (e.g. a main computer) coupled to the sub-network interconnections 12 may be used, or even a remote device coupled to sub- network interconnections 12 via main interconnections 12. The locally assigned addresses may be assigned dynamically, each time when a device 14, 16 starts up, or more persistently, for example each time a device 14, 16 is added to sub-network interconnections 12 of a subnetwork.

Figure 2 shows an address selection device 20 for assigning locally assigned addresses. In an embodiment address selection device 20 is part of gateway device 16. Address selection device 20 comprises a sub-network interface 22, a processing circuit (processor) 24 and a storage unit 26. Typically, processor 24 is a programmable device, which is programmed to perform the described functions. Processor 24 is coupled to interface 22 and storage unit 26. In operation processor 24 receives requests from devices (not shown) for assigning addresses via interface 22. Storage unit 26 stores information that identifies a set of addresses that is reserved for the devices. Preferably, storage unit contains non- volatile storage, such as flash memory or a hard disk for example, to store the information about the set of reserved addresses. In response to a request processor 24 consults this information and selects a reserved address. Processor 24 then returns the selected address to the requesting device in response to the request. Alternatively, the requesting device may itself select an address, indicating the address in the request and processor may be arranged to consult the information to determine whether the address belongs to the set of reserved addresses, to grant or deny the request dependent on this determination. Although an embodiment has been mentioned wherein address selection device 20 is part of gateway device 16, it should be

understood that alternatively another device 14 connected to sub-network interconnections 12 of the sub-network may be used. In another embodiment a further device coupled to subnetwork interconnections 12 via main interconnections 10 may even be used, although of course this has the disadvantage that it makes the sub-network more dependent on main interconnections 10.

The information that defines the set of reserved address for a particular depends on information about sub-networks that are recorded as "related" to the particular sub-network. A compiling device is provided for compiling the information that defines the set of reserved address dependent on the recorded related sub-networks. This compiling device is operative at least to update the information when an additional sub-network is added as related sub-network. Alternatively this compiling device may be activated each time when the particular sub-network is powered up. The function of compiling device may be performed by address selection device 20, of gateway device 16, another device 14 connected to sub-network interconnections 12 of the particular sub-network, or a further device coupled to sub-network interconnections 12 via main interconnections 10.

Figure 3 shows a flow-chart for compiling the information that identifies the set of reserved addresses when a new sub-network is added as related sub-network. An embodiment will be described wherein an address selection device 20 coupled to a particular sub-network acts as compiling device for that particular sub-network. Furthermore, it will be assumed that the set of reserved addresses is specified as a range of reserved addresses for devices connected to the particular sub-network.

In a first step 31 the compiling device receives a signal that a specified subnetwork should be added as related sub-network for the particular sub-network. The compiling device updates a stored list of related networks in storage unit 26, by adding the specification of the related sub-network to this list (preferably in a non- volatile memory such as a flash memory or a hard disk). In a second step 32 the compiling device sends a query message to a further compiling device of the specified sub network, requesting a list of address ranges reserved for further sub-networks that are related to the specified subnetwork. In response the further compiling device provides this list. In an embodiment the further compiling device generates the by executing a third step 33, wherein the further compiling device of the specified sub-network receives the query message. In a fourth step 34 the compiling device of the specified sub-network sends further query messages to the yet further compiling devices of the sub-networks that are related to the specified sub-network.

In a fifth step 35 the yet further compiling devices of the sub-networks that are related to the specified sub-network return identifications of ranges of addresses that they have reserved for devices. In a sixth step 36 the further compiling device returns a compilation of these identifications plus identifications of a range of reserved addresses of sub-network of the further compiling device itself (or the identifications themselves).

In a seventh step 37 the compiling device of the particular sub-network receives this compilation (or these identifications) and changes its currently reserved range of addresses if that range overlaps with the reserved addresses of the specified sub-network or sub-networks that are directly related to the specified sub-network. In an eight step 38 the compiling device tests whether any devices are currently connected to the particular sub-network that have addresses in the compilation provided by the further compiling device. If so the addresses of these devices are changed. Preferably, the compiling device of the particular sub-network also sends its own compilation of its own reserved address range (or ranges; after the update of seventh step 37) and those of its previous related sub-networks to the further compiling device of the specified sub-network. The further compiling device then executes steps similar to seventh step 37 and eight step 38.

Figure 4 shows a more symmetric approach. Two branches are shown, which are executed by a first and second compiling device for a first and second one of the sub- networks respectively. In a first step 41a,b the compiling devices receive a signal that a relation is to be created between the first and second one of the sub-networks. The compiling devices record this relation in their storage units. In second steps 42a,b the first and second compiling devices send query messages to further compiling devices of related further subnetworks that are related to the first and second one of the sub-networks respectively. In third steps 43a,b the further compiling devices return identifications of ranges of addresses that they have reserved for devices in the related further sub-networks. In fourth step 44 the first compiling device sends information about its own reserved range and the reserved ranges of its related further ranges to the second compiling device. In a fifth step 45 the second compiling device receives this information and changes its currently reserved range of addresses if that range overlaps with the reserved addresses of according to the received information. In a sixth step 46 the second compiling device sends information about its own (possibly newly) reserved range and the reserved ranges of its related further ranges to the first compiling device. In a seventh step 47 the first compiling device receives this

information and changes its currently reserved range of addresses if that range overlaps with the reserved addresses of according to the received information.

In an eight step 48 the first and second compiling device tests whether any devices are currently connected to the first or second one of the sub-networks have addresses outside the now reserved range. If so the addresses of these devices are changed.

In an embodiment the compiling devices are arranged to cache (store) information about the ranges of addresses that have been reserved for their related subnetworks. If so transmission of (further) query messages to compiling devices of previously related sub-networks may be omitted. In this embodiment the compiling device preferably sends an update message to the compiling devices of its related sub-networks if the range of reserved addresses is changed in seventh step 37, 47or fifth step 35. In a further embodiment the cached identifications of reserved ranges are used for those related sub-networks that do not respond to queries about their reserved ranges, and responses from the related subnetworks are used for those related sub-networks that do respond to a query. Figure 5 shows an alternative embodiment wherein the compiling devices of the newly related sub-networks transmit only information about their reserved range as a proposal to each other and send back an approval/disapproval signal to indicate whether this proposed transmitted reserved range of the other compiling device overlaps with their own reserved range or any reserved range of the related sub-networks of their own sub-network. If an overlap is signaled the compiling device generates a proposed change to its reserved range and transmit information about the new proposed reserved range. In response to this, another approval/disapproval signal is returned and so on until approved ranges have been established. This has the advantage that no complete information about the reserved ranges needs to be exchanged between the compiling devices of the newly related sub-networks. In a first new step 51a the compiling devices exchange proposals (initially indicating their existing reserved range). In a second new step 52a each compiling device tests the proposal of the other compiling devices against the reserved address range of their own sub network and those of their directly related sub-networks and return the result of the test to the other compiling device. In a third new step 53a the process returns to first new step 5 la,b if an overlap was signaled. In this case the first new step 51a each compiling device that has an overlapped proposal generates a proposed new range of reserved addresses and the process repeats. When no overlap occurs the proposed range is adopted and stored in the storage unit in fourth step 54a,b.

Also, various changes may be made in the sequence of the steps. For example, in one embodiment entry of the relation between the sub-networks and the subsequent steps may be executed only if it is requested in both related sub-networks. As another example the compiling device of the particular sub-network may send its compilation of reserved ranges to the further compiling device of the specified sub-network first, with the request to amend the reserved ranges at the specified sub-network before making amendments in the reserved range in the compiling device of the particular sub-network.

Although embodiments have been described wherein a range of addresses is reserved (for example all addresses that start with a same series of digit values and have arbitrary values at a number of final digit positions), it should be understood that instead of ranges also sets of individual addresses that need not be mutually adjacent may be used as set of reserved addresses.

An embodiment has been described wherein the set of reserved addresses is updated when a new relation between sub-networks is established. Preferably information about this updated set is saved and the saved information is used to define the set each time when the sub-network is started up. However, it should be appreciated that alternatively a set of reserved addresses may be established each time when a particular sub-network is started up, by sending queries about reserved ranges of related further sub-networks that are recorded to be related to the particular sub-network and to yet further sub-networks that are recorded to be related to the related further sub-networks.