Method and apparatus for determining whether an alias is available to uniquely identify an entity in a communications system

Claims

What is claimed is:

1. In a communication system for transferring data between a plurality of devices, a method used by a first entity for determining whether an alias is available to uniquely identify said first entity, said first entity being a networkable computer resource, the method comprising the steps of:

A) said first entity broadcasting a first signal to a first local area network, wherein said first entity is directly coupled to said first local network, wherein said first signal includes said alias, said alias including a zone name,

B) a first routing means of said first local area network translating said first signal into a second signal which includes said alias, said first routing means being coupled to at least one second routing means which is directly coupled to at least one second local area network of said communication system,

C) said first routing means forwarding said second signal to said at least one second routing means,

D) said at least one second routing means computing a zone multicast address from said zone name,

E) said at least one second routing means translating said second signal into a third signal which includes said alias and said zone multicast address,

F) if said at least one second local area network includes a first set of nodes having said zone multicast address, then

F1) said at least one second routing means multicasting said third signal over said second network,

F2) if a second entity of said first set of nodes has said alias, then said second entity transmitting a fourth signal to said first entity, said fourth signal including it network address of said second entity,

G) if said first entity receives said fourth signal, then

G1) said first entity entering said network address into a names table in said first entity, said names table associating said network address with said alias, and

G2) said first entity determining that said alias is not available to uniquely identify said first entity; and

H) if said first entity does not receive said fourth signal, said first entity determining that said alias is available to uniquely identify said first entity.

2. The method of claim 1 wherein said networkable computer resource includes a printer.

3. The method of claim 1 wherein said alias further comprises a type and object portion.

4. The method of claim 1 wherein said first signal comprises an identifier uniquely identifying said first signal, said fourth signal including said identifier to associate said fourth signal with said first signal.

5. In a communication system for transferring data between a plurality of devices, an apparatus in a first entity for associating an alias with a network address, said first entity being a networkable computer resource, the apparatus comprising:

a. transmission circuitry directly coupleable to a first local area network of said communication system;

b. reception circuitry coupleable to said first local area network; and

c. association circuitry coupled to said reception circuitry;

wherein said transmission circuitry broadcasts a first signal to said first local area network when said transmission circuitry is coupled to said first local area network, wherein said first signal includes said alias, said alias including a zone name,

wherein a first routing means of said first local area network translates said first signal into a second signal which includes said alias, and forwards said second signal to at least one second routing means,

wherein each at least one second routing means is directly coupled to at least one second local area network of said communication system,

wherein said at least one second routing means computes a zone multicast address from said zone name, translates said second signal into a third signal which includes said alias and said zone multicast address, and multicasts said third signal to a first set of nodes having said zone multicast address,

wherein if a second entity of said first set of nodes has said alias, then said second entity transmits a fourth signal to said first entity, said fourth signal including said network address of said second entity,

wherein if said second entity transmits said fourth signal, then said reception circuitry receives said fourth signal, and

wherein said association circuitry enters said network address into a names table in said first entity if said fourth signal is received, said names table associating said network address with said alias.

6. The apparatus of claim 5 wherein said networkable computer resource includes a printer.

7. The apparatus of claim 6 wherein said transmission circuitry further includes a means for including a type and object portion within said alias.

8. The apparatus of claim 6 wherein said transmission circuitry further includes a means for including a unique identifier in said first signal for uniquely identifying said first signal, wherein said fourth signal includes said unique identifier to associate it with said first signal.

9. In a communication system for transferring data between a plurality of devices, a method used by a first entity for associating an alias with a network address, said first entity being a networkable computer resource, comprising the steps of:

A) determining whether said first entity is directly coupled to a first local area network,

B) if said first entity is directly coupled to a first local area network, then

B1) said first entity broadcasting a first signal to said first local area network, wherein said first signal includes said alias, said alias including a zone name,

B2) a first routing means of said first local area network translating said first signal into a second signal which includes said alias,

B3) determining whether at least one second routing means is directly coupled to at least one second local area network of said communication system,

B4) if at least one second routing means is directly coupled to at least one second local area network of said communication system, then

B4a) said first routing means forwarding said second signal to said at least one second routing means,

B4b) said at least one second routing means computing a zone multicast address from said zone name,

B4c) said at least one second routing means translating said second signal into a third signal which includes said alias and said zone multicast address,

B4d) determining whether a first set of nodes on said second local area network has said zone multicast address.

B4e) if said first set of nodes has said zone multicast address, then

i) said at least one second routing means multicasting said third signal to said first set of nodes having said zone multicast address,

ii) if a second entity of said first set of nodes has said alias, then

