Dynamic address assignment in an arbitrarily connected network

• US 5,745,699 A
• Filed: 10/18/1996
• Issued: 04/28/1998
• Est. Priority Date: 09/24/1993
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Oppenheimer, Alan, Mullins, Jeffery L., Zweig, Jonathan Marcus, Ritter, Michael Walker, Lynn, Kerry Eugene
• Primary Examiner(s): Geckil, Mehmet B.
• Application Number:
  US08/733,540
• Time in Patent Office: 557 Days
• Field of Search: 395/200.16, 395/85.13-85.16, 395/800, 395/200.5, 395/200.75, 395/200.53, 395/200.54, 395/200.57
• US Class Current: 709/245
• CPC Class Codes: G06F 12/0669 with decentralised address assignment
• CPC Class Codes: H04L 61/10 of different types
• CPC Class Codes: H04L 61/5007 Internet protocol [IP] addresses
• CPC Class Codes: H04L 61/5084 Providing for device mobility network addressing or numbering for mobility support in wireless networks H04W8/26; mobile IP H04W80/04
• CPC Class Codes: H04L 61/5092 by self-assignment, e.g. picking addresses at random and testing if they are already in use
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support

Abstract

A method and apparatus for assigning a unique network address to a first node within a network which is arbitrarily connected. The first node may include a shared network resource, such as a networked printer device, or a modem, in addition to a stand-alone computer system. The network may include a network which is wireless, wherein various nodes comprise radio transceiver circuitry, including radio frequency modems. A first provisional network address for use in assigning the unique network address is determined by the first node. The first node broadcasts probes containing the provisional network address until a first probe response to one of the probes is received or a first interval of time elapses. If the first probe response to one of the probes is received, then the first node determines a second provisional network address and repeats selection of the address and broadcasting, until no probe response is received in the first interval of time. Using the first provisional network address, the first node broadcasts forward probes in the network until a second probe response to one of the forward probes is received by the first node or a second period of time has transpired. If a second probe response to one of the forward probes is received by the first node, then the first node determines a third provisional network address and repeats the steps of selecting, broadcasting probes and forward probes until no the response is received in the second interval of time. The final provisional network address may be used as the unique network address for the first node.

Claims

1. In a network comprising a first node and a second node in wireless communication, a method of assigning a unique network address within said network to said first node, comprising the following steps:

a. said first node in said network determining a first provisional network address for use in assigning said unique network address;

b. said first node broadcasting a first probe containing said first provisional network address until a first probe response to said first probe is received or a first interval of time has transpired;

c. if said first probe response to said first probe is received, then said first node determining a second provisional network address and repeating steps b and c, said second provisional network address becoming said first provisional network address, until no said first probe response is received in said first interval of time;

d. using said first provisional network address, broadcasting by said second node, a second probe in said network until a second probe response to said second probe is received by said first node or a second period of time has transpired, wherein said second probe comprises a forward probe that includes a radius remaining number indicating whether another node in said network may re-broadcast said forward probe;

e. if said second probe response to said second probe is received, then said first node determining a third provisional network address and repeating steps b through e, said third provisional network address becoming said first provisional network address, until no said second probe response is received in said second interval of time; and

f. using said first provisional network address as said unique network address for said first node.

2. The method of claim 1 wherein said first node comprises a shared network resource.

3. The method of claim 2 wherein said shared network resource comprises a networked printer.

4. The method of claim 1, wherein said forward probe further comprises a probe number indicating a number of times said forward probe has been broadcast.

5. The method of claim 1, wherein said forward probe further comprises a maximum probe number indicating a maximum number of times said forward probe may be broadcast.

20. The method of claim 1, wherein said network comprises an arbitrarily connected network.

6. In a network comprising a first node and a second node in wireless communication, a method of assigning a unique network address within said network to said first node, comprising the following steps:

(1). said first node in said network determining a first provisional network address for use in assigning said unique network address;

(2). said first node broadcasting a first probe containing said first provisional network address until a first probe response to said first probe is received or a first interval of time has transpired;

