WO2005067264A1

WO2005067264A1 - Method and system for including a new node into a computer network

Info

Publication number: WO2005067264A1
Application number: PCT/NO2005/000002
Authority: WO
Inventors: Andreas Hafslund; Andreas TØNNESEN; Paal Engelstad; Roar Bjørgum ROTVIK; Jon Andersson
Original assignee: Thales Norway AS
Current assignee: Thales Norway AS
Priority date: 2004-01-05
Filing date: 2005-01-05
Publication date: 2005-07-21
Anticipated expiration: 2006-07-05
Also published as: NO20040033L

Abstract

System and method for including a new node into a computer network comprising a number of nodes, wherein the new node includes a requester unit for transmitting a request signal for participating in the network, and at least one of said nodes existing in the network comprising a responder unit, each responder unit including a list of addresses of the nodes already participating in the network and address generation means for generating a new address and transmitting this to the requester unit, the new node thus being provided with an address and being included in the network, and said responder units in the network updating the list of network addresses.

Description

Method and system for including a new node into a computer network

This invention relates to a method and system for including a new node into a computer network comprising a number of nodes.

The data communication and connections in any IP network are based upon using the IP address for identifying the communicating nodes. Therefore, any node wishing to join an IP network needs a valid, unique IP address. In this document we propose a mechanism for autoconfiguring the IP address. With this mechanism, any node can get a valid address, and then participate in the routing and the regular data communication.

1. Introduction 1.1 Background Any node in an IP network needs a valid IP address to be able to participate in the routing and the regular data communication. It is the IP address that uniquely identifies the node in the network, which the node belongs to.