said second entity transmitting a fourth signal to said first entity, said fourth signal including said network address of said second entity; and

said first entity receiving said fourth signal, said first entity entering said network address into a names table in said first entity, said names table associating said network address with said alias.

10. The method of claim 9 wherein said networkable computer resource includes a printer.

11. The method of claim 9 wherein said alias further comprises a type and object portion.

12. The method of claim 9 wherein said first signal comprises an identifier for uniquely identifying said first signal, said fourth signal including said identifier to associate said fourth signal with said first signal.

13. In a communication system for transferring data between a plurality of devices, a method used by a networkable printer for determining whether any entity in said communication system has a particular alias, comprising the steps of:

A) determining if said networkable printer is directly coupled to a first local area network of said communication system,

B) if said networkable printer is directly coupled to a first local area network of said communication system, then

B1) Said networkable printer broadcasting a first signal to said first local area network, wherein said first signal includes said particular alias, said particular alias including a zone name,

B2) a first routing means of said first local area network translating said first signal into a second signal which includes said particular alias,

B3) said first routing means forwarding said second signal to at least one second routing means directly coupled to at least one second local area network of said communication system,

B4) said at least one second routing means computing a zone multicast address from said zone name,

B5) said at least one second routing means translating said second signal into a third signal which includes said particular alias and said zone multicast address,

B6) said at least one second routing means multicasting said third signal to a first set of nodes having said zone multicast address,

B7) if an entity of said first set of nodes has said particular alias, then

said entity transmitting a fourth signal to said networkable printer, said fourth signal including said network address of said entity; and

said networkable printer receiving said fourth signal and entering said network address into a names table in said networkable printer, said names table associating said network address with said particular alias.

14. The method of claim 13 wherein said particular alias further comprises a type and object portion.

15. The method of claim 13 wherein said first signal comprises an identifier for uniquely identifying said first signal, said fourth signal including said identifier to associate said fourth signal with said first signal.

16. A method used by a networkable printer for determining whether any entity in a communication system has a particular alias, wherein said networkable printer is directly coupled to a first local area network of said communication system, comprising the steps of:

a. said networkable printer broadcasting a first signal to said first local area network, wherein said first signal includes said particular alias,

b. forwarding and multicasting said first signal by routers to a first set of nodes having a zone multicast address derived from said particular alias,

c. if an entity of said first set of nodes has said particular alias, then

c1) said entity transmitting a second signal to said networkable printer, said second signal including said network address of said entity;

c2) said networkable printer receiving said second signal, and

c3) said networkable printer entering said network address into a names table in said networkable printer, said names table associating said network address with said particular alias.

17. The method of claim 16 wherein said particular alias further comprises a type and object portion.

18. The method of claim 16 wherein said first signal comprises an identifier for uniquely identifying said first signal, said second signal comprising said identifier to associate said second signal with said first signal.

19. In a communication system for transferring data between a plurality of devices, an apparatus in a networkable printer for determining a network address of any entity in said communication system having a particular alias, the apparatus comprising:

a. transmission circuitry directly coupled to a first local area network of said communication system,

b. reception circuitry coupled to said first local area network; and

c. association circuitry coupled to said reception circuitry;

wherein said transmission circuitry broadcasts a first signal to said first local area network of said communication system, wherein said first signal includes said particular alias;

wherein said first signal is forwarded and eventually multicast by routers to a first set of nodes having a zone multicast address derived from said particular alias;

wherein if any entity of said first set of nodes has said particular alias, said any entity transmits a second signal to said networkable printer, said second signal including said network address of said any entity;

wherein said reception circuitry receives said second signal: and

wherein said association circuitry enters said network address into a names table in said networkable printer if said second signal is received, said names table associating said network address with said particular alias.

20. The apparatus of claim 19 wherein said transmission circuitry further includes a means for including a type and object portion within said particular alias.

21. The apparatus of claim 19 wherein said transmission circuitry further includes a means for including a unique identifier in said first signal for uniquely identifying said first signal, wherein said second signal includes said unique identifier to associate it with said first signal.

22. A method used by a networkable computer resource for avoiding alias duplication in a network, said networkable computer resource having at least one alias, said network having a plurality of zones, said networkable computer resource belonging to a first zone of said plurality of zones, the method comprising the steps of:

A) when an entity in said network is performing an alias registration operation, performing the steps of:

A1) determining if a packet multicast over said network in response to said alias registration operation includes a zone multicast address corresponding to said first zone;

A2) if said packet includes a zone multicast address corresponding to a zone other than said first zone, then ignoring said packet;