(3). if said first probe response to said first probe is received, then said first node determining a second provisional network address and repeating steps b and c, said second provisional network address becoming said first provisional network address, until no said first probe response is received in said first interval of time,

(4). using said first provisional network address, broadcasting by said second node, a second probe in said network until a second probe response to said second probe is received by said first node or a second period of time has transpired, wherein said second node further performs the following steps;

a. receiving said second probe from a transmitting node;

b. determining if said first provisional network address is in use by said second node, and if so, transmitting said second probe response to said transmitting node;

c. if said first provisional network address is not in use by said second node, then said second node determining if said first provisional network address is in use by a third node which has communicated with said second node;

d. if said first provisional network address is in use by said third node, then said second node transmitting said second probe response to said transmitting node including a hardware address of said third node;

e. if said second probe has not been re-broadcast a maximum specified number of times, then storing a hardware address of said transmitting node and re-broadcasting said second probe;

(5). if said second probe response to said second probe is received, then said first node determining a third provisional network address and repeating steps b through e, said third provisional network address becoming said first provisional network address, until no said second probe response is received in said second interval of time; and

(6). using said first provisional network address as said unique network address for said first node.

7. The method of claim 6 further comprising the step of waiting a first random interval of time prior to re-broadcasting said second probe.

8. The method of claim 6 further comprising the step of waiting a second random interval of time prior to transmitting said second probe response to said transmitting node.

9. The method of claim 6 further comprising the steps of:

a. receiving said second probe response to said second probe;

b. retrieving said hardware address of said transmitting node; and

c. re-broadcasting said second probe response to said hardware address of said transmitting node.

10. The method of claim 9 further comprising the step of waiting a third random interval of time prior to re-broadcasting said second probe response.

11. The method of claim 6 wherein said step of storing said hardware address of said transmitting node further comprises the step of storing said first provisional network address, and a hardware address of said first node in an entry wherein said hardware address of said transmitting node, said first provisional network address, and said hardware address of said first node are associated with one another.

12. The method of claim 6, wherein said determining step further comprises determining if said first provisional network address is in use by said second node, and if so, transmitting said second probe response to said transmitting node including a hardware address of said second node.

13. In a network comprising a first node and a second node in wireless communication, a method for determining a unique network address for said first node, comprising the following steps:

a. said first node selecting a provisional network address and broadcasting a first signal to said second node until a unique provisional network address is determined for said first node;

b. said first node broadcasting a second signal to said second node to determine if said unique provisional network address is being used by a third node which may exist in said network, wherein said second signal comprises a forward probe including a radius remaining number indicating whether said second node or another node may re-broadcast said forward probe;

c. said second node broadcasting said second signal to said third node which may exist in said network to determine if said third node is using said unique provisional network address;

d. if said third node which may exist in said network is using said unique provisional network address, then repeating steps a-c until it is determined that said third node is not using said unique provisional network address; and

e. using said unique provisional network address as said unique network address.

14. The method of claim 13, wherein said first node comprises a shared network resource.

15. The method of claim 14, wherein said shared network resource comprises a shared network printer.

16. The method of claim 13, wherein said network comprises an arbitrarily connected network.

17. The method of claim 13, wherein said forward probe further comprises a probe number indicating a number of times said first node has broadcast said forward probe.

18. The method of claim 13, wherein said forward probe further comprises a maximum probe number indicating a maximum number of times said first node may broadcast the forward probe.

19. An apparatus in a network having a first, second, and third nodes in wireless communication, said apparatus determining a unique network address for said first node comprising:

a. selection circuitry in said first node selecting a provisional network address and broadcasting a first signal to said second node directly connected to said first node until a unique provisional network address is determined for said first node;

b. broadcast circuitry in said first node broadcasting a second signal to said second node to determine if said unique provisional network address is being used by said third nodes, if any, not directly connected to said first node, said second node comprising a forward probe including a radius remaining number indicating whether said third nodes, if any, in said network may re-broadcast said forward probe;

