# Patent

## Title
Methods of using beacon messages to discover devices across subnets

## Abstract

A method of discovering a device to be discovered in a communication network having multiple interconnected nodes includes transmitting, by a discoverer, at least one beacon signal including an IP address to the network. The device to be discovered receives the at least one beacon signal. The device to be discovered configures the IP address located in the at least one beacon signal. Additionally, the device to be discovered transmits an advertisement to a server specified by the discoverer.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This application is a continuation of and claims priority to U.S. patent application Ser. No. 13/552,022, filed Jul. 18, 2012, now allowed, which is incorporated herein in its entirety.
This application incorporates by reference in their entireties the following applications, all of which have the same filing date as the present application: U.S. application Ser. No. 13/551,998, “Systems and Methods of Detecting and Assigning IP Addresses to Devices with ARP Requests,” by Robitaille and Lemieux; U.S. application Ser. No. 13/552,022, “Systems and Methods of Using Beacon Messages to Discover Devices Across Subnets,” by Robitaille and Bouffard; U.S. application Ser. No. 13/552,063, “Systems and Methods of Discovering and Controlling devices without Explicit Addressing,” by Robitaille and Bouffard, and U.S. application Ser. No. 13/551,984, “Systems and Methods of Installing and Operating Devices without Explicit Network Addresses,” by Robitaille and Lemieux.


TECHNICAL FIELD
This invention is directed towards addressing the need for discovering when a device has been connected on a network. The discovery process shall be carried without the need for specific layer-2 or layer-3 addressing information about the device(s) to discover. This discovery process can be carried out by a discoverer/tester that is located in the network. The discoverer could either be implemented in a centralized manner or in a distributed manner.
BACKGROUND
There is a need to be able to discover any number of devices in any directly or indirectly reachable networks when they may not have any layer-2 and/or layer-3 addressing information since they do not actively participate in any of the normal network protocols in use.
Often the IDs or labels used by the protocols are not the same in both directions. If the device is not participating in the underlying protocols (e.g., MPLS, L2TPv3, GTP-U, etc.), the device (Small Form-Factor Pluggable (SFP) with a Field Programmable Gate Array (FPGA), Network Interface Device (NID), module or other platform) does not know what ID or label to use to communicate.
BRIEF SUMMARY
The device to be discovered must be able to be discovered without (but not excluding) being pre-programmed with information specific to the network or the control infrastructure.
After the discovery of a device, the discovered device can notify the discoverer of its presence via an Advertisement message. Once the server specified by the discoverer receives a valid Advertisement message, it can proceed with assigning a Layer-2 and/or Layer-3 address to the discovered device as required. Alternatively, the discoverer can provide information to the discovered device on how to obtain a layer-2 and/or layer-3 address from other services available on the network where the discovered device is located.
In one embodiment, the discovery process is used to enable an initial management access where a newly discovered device can be put in a state where it can receive further configuration, control, management or even new firmware information from a remote management entity, the management entity not necessarily being the same as the discoverer.
According to one aspect of the present invention, a method of discovering a device to be discovered in a communication network having multiple interconnected nodes includes transmitting, by a discoverer, at least one beacon signal including an IP address to the network. The device to be discovered receives the at least one beacon signal. The device to be discovered configures the IP address located in the at least one beacon signal. Additionally, the device to be discovered transmits an advertisement to a server specified by the discoverer.
According to a further aspect of the present invention, a system for discovering a device to be discovered in a communication network having multiple interconnected nodes includes the device to be discovered and a discoverer. The discoverer is coupled to a first processor and is configured to transmit at least one beacon message including an IP address to the communication network. The device to be discovered is coupled to a second processor and is configured to receive the at least one beacon message transmitted by the discoverer and to configure the IP address from the at least one beacon signal. The device to be discovered transmits an advertisement to a server specified by the discoverer in the at least one beacon signal.



BRIEF DESCRIPTION OF THE DRAWINGS
The foregoing and other advantages of the present disclosure will become apparent upon reading the following detailed description and upon reference to the drawings.
FIG. 1 illustrates a prior art DHCP message exchange between a device looking for an IP address and a server configured to provide a valid IP address to the requesting node;
FIG. 2 illustrates a prior art DHCP frame format;
FIG. 3 is a message flow diagram showing the exchange of a modified DHCP message between a discoverer and a device to be discovered and an Advertisement message returned by the detected or discovered device.