A3) if said packet includes a zone multicast address corresponding to said first zone, then performing the steps of:

A3a) determining if said packet is a look-up packet which includes a second alias;

A3b) if said packet is a look-up packet which includes said second alias, then performing the steps of:

i) determining if said second alias included in said look-up packet matches said at least one alias;

ii) if said second alias included in said look-up packet matches said at least one alias, then transmitting a response packet over said network, said response signal including a network address uniquely identifying said networkable computer resource;

B) initiating an alias registration operation to determine whether a particular alias is in use by any entity in said first zone before using said particular alias by performing the steps of:

B1) transmitting a broadcast request packet to cause a router in said network to multicast a lookup-packet containing said particular alias;

B2) receiving a lookup response packet from an entity using said particular alias if said particular alias is in use by any entity in said first zone; and

B3) determining that said particular alias in not in use by any entity if no lookup response packet is received.

23. The method of claim 22 wherein said second alias includes one or more alphabetic characters, the method further comprising the step of converting said one or more alphabetic characters to a selected case of either uppercase or lowercase prior to performing said step of determining if said second alias included in said look-up packet matches said at least one alias.

24. The method of claim 22 wherein said step of determining if said packet multicast by said entity in said network over said network includes said zone multicast address corresponding to said first zone includes the step of examining a zone name field of a network binding protocol tuple contained within said packet.

25. The method of claim 22 further comprising the step of maintaining a names table containing alias-to-entity address mappings of all network visible entities in the networkable computer resource, said names table storing said at least one alias.

26. The method of claim 25 wherein said step of determining if said second alias included in said look-up packet matches said at least one alias comprises the steps of:

comparing said second alias to all aliases contained in said names table; and

transmitting said response packet over said network if said second alias matches any alias in said names table.

27. A method used by a networkable computer resource for avoiding alias duplication in a network, said networkable computer resource having a first alias, said network having a plurality of zones, said networkable computer resource belonging to a first zone of said plurality of zones, the method comprising the steps of:

A) determining if a packet multicast by an entity in said network over said network includes a zone multicast address corresponding to said first zone;

B) if said packet includes said zone multicast address corresponding to a zone other than said first zone, then ignoring said packet;

C) if said packet includes said zone multicast address corresponding to said first zone, then performing the steps of:

C1) determining if said packet is a look-up packet which includes a second alias;

C2) if said packet is a look-up packet which includes said second alias, then performing the steps of:

i) determining if said second alias included in said look-up packet matches said first alias;

ii) if said second alias included in said look-up packet matches said first alias, then transmitting a response packet over said network, said response signal including a network address uniquely identifying said networkable computer resource.

28. The method of claim 27 wherein said second alias includes one or more alphabetic characters, the method further comprising the step of converting said one or more alphabetic characters to a selected case of either uppercase or lowercase prior to performing said step of determining if said second alias included in said look-up packet matches said first alias.

29. The method of claim 27 wherein said step of determining if said packet multicast by said entity in said network over said network includes said zone multicast address corresponding to said first zone includes the step of examining a zone name field of a network binding protocol tuple contained within said packet.

30. The method of claim 27 further comprising the step of maintaining a names table containing alias-to-entity address mappings of all network visible entities in the networkable computer resource.

31. The method of claim 30 further comprising the steps of:

comparing said second alias to all aliases contained in said names table; and

transmitting said response packet over said network if said second alias matches any alias in said names table.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to an apparatus and method for transferring data between a source and a plurality of receiving data processing devices. More particularly, this invention relates to determining the address of a process residing in a device having an alias ("entity name").

2. Background Information

In the computing industry, it is quite common to transfer data and commands between a plurality of data processing devices, such as computers, printers, displays, terminals, and other network resources. Interconnection of computers and other peripheral devices principally developed in the early 1970s with the advent of computer networking systems which permitted the distribution of access to computing resources beyond the immediate proximity of a mainframe computer.

Recently, "local area networks" (LANs) have been developed which allow transfer of data between a localized set of computing and peripheral devices, typically in the same geographical area such as one building or a plurality of buildings closely situated together. Examples of such LANs may be found in U.S. Pat. Nos. 4,063,220, 4,661,902 and 4,689,786. In the APPLETALK.RTM. brand (a trademark of Apple Computer, Inc.) network system, each "node" or computer, printer, peripheral, and other network resource, previously had a unique 8 bit identifier which allowed the node to filter out transmissions directed to other nodes. Since the 8 bit identifier, or node ID, was 8 bits in length, the number of nodes or computers and peripherals and other network resources in the LAN was limited to 254 (this number is less the values where all the bits are set and all of the bits, are clear, which are reserved). This has resulted in a limitation in the utility of such LANs, since an expansion beyond the 254 node limit required the connection of additional hardware to the system, such as network routers and/or other hardware devices. This resulted in an increase of the complexity of the local area network, as well as an increase in its cost.