c. receiver and broadcast circuitry in said second node re-broadcasting said second signal to said third nodes to determine if said third nodes are using said unique provisional network address;

d. iteration circuitry in said first node iteratively activating elements a-c if said third nodes are using said unique provisional network address until it is determined that none of said third nodes are using said unique provisional network address;

e. establishment circuitry using said unique provisional network address as said unique network address for said first node;

f. first tables in said first, second and third nodes associating network and hardware addresses; and

g. second tables in said first, second and third nodes associating a signal response with an immediate transmitter of said second signal.

21. A data processing apparatus comprising:

selection circuitry selecting a provisional network address;

receiver circuitry coupled to said selection circuitry and for coupling to an intermediate node which may exist in a network;

broadcast circuitry coupled to said selection circuitry and for communicating in a wireless manner with said intermediate node which may exist in said network, said selection circuitry causing said broadcast circuitry to broadcast a first signal to said intermediate node until a unique provisional network address is determined for said data processing apparatus, said selection circuitry causing said broadcast circuitry to further broadcast a second signal to said intermediate node to determine if said unique provisional network address is being used by another node which may exist in said network, said second signal for causing a broadcasting of a third signal by said intermediate node to said another node which may exist in said network and for determining if said another node is using said unique provisional address, said second signal comprising a forward probe including a radius remaining number indicating whether said intermediate node or said another node may re-broadcast said forward probe, said data processing apparatus using said unique provisional network address as a unique network address if said intermediate node and said another node are not using said unique provisional network address.

22. The data processing apparatus of claim 21, wherein said data processing apparatus comprises a shared network resource.

23. The data processing apparatus of claim 22, wherein said shared network resource comprises a shared network printer.

24. The data processing apparatus of claim 21, wherein said forward probe further comprises a probe number indicating a number of times said selection circuitry causes said broadcast circuitry to broadcast said forward probe.

25. The data processing apparatus of claim 21, wherein said forward probe further comprises a maximum probe number indicating a maximum number of times said selection circuitry may cause said broadcast circuitry to broadcast said forward probe.

26. The data processing apparatus of claim 21, wherein said data processing node directly communicates with said intermediate node.

27. The data processing apparatus of claim 21, wherein data processing apparatus directly communicates with said another node.

28. The data processing apparatus of claim 21, wherein said data processing apparatus indirectly communicates with said another node through said intermediate node.

29. A data processing apparatus comprising:

receiver circuitry for coupling to an acquiring node in a network; and

broadcast circuitry coupled to said receiver circuitry and for communicating in a wireless manner with the acquiring node and another node in said network, said receiver circuitry for receiving a first signal from said acquiring node, said first signal for determining whether said data processing apparatus is using a network address of said acquiring node, said receiver circuitry further for receiving a second signal from said acquiring node, wherein said second signal comprises a forward probe including a radius remaining number indicating whether said forward probe may be re-broadcast by said data processing apparatus or by said another node, said second signal causing a broadcasting of a third signal by said broadcast circuitry to said another node, said third signal for determining whether said another node is using said network address of said acquiring node.

30. The data processing apparatus of claim 29, wherein said second signal is for determining whether said data processing apparatus is communicating with said another node which is using said network address.

31. The data processing apparatus of claim 29, wherein said data processing apparatus comprises a shared network resource.

32. The data processing apparatus of claim 31, wherein said shared network resource comprises a shared network printer.

33. The data processing apparatus of claim 29, wherein said forward probe further comprises a probe number indicating a number of times said acquiring node has broadcast said forward probe.

34. The data processing apparatus of claim 29, wherein said forward probe further comprises a maximum probe number indicating a maximum number of times said acquiring node may broadcast said forward probe.

35. The data processing apparatus of claim 29, wherein said data processing apparatus directly communicates with said acquiring node and said another node, and said acquiring node directly communicates with said another node.

36. The data processing apparatus of claim 29, wherein said data processing apparatus directly communicates with said acquiring and said another node, and said acquiring node indirectly communicates with said another node.