While the invention is susceptible to various modifications and alternative forms, specific embodiments have been shown by way of example in the drawings and will be described in detail herein. It should be understood, however, that the invention is not intended to be limited to the particular forms disclosed. Rather, the invention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the appended claims.
DETAILED DESCRIPTION
Different types of devices can be discovered in the network using one of the embodiments of the present invention. The term discoverer is used to describe a system (e.g., testing unit, router, remote node, etc.) that has direct or indirect access to the subnet where a device to be discovered is located. Since the discoverer is not necessarily directly located on the same subnet as the device(s) to be discovered, necessary addressing information about the discoverer is included in a beaconing message to allow the newly discovered device(s) to reply with an Advertisement message that will reach the discoverer.
When the device to discover is on the same IP subnet as the discoverer, layer-2 broadcast techniques may be used to facilitate the discovery process. Techniques based on layer-2 (broadcast or unicast) cannot be used when the device to discover is not located on the same IP subnet as the discoverer. For simplicity of installation and deployment, the device to discover needs to be discovered without any prior configuration settings in the device to discover. This means that the device to discover does not have any information about reaching a DHCP server located on a different IP subnet and is not allowed to proactively take steps to be discovered by a discoverer unless it is prompted to do so with a communication from a discoverer node. Such a restriction is needed since the device to discover may be embodied in a variety of systems that are not permanently installed in a network and may need to be activated only under specific circumstances and for a limited period of time. The discovery process therefore needs to be initiated by a discoverer node and needs to operate across one or more IP subnet.
In order for the discovery process to operate seamlessly across subnet boundaries, the discoverer needs to be able to craft a stateless packet that can be broadcast across one or more IP subnet and reach the device(s) to be discovered. Since there is no way to control the IP routers, gateways or firewall that may be installed at the boundaries of an IP subnet, the choice of the packet encoding used needs to be completely transparent to any router, gateway or firewall and must not conflict with the proper operation of the network and of the devices inside the network. The Dynamic Host Configuration Protocol (DHCP-RFC 2131) has been selected as the basis for this invention since it is widely supported by routers, gateways and firewalls and is stateless as far as these devices are concerned. Furthermore, DHCP messages are well suited for the discovery process since they are encapsulated as User Datagram Protocol (UDP) packets and can be broadcast on any subnet. When the discoverer is not located on the same subnet as the device to be discovered, the DHCP Relay function (RFC 3046) can be used to reach remote subnets in order to reach any undetected devices.
The DHCP protocol exchange is usually initiated by a device looking for an IP address it can use. The standard prior art DHCP message exchange is illustrated by FIG. 1. Such prior art DHCP message exchange is commonly referred to as a 4-way handshake. The 4-way handshake consists of sending a first message 101 DHCP DISCOVER from a device 102 looking for an IP address to a server or remote node 107 capable of offering an IP address. The DHCP DISCOVER message 101 is a broadcast message. The server replies with a DHCP OFFER message 111 that contains an IP address offered to the device 102. This DHCP OFFER 111 message is also a broadcast message. The device 102 replies with a third message, DHCP REQUEST message 121 to formally request that the offered IP address be assigned to it for the duration of a lease as determined by the server 107. The server 107 then replies with a fourth message, DHCP ACK 131 to confirm that the IP address is now officially assigned to the device 102 which can use it for the duration of the lease as determined by the server 107.
According to systems and methods of the present invention, the device to be discovered is passively waiting to be discovered. The discovery process therefore needs to be initiated by the discoverer and the traditional 4-way DHCP exchange cannot be applied as defined in the art. However, according to the present invention, the DHCP OFFER message, if modified, may be used by the discoverer as an unsolicited message or beacon. The DHCP OFFER message is modified in such a way as to be rejected by any other device that supports the traditional 4-way DHCP message handshake. The modified DHCP OFFER shall also carry information to allow the device to be detected or discovered to determine whether the DHCP OFFER message originates from a valid discoverer and is not part of the 4-way DHCP handshake. Finally, the modified DHCP OFFER message shall still be able to be relayed to other subnets by a standard implementation of the DHCP RELAY function supported by popular Routers, Switches, Gateways and other devices.
Each DHCP messages share a common format, as shown below. DHCP uses Uniform Data Protocol (UDP) as the transport layer protocol. Referring now to FIG. 2, the fields in a DHCP message are defined below:







TABLE 1







Fields in a DHCP Message.








DHCP Message Field
Description





Operation Code
Specifies the type of the Dynamic Host Configuration Protocol (DHCP) message.



Set to 1 in messages sent by a client device (requests) and 2 in messages sent by a



server or remote node (response).


Hardware Type
Specifies the network LAN architecture. For example, the Ethernet type is



specified when hardware type is set to 1.


Hardware Address
Link-layer address length (in bytes); defines the length of hardware address in the


Length
chaddr field. For Ethernet, this value is 6.


Hops
Number of relay agents that have forwarded this message.


Transaction identifier
Used by client devices to match responses from servers with previously


(XID)
transmitted requests.


seconds
Elapsed time (in seconds) since the client device began the Dynamic Host



Configuration Protocol (DHCP) process.


Flags
Flags field is called the broadcast bit, can be set to 1 to indicate that messages to



the client device must be broadcast


ciaddr
Client device's IP address; set by the client device when the client device has



confirmed that its IP address is valid.


yiaddr
Client's IP address; set by the server or remote node to inform the client device of



the client device's IP address.


siaddr
IP address of the next server for the client device to use in the configuration



process (for example, the server to contact for TFTP download of an operating



system kernel).


giaddr
Relay agent (gateway) IP address; filled in by the relay agent with the address of



the interface through which Dynamic Host Configuration Protocol (DHCP)



message was received.


chaddr
Client device's hardware address. (Layer 2 address)


sname
Name of the next server for the client device to use in the configuration process.


file
Name of the file for the client device to request from the next server (for example



the name of the file that contains the operating system for this client).