As will be described, the present invention provides a local area network for communication and resource sharing among various computers, servers, disks, printers, modems, and other data processing devices, peripherals and network resources, which increases the current 254 node limit to nearly 2.sup.24 or approximately 16 million nodes while remaining compatible with earlier non-extended local area networks which may still be connected to it through network routers. Specifically, this invention relates to the determining of the address of a process in a node having a given alias ("entity name").

SUMMARY AND OBJECTS OF THE INVENTION

One object of the present invention is to determine the location of a device on a communication system having an alias.

Another object of the present invention is to determine whether an alias is presently being used on a communication system.

Another object of the present invention is to determine the multicast address of a node having a particular zone name.

Another object of the present invention is to update zone information contained in a node.

These and other objects of the present invention are provided for by a method, in a communication system for transferring data between a plurality of devices, for determining the location of a first entity. A second entity transmits a first signal to a first routing means connected to a first local network of the communication system, wherein the first signal includes an alias, wherein the alias includes a zone name, and the first local network includes the second entity. The first routing means translates the first signal into a second signal which includes the alias, and transmits the second signal to at least one second routing means, each at least one second routing means coupled to at least one second local network of the communication system. Each at least one second routing means translates the second signal into a third signal which includes the alias, and transmits the third signal to a first set of nodes. The first set of nodes comprises at least one first node, and each of the first set of nodes has a first zone multicast address, wherein the value of the first zone multicast address is equivalent to a second zone multicast address which was computed from the zone name. Each of the first set of nodes determines whether the zone name contained within the alias is equal to a zone identifier contained in each of the first set of nodes. Each of the first set of nodes having the zone identifier equal to the zone name contained within the alias becomes a second set of nodes, wherein the second set of nodes comprises at least one second node. Each of the second set of nodes then determines whether the alias contained within the third signal is equal to alias information contained within each of the second set of nodes. The first entity, being a part of the second set of nodes and having alias information contained within it that is equal to the alias contained within the third signal, transmits a fourth signal to the second entity, wherein the fourth signal includes the address of the first entity.

These and other objects of the present invention are provided for by a method for determining a zone multicast address from a zone name by first initializing a hash value to zero. Then each byte comprising the zone name is converted to an uppercase value. For each byte comprising the zone name, each uppercase value for each byte comprising the zone name is added to and then stored in the hash value and then the hash value is rotated one bit left. If the final hash value equals zero then all bits in the hash value are set. An index value is then determined by computing the hash value modulo a first value, wherein the first value is the number of entries in a table containing a plurality of multicast addresses. This index value is then used to retrieve a first multicast address and the first multicast address is stored into a second value.

These and other objects of the present invention are provided for by a method used by a first entity for changing the zone in which it resides when it receives a first signal, the first signal containing old zone information and new zone information. The old zone information contained in the first signal comprises a zone name, and the new zone information contained within the first signal and the zone information contained within the first entity each comprise a zone name and a zone multicast address. If the old zone information contained within the first signal is equivalent to zone information contained within the first entity, then the zone information in the first entity is set equal to the new zone information contained within the first signal.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example and not limitation and the figures of the accompanying and in which like references indicate similar elements and in which:

FIG. 1 shows a local area network (LAN) on which the preferred embodiment of the present invention is implemented.

FIG. 2 shows a detailed representation of one computer in the Local Area Network.

FIG. 3 shows packets used for transmission of data between nodes in the preferred embodiment.

FIG. 4 shows a representation of the various protocol stacks used in the preferred embodiment.

FIG. 5 shows the protocol stacks and data link organization as it relates to translation of protocol addresses into hardware addresses in the preferred embodiment.

FIG. 6 shows address resolution protocol packets which are used in the preferred embodiment for determining the availability of certain protocol addresses.

FIG. 7 shows a detailed representation of a protocol address used in data packets in the preferred embodiment.

FIG. 8 shows an internetwork which connects several local area networks in the preferred embodiment, including routers used for routing information from one local area network to another.

FIG. 9 shows a packet used for transmittal of data from one node in the internet to another node.

FIG. 10 shows the process of generating a checksum used in the preferred embodiment.

FIG. 11A and 11B show packets used to transmit information to and from a router and nodes in the preferred embodiment for obtaining network information.

FIG. 12 shows a packet used for obtaining name information using the Network Binding Protocol (NBP).