37. The data processing apparatus of claim 29, wherein said data processing apparatus further comprises a table communicating with said receiver circuitry and said broadcast circuitry, said table associating said forward probe with said acquiring node.

38. In a wireless network, a method of assigning a unique network address within said wireless network to a first node, comprising the following steps:

a. said first node in said wireless network determining a first provisional network address for use in assigning said unique network address;

b. said first node broadcasting a first probe containing said provisional network address until a first probe response to said first probe is received or a first interval of time has transpired;

c. if said first probe response to said first probe is received, then said first node determining a second provisional network address and repeating steps b and c, said second provisional network address becoming said first provisional network address, until no said first probe response is received in said first interval of time;

d. using said first provisional network address, broadcasting by a second node, a second probe in said wireless network until a second probe response to said second probe is received by said first node or a second period of time has transpired, wherein the second node is an arbitrary node in the wireless network and not a server or a bridge to another wireless network;

e. if said second probe response to said second probe is received, then said first node determining a third provisional network address and repeating steps b through e, said third provisional network address becoming said first provisional network address, until no said second response is received in said second interval of time; and

f. using said first provisional network address as said unique network address for said first node.

39. A method in a wireless network for determining a unique network address for a first node, comprising the following steps:

a. said first node selecting a provisional network address and broadcasting a first signal to a second node until a unique provisional network address is determined for said first node, wherein the second node is an arbitrary node in the wireless network and not a server or a bridge to another wireless network;

b. said first node broadcasting a second signal to said second node to determine if said unique provisional network address is being used by a third node which may exist in said wireless network;

c. said second node broadcasting said second signal to said third node which may exist in said wireless network to determine if said third node is using said unique provisional network address;

d. if said third node which may exist in said wireless network is using said unique provisional network address, then repeating steps a-c until it is determined that said third node is not using said unique provisional network address; and

e. using said unique provisional network address as said unique network address.

40. An apparatus in a wireless network, said apparatus determining a unique network address for a first node comprising:

a. selection circuitry in a first node selecting a provisional network address and broadcasting a first signal to a second node directly connected to said first node until a unique provisional network address is determined for said first node;

b. broadcast circuitry in said first node broadcasting a second signal to said second node to determine if said unique provisional network address is being used by third nodes, if any, not directly connected to said first node, wherein the second node is an arbitrary node in the wireless network and not a server or a bridge to another wireless network;

c. receiver and broadcast circuitry in said second node re-broadcasting said second signal to said third nodes to determine if said third nodes are using said unique provisional network address;

d. iteration circuitry in said first node iteratively activating elements a-c if said third nodes are using said unique provisional network address until it is determined that none of said third nodes are using said unique provisional network address;

e. establishment circuitry using said unique provisional network address as said unique network address for said first node;

f. first tables in said first, second and third nodes associating network and hardware addresses; and

g. second tables in said first, second and third nodes associating a signal response with an immediate transmitter of said second signal.

41. In a network comprising a first node and a second node in wireless communication, a method of assigning a unique network address within said network to said first node, comprising the following steps:

a. said first node in said network determining a first provisional network address for use in assigning said unique network address;

b. said first node broadcasting a first probe containing said first provisional network address until a first probe response to said first probe is received or a first interval of time has transpired;

c. if said first probe response to said first probe is received, then said first node determining a second provisional network address and repeating steps b and c, said second provisional network address becoming said first provisional network address, until no said first probe response is received in said first interval of time;

d. using said first provisional network address, transmitting by said second node, a second probe in said network until a second probe response to said second probe is received by said first node or a second period of time has transpired, said second probe comprising a forward probe including a radius remaining number indicating whether another node in said network may re-broadcast said forward probe;

e. if said second probe response to said second probe is received, then said first node determining a third provisional network address and repeating steps b through e, said third provisional network address becoming said first provisional network address, until no said second probe response is received in said second interval of time; and

f. using said first provisional network address as said unique network address for said first node.