Looking at the above format for DHCP messages, the following fields are modified or interpreted differently when used by the discoverer to detect new devices: Transaction identifier: this field is normally set by a DHCP client device. When used as part of the modified DHCP OFFER, this 32-bit field includes a unique encryption key that is used to encrypt select portions of the modified DHCP OFFER message. This optional cryptographic information can be used to protect (encrypt) critical elements of the DHCP OFFER message including, but not limited to the siaddr and the giaddr fields. Flags: the broadcast bit shall be set to 1. All other bits are typically ignored and should be set to zero (0) for future compatibility.
Ciadd: the client IP address field should be set to 0.
Yiaddr: this field shall be set to 0. In a normal DHCP OFFER message, this field is used by a DHCP Server to inform a client of the IP address that has been reserved for it.
Siaddr: this is the IP address of the management device that will handle the management functions for the detected device.
Chaddr: this field shall be set to 0. In a normal DHCP OFFER message, this field is used to carry the hardware (for example Ethernet MAC) address of the client.
Sname: this field shall be set to 0.
File: this field shall be set to 0.
The modified DHCP OFFER 201 (in FIG. 2) is further modified via the following option list:
Server ID (option 54): this option shall include the discoverer IP address. This will be used by the detected device to return the ADVERTISEMENT message.
Vendor ID (option 43): this option shall be set to a unique string identifying the vendor and used by the detected device to filter out other DHCP OFFER it could inadvertently receive.
Vendor Information (option 60, also known as Vendor Class Identifier): this option field is used to carry additional information about the discoverer as well as information of interest to a detected device. Among others, this option field typically includes the following information: IP address configuration mode, Organizational Unique Identifier (OUI), rate of transmission, Time to Live (TTL), Supported Type-Length-Value, and other information. The IP address configuration mode is used to indicate to the detected device how it should obtain an IP address. Typical choices include (but are not limited to): using a static IP address, obtaining an IP address via the normal 4-way DHCP message handshake or the detected device automatically generating its own IP address based on an IP subnet provided by the detector/discoverer or specified in the default (or current) configuration settings for the detected/discovered device. The OUI is a unique value assigned to the Vendor by the Internet Assigned Numbers Authority (IRNA) and is used to filter out improper messages. The rate of transmission is the rate at which a detected device shall repeatedly transmit an Advertisement message to indicate it is still present in the network. TTL is the field that is decremented by a detected device. Supported TLV may contain a number of fields depending on the range of information to be exchanged between the discoverer and the detected device.
Referring now to FIG. 3, the modified DHCP OFFER message 301 also referred to as a beacon message or signal could be transmitted directly by the discoverer into the network using a broadcast. The DHCP OFFER message 301 could also be transmitted into the network indirectly via a list of DHCP relay functions available in the network. When the device to be discovered 302 receives one of these beacons, it first verifies to see if it is in fact a beacon transmitted by the discoverer. If the beacon is a beacon transmitted by the discoverer 307, then the device will use the information included in the modified DHCP OFFER 301 message to update its operation. It will then reply to the IP address of the Server as specified via option 54 in the beacon with an Advertisement 311 message to be transmitted repeatedly at the rate specified in the modified DHCP OFFER 301. By repeatedly transmitting Advertisement messages 311, it allows the management server specified in the beacon to detect an eventual disappearance of a detected device (or the fact that it is no longer reachable).
In order for the discovered device to begin to transmit the Advertisement message, the device should obtain a valid IP address as specified in the beacon message. Once the device has obtained a valid IP address, the transmission of the Advertisement message can begin. FIG. 3 shows an example of this. The discoverer 307 transmits modified DHCPOFFER 301 into the network. Device 302 receives modified DHCPOFFER 301 and verifies that it is a modified DHCPOFFER transmitted by discoverer 307. Device 302 then configures its IP address as per the information in the modified DHCP OFFER 301, and sends Advertisement 311 to the IP address specified in the beacon 301. According to one aspect of the present invention, the IP address may be the same node as the discoverer 307. The Advertisement message 311 is directly encapsulated in a UDP packet and sent as a unicast. The UDP port to use for the unicast Advertisement message may be extracted from the beacon message. In another embodiment, the UDP port is coded in the firmware of the device to be discovered or can be defined as part of a configuration profile.
The content of the Advertisement message 311 includes information about the detected or discovered device 302, including but not limited to: port identifier, device name, device description, IP address of the device (if known), serial number, firmware/software revision, base MAC address, configuration status, platform identifier, slot identifier, module information, and so on. The information may be encoded using the popular Type-Length-Value (TLV) format. In another embodiment, the information of the Advertisement packet may be encoded as a sequence of position dependent fields with pre-agreed lengths.
In another embodiment, the detected or discovered device may enable access to other undetected devices downstream from the device. When this is the case, the TTL value specified in option 60 of the beacon should be decremented by a value of 1 and if not zero (0), the newly detected device may elect to forward the beacon to other devices only reachable through the detected device.
As disclosed earlier, the modified DHCP OFFER message (beacon) is broadcast by the discoverer as an unsolicited message in order to reach as many undetected devices as possible. In another embodiment, the DHCP OFFER message (beacon) may be transmitted as a directed unicast packet to a specific previously detected device when the detected device cannot be reached using a valid destination IP address. This may occur when a device is in an unknown state and needs to be reset to a previously defined state (such as a factory default state) or when a detected device needs to receive additional information before it can obtain a valid IP address for further communication. A typical unicast packet includes the IP address of the remote device. In this embodiment, the detected device does not yet have a valid IP address and cannot therefore be reached using this method. In order to make sure the beacon is only valid for that specific device, as would a standard unicast UDP packet, the modified DHCP OFFER message should include other information that is unique to this device to be discovered. This information may include (but is not limited to): serial number, MAC address, device name or any other unique identifier where the unique identifier may be a combination of any of these individual identifiers.
The device to discover and the discoverer node are each coupled to a processor. The present invention includes systems having processors to provide various functionality to process information, and to determine results based on inputs. Generally, the processing may be achieved with a combination of hardware and software elements. The hardware aspects may include combinations of operatively coupled hardware components including microprocessors, logical circuitry, communication/networking ports, digital filters, memory, or logical circuitry. The processors may be adapted to perform operations specified by a computer-executable code, which may be stored on a computer readable medium.
The steps of the methods described herein may be achieved via an appropriate programmable processing device, such as an external conventional computer or an on-board field programmable gate array (FPGA) or digital signal processor (DSP), that executes software, or stored instructions. In general, physical processors and/or machines employed by embodiments of the present invention for any processing or evaluation may include one or more networked or non-networked general purpose computer systems, microprocessors, field programmable gate arrays (FPGA's), digital signal processors (DSP's), micro-controllers, and the like, programmed according to the teachings of the exemplary embodiments of the present invention, as is appreciated by those skilled in the computer and software arts. Appropriate software can be readily prepared by programmers of ordinary skill based on the teachings of the exemplary embodiments, as is appreciated by those skilled in the software arts. In addition, the devices and subsystems of the exemplary embodiments can be implemented by the preparation of application-specific integrated circuits or by interconnecting an appropriate network of conventional component circuits, as is appreciated by those skilled in the electrical arts. Thus, the exemplary embodiments are not limited to any specific combination of hardware circuitry and/or software.
Stored on any one or on a combination of computer readable media, the exemplary embodiments of the present invention may include software for controlling the devices and subsystems of the exemplary embodiments, for driving the devices and subsystems of the exemplary embodiments, for processing data and signals, for enabling the devices and subsystems of the exemplary embodiments to interact with a human user, and the like. Such software can include, but is not limited to, device drivers, firmware, operating systems, development tools, applications software, and the like. Such computer readable media further can include the computer program product of an embodiment of the present invention for performing all or a portion (if processing is distributed) of the processing performed in implementations. Computer code devices of the exemplary embodiments of the present invention can include any suitable interpretable or executable code mechanism, including but not limited to scripts, interpretable programs, dynamic link libraries (DLLs), Java classes and applets, complete executable programs, and the like. Moreover, parts of the processing of the exemplary embodiments of the present invention can be distributed for better performance, reliability, cost, and the like.
Common forms of computer-readable media may include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, any other suitable magnetic medium, a CD-ROM, CDRW, DVD, any other suitable optical medium, punch cards, paper tape, optical mark sheets, any other suitable physical medium with patterns of holes or other optically recognizable indicia, a RAM, a PROM, an EPROM, a FLASH-EPROM, any other suitable memory chip or cartridge, a carrier wave or any other suitable medium from which a computer can read.
While particular implementations and applications of the present disclosure have been illustrated and described, it is to be understood that the present disclosure is not limited to the precise construction and compositions disclosed herein and that various modifications, changes, and variations can be apparent from the foregoing descriptions without departing from the spirit and scope of the invention as defined in the appended claims.