FIG. 13 shows a detailed representation of an "NBP Tuple" used to keep track of name information in the preferred embodiment.

FIG. 14 is a representation of device location using packets transmitted by a requesting node, which packets are transformed by internet routers en route to the device.

FIG. 15 is a representation of a packet used in the preferred embodiment for updating zone information for a node in a network.

FIG. 16 is a process flow diagram of the method used by the preferred embodiment for network device location using multicast.

FIG. 17 is a process flow diagram illustrating the operation of a transmitting node in a name registration operation.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

A local area network node startup method for assigning a unique address is described. In the following description for the purposes of explanation, specific numbers, bytes, registers, addresses, times, signals, and formats are set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to one skilled in the art that the present invention may be practiced without the specific details. In other instances, well known circuits and devices are shown in block diagram form in order to not unnecessarily obscure the present invention.

Referring to FIG. 1, the present invention may include a plurality of data processing devices or network resources identified generally by the numbers 101 through 105. These network resources may include, among other things, printers, modems, memory, disk devices, etc. For the purposes of this specification, all data processing and peripheral devices which are coupled to the network are collectively referred to as "entities." As shown, the entities 101 through 105 are interconnected for data transfer to one another by common cable 110. The entities are coupled to cable 110 by connection modules 106 on FIG. 1. It will be appreciated by one skilled in the art that cable 110 may comprise any shared media, such as co-axial cable, fiber optics, radio channel, twisted pair cable, or the like. The present invention permits access to various network resources such as data stored in local memories or disk and the common use of printers without the need to predefine addresses for each device coupled to cable 110.

Note that the network 100, shown in FIG. 1, in the preferred embodiment may be an ETHERNET (U.S. Pat. No. 4,063,220) standard networking system, under the Institute of Electrical and Electronic Engineers (IEEE) specification 802.3, or in an alternative embodiment a token-ring standard networking system under IEEE 802.5 or any other type of networking system such as fiber distributed data interface (FDDI) networking system. As is known in the art, the ETHERNET networking system is capable of transmission at rams of approximately ten megabits per second and belongs to the class of LAN's known as CSMA/CD (carder sense multiple access with collision detection) systems. Using the CSMA/CD protocol, each data processing device 101-105 may not transmit on the network cable 110 as long as traffic is present (i.e. another node is already transmitting on cable 110). As soon as a node detects that cable traffic has ceased on cable 110, the node will wait for a certain mandatory time period to pass to allow the network to settle, and then the node will begin to transmit its data. This CSMA/CD protocol is used in conformance with IEEE specification 802.3.

In an alternative embodiment, network 100 may be a standard token-ring networking system. In this case, networking cable 110 further couples nodes 101 and 105 directly so that the network 100 forms a complete loop. Data travels unidirectionally in the network 100 at a data rate of approximately four to sixteen megabits per second. Each connection module 106 is a "repeater," that is, when data is received from an adjoining node "upstream" from the receiving node, the token is placed back on the network cable 110. This is done after the node has examined the token to see if the node must act upon the token, and transform it accordingly, if required. In this alternative embodiment for network 100, the token-ring topology is driven in accordance with IEEE 802.5 specifications.

FIG. 2 illustrates one node on network 100, for instance 103, which may be a computer system upon which the preferred embodiment of the present invention is implemented. Computer system 103 comprises a bus or other communication means 250 for communicating information, a processing means 251 coupled with bus 250 for processing information, a random access memory (RAM) or other dynamic storage device 252 (commonly referred to as main memory) coupled to bus 250 for storing information and instructions for processor 251. Computer system 103 also comprises a read only memory (ROM) and/or other static storage device 253 coupled to bus 250 for storing static information and instructions for the processor 251, a data storage device 254, such as a magnetic disk or optical disk and disk drive, coupled to bus 250 for storing information and instructions. Computer system 103 further comprises a display device 255, such as a cathode ray tube (CRT), coupled to bus 250 for displaying information to the computer user, an alpha-numeric input device 256, including alpha numeric and other keys, coupled to bus 250 for communicating information and command selections to processor 251, and may also comprise a cursor control device 257, such as a mouse, a track ball, or cursor direction keys, coupled to bus 250 for communicating direction information and command selections to processor 251 and for controlling cursor movement. Computer system 103 may also be coupled to connection module 106 via bus 250.

In the preferred embodiment computer system 103 is one of the MACTINTOSH family of personal computers, such as the MACINTOSH SE or MACINTOSH II manufactured by Apple Computer, Inc. of Cupertino, Calif. Processor 251 is one of the 68000 family of microprocessors manufactured by Motorola, Inc.