Abstract:
A management station responds to an HTTP request for device discovery by spawning a device discovery task that creates a linked list and first broadcasts UDP based requests out on a subnetwork for devices on the same subnetwork to respond. Device information from responding network devices is stored in a linked list. This process is repeated until a specified length of time has expired. Then a second broadcast request is sent out that includes a list of printers that have responded so that they will nor keep responding. The list is updated by responses until there are no more responses. Any nodes in the linked list that still only have a network address are updated by sending a unicast SNMP request those network addresses in order to get the additional information. The data from the linked list is sent back to the HTTP client.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
       [0001]    This applications is a divisional of co-pending U.S. application Ser. No. 09/199,935, filed Nov. 25, 1998, the contents of which are incorporated herein by reference. 
     
    
     
       BACKGROUND OF THE INVENTION  
         [0002]    The present invention relates to locating devices on a network, and more particularly to allowing a network device to locate other network devices on the same sub-network.  
           [0003]    Some users of devices residing on a network find it desirable to locate all or a class of other devices on the network. For example, a user may wish to have a list of all the printers of a certain brand, along with information about those printers that are on the same sub-network. Typically, a network device would perform such a search using a network communications method (protocol) such as Simple Network Management Protocol (SNMP).  
           [0004]    A network device typically searches for other devices on the network by sending (User Datagram Protocol) UDP messages to the sub-network and then waiting for particular responses from network devices that are listening on the same sub-network. The network device that sends out the request is typically called a management station and a device responding to such a request is typically referred to as a network agent.  
           [0005]    UDP is a protocol that offers a limited amount of service when messages are exchanged between network devices in a network that uses the Internet Protocol (IP). A persistent problem is the loss of information packets due to congestion in the network or the receiving device, whether a management station or agent. Congestion essentially is the existence of interfering messages. One way this problem can occur, for example, is when responses from network agents arrive as a result of the UDP broadcast message from the management station and they are initially received by the on-board Ethernet driver. This driver executes at a high priority intercepting every packet that arrives. If the packet has the expected frame type then the packet is ready to be delivered to the IP layer of the network stack. The IP task, which is running at a lower priority than the Ethernet driver, needs to accept as many packets as possible from the Ethernet driver. The total buffer area for the IP task is finite and the buffer for the Ethernet driver is also finite. Available buffer space depends on how fast the application task that is executing UDP routines can read and consume the data. Since both the  1 P task and the UDP level task run at a lower priority than the Ethernet Driver and total buffer space of the Ethernet driver is limited, the management station will not be able to read all the UDP based response packets that arrive at the on-board Ethernet driver. This approach of using UDP alone prevents an exhaustive and reliable search of the network since some request or response packets can be lost.  
           [0006]    Service Location Protocol (SLP), described in the Internet Request For Comments document 2165 (RFC 2165), is one protocol that may be used instead of, or to supplement UDP based SNMP broadcast and responses. SLP provides a means to send in the broadcast request a list of devices that have already responded such that those who have already responded will not do so again. However, using SLP would result in slower and more cumbersome location of devices on the network because of its complexity and lack of specialization.  
           [0007]    A second problem also exists when attempting to locate or find devices with no IP address. Prior approaches using IP multicasting require registration with the router and therefore do not provide a complete solution.  
           [0008]    What is desired is a system for network device location that provides a faster and more exhaustive search which supplements the basic UDP broadcast and responses in order to reliably receive response packets from network agents or devices, and to uniquely identify those devices without relying on their IP address.  
         SUMMARY OF THE INVENTION  
         [0009]    Accordingly, the present invention provides a faster, more exhaustive search and supplements the basic UDP broadcast and responses in order to receive and read more response packets from network agents. The present invention provides an approach to achieve device location discovery based on a MAC (media access channel) address even though the IP address is not known.  
           [0010]    The invention employs a unicast (HTTP) request that is sent on a network to a device, such as a printer, with a known location and that device discovers other devices with unknown network locations. The device with the known location returns a web page to the user showing its status, with links to the other discovered devices. The user can then select the link to one of the newly discovered devices and view the web page of the selected device.  
           [0011]    A device implementing this invention responds to an HTTP request for device discovery by spawning a device discovery task that broadcasts a SNMP over UDP based request out on a subnetwork for devices to respond. When responses are received they are parsed and the device information such as network address, name, status, version and model is added to a list of discovered devices. Any responses from devices outside a specified class of devices, such as those not of a certain brand, are disregarded. The task waits for the responses until a specified amount of time has expired.  
           [0012]    Then a device location protocol (DLP) over UDP broadcast request is sent out that includes a list of devices, such as printers, that have responded. The request is that only devices not on the list respond. Responses are then parsed and the responding device&#39;s network address is added to the list of responding devices. This process is repeated until there are no more responses.  
           [0013]    The management station may use unicast SNMP requests to the devices in the list to learn additional information about those devices which have an assigned IP address. The data from the linked list is then copied into a (Hypertext Markup Language) HTML buffer to be sent to the HTTP client that sent the original request.  
           [0014]    These aspects, advantages, and other novel features of the present invention are apparent from the following detailed description when read in conjunction with the appended claims and attached drawings. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0015]    [0015]FIG. 1 is a block diagram representing various servers and clients on a network that are involved in network device location according to the present invention.  
         [0016]    [0016]FIG. 2 is a flow chart of the process of network device location according to the present invention.  
         [0017]    [0017]FIG. 3 is a diagram of a device location protocol (DLP) request packet according to the present invention.  
         [0018]    [0018]FIG. 4 is a diagram of a device location protocol (DLP) response packet according to the present invention.  
         [0019]    [0019]FIG. 5A is a diagrammatic illustration of a device location protocol (DLP) wherein a device (printer) with a known location broadcasts a request and discovers the locations of other unknown devices while permitting the user to select and view the web page of a discovered device.  
         [0020]    [0020]FIG. 5B is a diagrammatic illustration of another device location protocol (DLP) wherein a device (personal computer) broadcasts a request and discovers the locations of unknown devices and assigns an IP address to those discovered devices.  
         [0021]    [0021]FIG. 6 is a sample of the web page viewed by the user in FIG. 5.  
         [0022]    [0022]FIG. 7 is a list of locations of other devices linked to the known device in FIG. 5. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0023]    Referring to FIG. 1, various network devices  35  such as printers reside on a network  45 . A user on the network with a Hypertext Transfer Protocol (HTTP) client  15 , or web browser, wishes to find either all devices that reside on the network  45 , or those of a specified class, such as a certain brand of printers, and obtain information about those devices. The HTTP client  15  sends an HTTP request to a management station  5 , which has an HTTP server running in order to find desired network devices. This request is called a device discovery request.  
         [0024]    Referring to FIG. 2, the HTTP server waits for HTTP requests  50 . After receiving the device discovery request  55 , the HTTP server spawns a device discovery task  10  as shown in FIG. 1. The HTTP server is preferably designed to spawn up to five device discovery tasks, each of which can run concurrently. The priority level of the device discovery task  10  is the same as the priority level of the HTTP server task in the management station  5 . This priority level will enable the device discovery task to read as much data as possible from the Internet Protocol (IP) task in the management station  5 , and at the same time it will not starve the HTTP server from the processor (CPU) time slice.  
         [0025]    Referring to FIG. 2, after the device discovery task initializes  60  (allocates memory, initialize semaphores, etc.), it creates a data structure to store device information  65 . In the preferred embodiment, this is a linked list, but may be any other data structure that provides similar features. A node is added to the list  65  for a local device  40 , such as that as shown in FIG. 1, and the device name, model and status are copied into the node  65 .  
         [0026]    The device discovery task  10  is a subset of a typical SNMP Manager, sending SNMP request UDP broadcast packets  70  to all the SNMP Agents  35  who are listening in the same sub-network. These broadcast packets contain a broadcast destination IP address, have a destination port as  161 , and are received by any application listening on port  161  on any active node. While the SNMP agents  35  respond to this request broadcast  70 , the device discovery task waits  75  for a configured amount of time (TIMEOUT) for all the responses to arrive. The device discovery task  10  uses parsing functions provided by the NEST SNMP library to generate SNMP requests and also to parse the responses from the SNMP Agents  35 . The SNMP response packets are parsed with the NEST SNMP library routines in order to extract the object identification and value pair. These values that are extracted from the NEST internal data structure contain information about the device name, model, and status, hereafter called SNMP information.  
         [0027]    In the preferred embodiment, the responder&#39;s IP address and SNMP information is extracted from these response packets and saved into a linked list  90  only if the packets are from devices in a desired class of devices  85 ,  80 , such as printers of a certain brand, but this step may be skipped without going beyond the scope of this invention. When this step is skipped, any devices residing on the same sub-network that are SNMP Agents  35  could be located. If the response packets are not from devices of the desired class, the packet is simply discarded by the device discovery task  80 .  
         [0028]    After the expiration of TIMEOUT seconds  95 , the device discovery task  10  sends a UDP based broadcast request  100  according to the protocol in FIG. 3, hereafter called (device location protocol) DLP. The DLP broadcast request operates on port  1200  and contains a request for any devices listening  35  that are not already a member of the linked list, to respond. Referring to FIG. 3, the request packet contains the IP addresses of devices that have already responded, such that the devices with a DLP server running will know not to respond if their IP address appears in the list. The length of each IP address is included before each IP address in the request. This is an important improvement over SLP because indicating the length of the IP address before each address, as opposed to merely separating the addresses by a semicolon (see RFC 2165), DLP servers  35  do not have to parse every byte of the request, which results in faster searches. This is because the DLP server within the network devices  35  will know the length of each address beforehand.  
         [0029]    Only DLP servers  35  listening on port  1200  respond to this request. Referring to FIG. 3, the DLP server will reject the request message if any of the following conditions are true:  
         [0030]    1) Length of the request buffer is less than 9 bytes. As shown in FIG. 3, the first 8 bytes of the request buffer are for version number (4 bytes) and length of the whole packet (4 bytes). The next 1 byte is allocated for section of the request packet and for indicating the model name. This is a total of at least 9 bytes for the request message.  
         [0031]    2) If value in the length section of the request buffer is not equal to the total number of bytes returned in the UDP packet.  
         [0032]    3) If the value of the IP address length is more than the calculated value of the bytes following the position of the IP address length field.  
         [0033]    4) If any of the values of IP address length field is zero or less than zero.  
         [0034]    Whenever the device discovery task  10  receives a DLP response  105 ,  102 , responder&#39;s IP address is added to the list  110 , only if that IP address is not already found in the list. The DLP response protocol appears in FIG. 4. Note that the response includes the current responder&#39;s machine address (MAC address) as well as the IP address. This is also an important improvement over SLP because new devices may not have an IP address, but will be able to be detected anyway.  
         [0035]    Referring to FIG. 4, the device discovery task  10  will reject the response if any of the following conditions are true:  
         [0036]    1) length of the response buffer is less than 10 bytes (4 bytes for version number, 4 bytes for the length of buffer, 1 byte for device model name, and 1 byte for device IP Address).  
         [0037]    2) If the value of IP Address length field is zero or less.  
         [0038]    3) If the length of the buffer is not equal to the total byte return by the recvfrom socket call.  
         [0039]    4) If the value of the IP Address length is more than the calculated value of the bytes following the position of the IP Address length field.  
         [0040]    5) If the MAC address is less than or equal to zero.  
         [0041]    6) If the value of the MAC Address length is more than the calculated value of the bytes following the position of the MAC Address length field.  
         [0042]    If at least one response has arrived after the last and most recent DLP request broadcast, another DLP request is generated  102 ,  100 . Otherwise, if no request has arrived after the last and most recent DLP request broadcast the device discovery task  10  closes the DLP port and generates a SNMP request unicast to each of those IP address in the linked list that were added to the list as result of DLP responses  115 . These SNMP request messages to each of the IP addresses are unicast messages generated to a maximum set of  10  destinations at a time. After up to a maximum of  10  unicast requests are generated, the device discovery task  10  waits again  120  up to TIMEOUT seconds for the SNMP response packets to arrive. When they arrive, the SNMP information such as device name, model, version number, and device status are copied into the list  125 .  
         [0043]    This continuous sequence of generating up to  10  SNMP request unicast messages and waiting up to TIMEOUT for the SNMP response packets to arrive and then copying the SNMP information to the list comes to an end when all the remaining IP addresses from the linked list are exhausted  130 . The device discovery task  10  then generates the Hypertext Markup Language (HTML) based buffer  135  from the information collected in the linked list. The HTTP server running on the management station  5  is partially single threaded and this single threaded portion is located in the area where the server prepares the HTML buffer to be sent to the HTTP client  15 . The device discovery task  10  and other servers may share a semaphore with the HTTP server task, and as a result only one task at a time can prepare and send the HTML buffer back to the HTTP client. Therefore, the device discovery task  10  locks a semaphore  140 , and then sends the HTML packet with the generated table of located device information to the HTTP client  15 . The device discovery task then unlocks the semaphore  150 , frees the list  150  and exits  155 .  
         [0044]    The approach shown in FIG. 5A has a web client PC  11  send out an HTTP request on a network to a printer  12  with a known location and that device acts as a management station to discover other printers  13  and  14  with unknown network locations. The printer  12  with the known location returns a web page in the form of a formatted HTML page to the user showing its status, with links to the other discovered printers  13  and  14 . The user can then select the link to one of the newly discovered printers and view the web page of the selected printer. A newly discovered printer  13  can repeat the process to discover other devices  12  and  14 , or newly added devices to the network (not shown). FIG. 6 shows a representative web page for a printer, while FIG. 7 shows a partial listing of printers in a network with the printer name, model number, IP name and status.  
         [0045]    In an alternative approach seen in FIG. 5B, PC  11  sends out a broadcast request to all devices on the network. DLP capable devices  12 ,  13 , and  14  individually send DLP replies to PC  11  which contain information (model and serial number) needed to identify the devices even though the devices do not have an IP address. PC  11  selects an IP address using an algorithm, such as Microsoft&#39;s Automatic Private IP Network Addressing employed in Windows 98. The PC  11  uses Dynamic Host Configuration Protocol (DHCP) to assign the IP address to the network device. PC  11  can repeat the process until all devices are identified and assigned an IP address.  
         [0046]    Thus, the present invention provides a more exhaustive search and supplements the the UDP based SNMP broadcast and responses in order to receive and read more response packets from network agents.  
         [0047]    Accordingly, the spirit and broad scope of the appended claims is intended to embrace all such changes, modifications and variations that may occur to one of skill in the art upon a reading of the disclosure. All patent applications, patents and other publications cited herein are incorporated by reference in their entirety.