## Claims

1. A method of discovering an undetected device to be discovered in a communication network having multiple interconnected nodes, comprising:
transmitting, by a discoverer to the device to be discovered, at least one unsolicited beacon signal including an IP address to the network and forwarding instructions, said transmitting based on Dynamic Host Configuration Protocol (DHCP);
receiving, by the device to be discovered, the at least one unsolicited beacon signal;
configuring the device to be discovered with forwarding instructions located in the at least one unsolicited beacon signal, to forward the beacon signal to one or more undetected devices downstream; and
transmitting, by the device to be discovered, an advertisement to a server specified by the discoverer,
wherein the device to be discovered will only take steps to be discovered if it is prompted to do so by the at least one unsolicited beacon signal.

2. A system for of discovering a device to be discovered in a communication network having multiple interconnected nodes, comprising:
a discoverer coupled to a first processor, wherein said discoverer transmits at least one unsolicited beacon message including an IP address to the device to be discovered over the communication network, wherein the at least one unsolicited beacon message is a dynamic host configuration protocol (DHCP) offer message modified so as to be rejected by any device that supports a traditional 4-way DHCP message handshake; and
a device to be discovered coupled to a second processor, wherein the device to be discovered is an undetected device on the network, and
said device to be discovered receives the at least one unsolicited beacon message transmitted by the discoverer;

wherein the device to be discovered is configured by the at least one beacon message to forward the beacon to one or more undetected devices downstream;
wherein the device to be discovered transmits an advertisement to a server specified by the discoverer in the at least one unsolicited beacon message; and
wherein the device to be discovered will only take steps to be discovered if it is prompted to do so by the unsolicited beacon message.

3. A method of discovering an undetected device to be discovered in a communication network having multiple interconnected nodes, comprising:
transmitting to the communication network, by a discoverer, at least one unsolicited beacon signal including an IP address to the communication network, wherein the at least one unsolicited beacon signal is a modified dynamic host configuration protocol (DHCP) offer message;
receiving, by the device to be discovered, the at least one unsolicited beacon signal;
configuring the device to be discovered with forwarding instructions located in the at least one unsolicited beacon signal, to forward the at least one unsolicited beacon signal to one or more undetected devices downstream; and
transmitting, by the device to be discovered, an advertisement to a server specified by the discoverer to indicate that the device to be discovered is present in the communication network,
wherein the device to be discovered will only take steps to be discovered if it is prompted to do so by the at least one unsolicited beacon signal.