There are several ways to acquire an IP address. For wired networks, the two most common ways are either static configuration, or with the use of DHCP (Dynamic Host Configuration Protocol [1] (see reference list below). A static configuration can simply be that the node has been given a valid address by a system administrator, and will use this address always. For a network with many nodes, this is not scalable. DHCP provides a framework for automatic allocation of reusable addresses. It also specifies additional configuration options, see [1] for details. DHCP is built on a client-sever model. The DHCP client is any node requesting configuration parameters such as an address, from the server. The DHCP server refers to the host providing configuration parameters. The basic mechanism for DHCP is that on a given network there is one DHCP server allocated. This server is responsible for allocating addresses to all nodes in it's own network. The addresses are allocated on request from the DHCP clients. A DHCP server should always have the full survey of all addresses that are in use in the network. This is to avoid address conflicts in the network, for instance from giving out the same address to more than one requesting node.

In some networks where there can be a problem with single point of failure, the use of a DHCP server is not recommended. Such networks can for instance be a wireless networks with low bandwidth radio links. If a node requests an address, but cannot contact the DHCP server, the node cannot participate in the network. Single point of failure can be if the DHCP server goes down is not reachable for a given node etc. In such networks a distributed address configuration scheme is preferred.

Thus it is an object of this invention to provide a method and system being independent of the availability of the DHCP server.

Mobile ad hoc networks running over wireless links is a typical example of such networks where a distributed address configuration scheme is preferred. The present invention is mostly related to ad hoc networks, but is not only applicable in such networks. It is an object of this invention to provide a solution that can be used in any network that is running a pro-active routing protocol.

Routing in mobile ad hoc networks is much more difficult than routing in regular, wired networks. Since the nodes can be mobile, and the networks links can have dynamic bandwidth, the topology of the network can always be changing. Routing in mobile ad hoc networks can be divided into to different approaches: reactive and pro-active. A reactive routing protocol does not know anything about the network in beforehand, but must find a route to a given destination on demand. A pro-active routing protocol seeks to always have a complete updated knowledge of the network topology. This means that the routing protocol always knows which addresses that are in use.

All the standard wired network routing protocols such as OSPF, IS-IS and RIP are pro- active routing protocols. It is a further object to this invention to provide an auto configuration approach which applies equally well to these pro-active protocols as it do for the specific pro-active routing protocols in ad hoc networks. 1.2 Summary of the invention

It is an object of this invention concerning address auto-configuration to avoid using a specific server for the allocation of addresses in the network. This approach is a fully distributed approach. This means that each node in the network can allocate an address to a new, requesting node. The approach according to the present invention uses the fact that the pro-active routing protocol always knows which addresses that are in use. On the basis of this knowledge, any node already within the network, can assign an address to a new, requesting node. The only thing the assign node must check is if the address it intends to assign to the requesting node is in use in the routing protocol or the address assigning cache. More specific the objects of this invention are obtained with a method and a system as described in the independent claims.

The present invention applies equally well for both IPv4 and IPv6 standards, and it applies equally well to any other addressing scheme besides IP. The current mechanism is not only for use in wireless ad hoc networks, but does apply very well in such networks.

2. Related Work As mentioned in section 1.1, DHCP is the mostly used auto configuration mechanism for wired networks.

For wireless, ad hoc networks, there have only been a few contributions to the subject of address autoconfiguration. The work [2] is the most common work on this subject. It describes a mechanism for how mobile nodes can autoconfigure themselves with unique and valid addresses. The method for determining if any other node in the network has taken the same address is taken from the reactive ad hoc routing protocol AODV [5]. The new node assigns itself an address on random, and then broadcasts a query to the ad hoc network, asking if this address is already taken or not. Note, for determining which address to use for the new node, this autoconfiguration mechanism does not involve any other node currently inside the ad hoc network. The new node itself generates the address it wants. The work [3] for the MANETconf autoconfiguration mechanism is the work mostly related to the present invention. In this mechanism, a node outside the ad hoc network has to request a valid address from a node currently inside the ad hoc network. Any node inside the network can assign an address, and this address must be taken from a range with unassigned addresses. Then the node inside the network will broadcast a query into the network, asking if this address is available, that is, not taken by anyone else.

Then the node inside the network will broadcast a query into the network, asking if this address is available, that is, not taken by anyone else.

Maintaining information about unassigned addresses is demanding in an active network, especially an active net having nodes leaving and assigning frequently, e.g. in mobile ad hoc networks. The present invention thus provides a more efficient and method and system for handling new node assigning to the network.

2.2 Duplicate Address Detection (DAD)

The work [4] is the most recent work in the subject of autoconfiguration. This work describes mechanism for Duplicate Address Detection (DAD), but does not specify how to acquire the address in the first place. In [4] they divide DAD into Strong DAD and Weak DAD.

When a new node enters an ad hoc network, it have to use Strong DAD to check if its chosen address is already take or not. The new node selects two addresses, one temporary and one tentative address. Then the node broadcasts a Address Request for checking if the tentative address is already used. If so, any node knowing that the tentative address is already used, answers back to the new node (temporary address) with an Address Response. The new node now has to generate a new tentative address, and check againg. Weak DAD's purpose is to detect address duplication during ad hoc routing. A given node inside the ad hoc network has a virtual IP address that is the combination of the current address and a key. When the node receives any control message from the other nodes in the network, the node checks if the address is used by itself, or any other node the current node knows about. The key is used for uniquely identifying the nodes by their virtual address, not only the IP address.

The work in [2] describes basically the same mechanisms. For DAD, any new node entering an ad hoc network must choose two addresses, a temporary one and the actual one. The uniqueness check is based upon sending out an broadcast Address Request, and waiting for an Address Response if the address is already in use.

In DAD mechanism described in [3] is also based upon the same idea, sending out an broadcast test to see if the chosen address is already in use or not. In comparison to [2] and [4], [3] lets the responder do the DAD. In the two other works, the requester will handle the DAD by itself.

3. Terminology - Requester: a node wanting to have a valid address for participating in the network. Responder: a node already participating in the network, which assigns the address to the requester. - Address assigning cache: a cache all the nodes inside the network keeps, where addresses that are currently being tested for address duplication are kept. The addresses in this cache have a certain lifetime before they are removed. - Passive address cache: a cache all the nodes inside the network keep, where addresses that have been used earlier, but not at the current time, are kept. The addresses in this cache have a certain lifetime before they are removed.

The invention will be described in detail below with reference to the accompanying drawings, illustrating the invention by way of examples: Figure 1 shows how the requester outside of the network contacts a responder inside the network to get a valid address. Figure 2 shows the decision flow chart of the responder according to one embodiment of the invention.

4. Detailed description of the invention 4.1 System Proposal Figure 1 illustrates a requester wanting to assign an address in the network, the network comprising a number of possible responders.

A requester is, as mentioned above, a (new) node that wants to get a valid address for participating in the network. Since there is no DHCP-server available, the requester must get a valid address from someone else in the network. The present invention gives all the current nodes in the network the possibility to become a responder. A responder is a node already participating in the network, and that has an updated view of the network topology. The responder is the node answering back to the requester, and thus assigning an address to the requester. The responder will check the assigned address against the routing protocol to see if the assigned address is already in use. If so, the responder will assign a new address.

The requirements for this invention are that the responder is using a pro-active routing protocol. This means that the responder always has a full knowledge of all the addresses in use in the network.

Also, according to a preferred embodiment of the invention the responder or the requester will need a Duplicate Address Detection (DAD) mechanism for checking to see if the assigned address is in fact in use or not. This mechanism is needed after the check against the routing protocol. A DAD as specified in [2] or [3] can be good enough. It is left for implementation issues to choose if the responder or the requester should do the DAD. Security issues should also be taken into considerations when deciding this.

During the DAD, all nodes inside the network will put the address in their address assigning cache. This is a cache where all addresses that is currently in DAD are cached. The address stays in the cache until a timer goes out, or the node finds the address in its own routing table.

All nodes in the network also keep a passive address cache. If a node inside the network is for a short time outside the network (for instance, out of radio range if the network is wireless and radio-based), its address is put in the passive address cache by all the other nodes in the network. This is to make sure the node can join the network again without asking for a new address. The cache is also used so that new nodes will not be assigned this address. That is, the responder checks its (1) routing table, (2) address assigning cache and (3) passive address cache. These control procedures are considered to be known to a person skilled in the art, and will not be described in any detail here.

The addresses in the passive address cache stays there until the node returns, or within a certain time. If the node does not return within the threshold time, all nodes in the network remove the address from the passive address cache. The node outside of the network, also knows that its address is timed out, and when returning, it will need a new address.

Also, a preferred embodiment of the invention will include a shutdown mechanism. This is when a node currently participating in the network, will end its participation in the network. The node can then send a shutdown message to the network. This message is broadcasted to the entire network. When the node is now longer a member of the network, all the nodes will not be putting its address in the passive address cache. This is because of the shutdown message.

Figure 2 illustrates more in detail the process after contact is made between the requester and the responder. As is clear from figure 2 the method according to the invention comprises the steps of assigning an address for the requestor, checking this new address with the routing tables in the nodes of the existing network, and sending the address to the new node if the address is not in use. In addition, the address may, as illustrated in the drawing, be checked against an address assigning cache and a passive address cache containing addresses of registered addresses being registered in the network but not present at the moment.

Preferably the DAD is also performed before sending the address to the requester, and in the case that a duplicate address is found a new address is generated from the start.

After the implementation of the requester in the network the routing tables of the network nodes are updated.

4.2 Other Considerations

As mentioned in section 4.1 , this invention for autoconfiguration will need a DAD mechanism. The present approach with using the routing protocol for verifying the validity of the assigned address will give few address collisions, but they might occur anyway. Therefore, to avoid this, some sort of DAD must be included. This is left as implementation issues.

Also, this invention needs a communication mechanism between the requester and responder. This could be a broadcast communication, where the requester sends a broadcast to the network, and all the nodes hearing this broadcast, will responds as a responder. Then the requester can choose the first (or last) to answer with an address.

If the responder should be one-hop away from the requester or if the responder should be allowed to be more than one-hop away is left as implementation issues. It is clear that to allow for multi-hop will increase the complexity of the system, and also decrease the security and robustness of the system. This invention does not take any security considerations in mind. But since the requester needs to get an address from a responder, that is, a node already inside the network, it is obvious to use an authentication procedure between requester and responder before this happens.

4.3 Summary

Summing up, the invention thus relates to a system for including a new node into a computer network comprising a number of nodes. The requesting, new node includes a requester unit for transmitting a request signal for participating in the network, and at least one of said nodes existing in the network comprises a responder unit, each responder unit including a list of addresses of the nodes already participating in the network and address generation means for generating a new address and transmitting this to the requester unit. The new node is thus being provided with an address and being included in the network, and said responder units in the network updating the list of network addresses .

The network addresses may in its simplest for be the routing tables, but other lists e.g. including disconnected but existing addresses and unavailable addresses may also be used for controlling whether the new address is unique.

According to a preferred embodiment of the invention at least one of the requester or responder units comprises duplicate address detection (DAD) means of any of the types discussed above, for detecting duplicate addresses in the network. The DAD may include the use of an address assigning cache, containing the addresses of each node in the network, making it possible to include a step of the responder unit comparing the addresses in said list of addresses with the addresses in the cache.

Enough nodes should preferably be participating in the network being provided with broadcast means, for broadcasting signals to a number of other nodes in the system, e.g. for communicating the proposed new address to the network nodes. The number of nodes participating nodes in the network being adapted to forward information to and from the requester unit, such that all nodes participating in the network is reachable. The method of the invention for admitting a new node into a network by providing an address in the network, will essentially comprise the steps of: 1. upon the arrival of a request signal, assigning an address to the new node 2. checking an address list, usually being the routing table of the node, included in the responding node, and if the address is in use a new address is generated by returning to step 1. 3. When an address is found to be unique it is sent to the new node.

The checking for addresses in step 2 may be followed by a DAD as described above. This DAD may be performed both from the responding node and from the requesting node, depending on the system specifications. After the address control a chosen number of nodes in the network is updated.

5. References [1] S. Alexander and R. Droms, "Dynamic Host Configuration Protocol', IETF RFC 2131, March 1997.

[2] C.E. Perkins, J.T. Malinen, R. Wakikawa, E. M. Royer and Y. Sun, "IP Address Autoconfiguration for Ad Hoc Networks", IETF Internet Draft, Work in Progress, November 2001.

[3] S. Nesargi and R. Prakash, "MANETconf: Configuration of Hosts in a Mobile Ad Hoc Network", INFOCOM 2002.

[4] J-H. Jeong, H-W. Cha, J-S. Park and H-J. Kim, "Ad Hoc IP Address Autoconfiguation" , IETF Internet Draft, Work in Progress, May 2003.

[5] C. E. Perkins, E. M. Belding-Royer and S. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing". IETF RFC 3561 July 2003.

Claims

C l a i m s

1. System for including a new node into a computer network comprising a number of nodes, wherein the new node includes a requester unit for transmitting a request signal for participating in the network, and at least one of said nodes existing in the network comprising a responder unit, each responder unit including a list of addresses of the nodes already participating in the network and address generation means for generating a new address and transmitting this to the requester unit, the new node thus being provided with an address and being included in the network, and said responder units in the network updating the list of network addresses, and wherein at least one of said requester and responder units comprising duplicate address detection means for detecting duplicate addresses in the network, and said address list is the routing table of the node.

2. System according to claim 1 , wherein the duplicate address detection means comprises an address assigning cache, containing the addresses of each node in the network, the method comprising the step of the responder unit comparing the addresses in said list of addresses with the addresses in the cache.

3. System according to claim 1, wherein enough nodes participating in the network are provided with broadcast means, for broadcasting signals to a number of other nodes in the system, e.g. for communicating the proposed new address to the network nodes..

4. System according to claim 1, wherein a number of nodes participating nodes in the network are adapted to forward information to and from the requester unit, such that all nodes participating in the network are reachable.

5. Method for admitting a new node into a network by providing an address in the network, said new node comprising a request unit for transmitting a request to the network and said network including at least one node comprising a responder unit for receiving request signals, comprising the steps of:

1. upon the arrival of a request signal, assigning an address to the new node 2. checking the node address list in the responding node, said address list being constituted by the routing table of the responding nodes, and if address is found in said list, return to step 1 3. send address to the new node, and wherein a duplicate address detection check is performed in at least one of said responding nodes and new node.

6. Method according to claim 5, wherein after step 2, performing duplicate address detection check in the responding node.

7. Method according to claim 5, wherein after step 3, performing duplicate address detection check in the new node.

8. Method according to claim 5, wherein after step 3, comprising the step of updating the address lists of a chosen number of nodes in the network.