Zero configuration networking on a subnetted network

Methods and apparatus are described for implementing service discovery protocols on subnetted zero configuration networks. A process for managing service advertisement across a plurality of subnets may comprise: collecting service advertisements on a local network level by designated network devices; sending listings of services from each of the designated devices to a master network device; sending a table of services for the plurality of subnets from the master device to all of the designated devices on the plurality of subnets; creating by each of the designated network devices for the corresponding subnet a service discovery proxy table listing the service advertisements on the subnets of the plurality of subnets beyond the subnet corresponding to the designated device; and periodically transmitting by each of the designated devices on the corresponding subnets service advertisements for the services of the corresponding service discovery proxy table.

BACKGROUND

Field of the Invention

The present invention relates generally to zero configuration networking and more specifically to methods and apparatus for implementing service discovery protocols on subnetted zero configuration networks.

Description of the Related Art

A zero configuration network is an IP network that is configured without the need for any manual configuration or special configuration servers. For example, someone without networking expertise can readily connect computers, printers and other devices, which are then automatically networked. This automatic networking function may: allocate IP addresses for the devices, if required, translate between domain names and IP addresses, and locate network services. A comprehensive description of zero configuration networking is provided inZero Configuration Networking: The Definitive Guide, Stuart Cheshire and Daniel H. Steinberg, O'Reilly Media, Inc., Sebastopol, C A 2006.

Service discovery protocols are used on zero configuration networks to automatically detect services available on connected network devices and to advertise the detected services. Examples of service discovery protocols used on zero configuration networks include Bonjour available from Apple, Inc. and Avahi, for example. Universal Plug and Play (UPnP) may also be used for service discovery on zero configuration networks.

These service discovery protocols provide automatic service discovery within a transmission domain. Thus, when the population of devices on a network becomes high and networks are segmented into multiple domains, users will have more limited service discovery. This may not be an issue where network switches or switching hubs connect multiple network segments to form a single L2 network allowing transmission of L3 link local multicasts across the entire network. However, as explained in more detail below, a network with a subnetted configuration does not permit L3 link local multicasts from one subnet to another without configuring DNS—a non-trivial challenge for the network administrator.

FIGS. 1-3provide an illustration of some of the current challenges of service discovery across multiple subnets.FIG. 1shows a multi-subnet configuration comprising two VLANs connected by an L3 switch or routing switch. Each VLAN is shown with an access point—AP1and AP2. In this example of a school environment, VLAN1is dedicated to students, the students accessing the network at AP1, and VLAN2is dedicated to faculty, the faculty accessing the network at AP2. There is a printer on VLAN2, for which a mDNS advertisement of a printing service appears on the local network, VLAN2. The L3 switch blocks mDNS advertisements; consequently, the advertisement will not reach the student network, VLAN1. However, in some circumstances it may be desirable for the students on VLAN1to be able to see the advertisement for the printing service on VLAN2. This can be achieved if the L3 switch allows for forwarding or duplication of mDNS advertisements, the printing service will be advertised on both VLAN1and VLAN2, as shown inFIG. 2, and the students can now see the advertisement of the printing service. However, the faculty would be able to see services advertised by student computers, such as_game._tcp perhaps, which may not be desirable. SeeFIG. 3. In fact, the students and faculty will be able to see all services available on both VLAN1and VLAN2. Clearly, there is a need for an efficient process of selectively limiting the network-wide visibility of certain services, and also to limit the total number of services advertised in order for the transmission of advertisements to be manageable and useful to network users.

Furthermore, all the services on all subnets in a multi-subnet network may be an extremely large set of services and may be unmanageable to transmit to all network users. There is a need for processes to manage the volume of services being advertised within any one subnet.

SUMMARY OF THE INVENTION

The present invention includes methods and apparatus for implementing service discovery protocols on subnetted zero configuration networks. In general, embodiments of the invention are based on the concept of using designated network devices, such as APs, at the local, subnet level to collect and filter service advertisements (services advertised using a mDNS service advertisement protocol, for example), send the filtered service advertisements to a higher level designated network device for creation of a list of services available across a multiplicity of subnets, and then send the list to the local level designated network devices to allow for proxy service advertisements (proxy advertisements are permitted in mDNS service advertisement protocol) from across the multiplicity of subnets to be transmitted on all subnets.

According to aspects of the present invention a process for managing service advertisement across a plurality of subnets may comprise: collecting service advertisements on a local network level by designated network devices; sending listings of services from each of the designated devices to a master network device; sending a table of services for the plurality of subnets from the master device to all of the designated devices on the plurality of subnets; creating by each of the designated network devices for the corresponding subnet a service discovery proxy table listing the service advertisements on the subnets of the plurality of subnets beyond the subnet corresponding to the designated device; and periodically transmitting by each of the designated devices on the corresponding subnets service advertisements for the services of the corresponding service discovery proxy table. Furthermore, the process may comprise sending listings of services from each of the designated network devices to a designated back-up master network device and providing the filtered listings to the designated back-up master network device for creating said table of services. Furthermore, the process may comprise filtering the advertisements by the designated devices to provide filtered listings of services, the filtered listings being provided to the designated master network device for creating the table of services, wherein the filtering may use filtering rules based on regular expressions. Furthermore, the service advertisements and the proxy service advertisements may use multicast DNS (mDNS) protocol.

According to further aspects of the present invention, a system for managing service advertisement across a plurality of subnets may comprise: (1) a designated master network device including (a) a first memory device, a first computer program being stored in the first memory device, and (b) a first processor; and (2) a multiplicity of designated network devices, each of the multiplicity of designated network devices including (a) a second memory device, a second computer program being stored in the second memory device, and (b) a second processor, the second computer program causing the second processor to perform: (i) collecting service advertisements on a local network level; (ii) sending a listing of services to the designated master network device; (iii) receiving a table of service advertisements from the master network device, wherein the table is a combination of the listings for the plurality of subnets; (iv) creating a service discovery proxy table listing the service advertisements on the subnets of the plurality of subnets beyond the subnet corresponding to the designated network device; and (v) periodically transmitting service advertisements for the services of the service discovery proxy table on the subnet corresponding to the designated network device. Furthermore, the first computer program may cause the first processor to perform: on receiving listings of services from the multiplicity of designated network devices, combining the listings for the plurality of subnets to form the table of service advertisements; and sending the table to the multiplicity of designated network devices on the plurality of subnets. Furthermore, the plurality of subnets may be a plurality of LANs or VLANs, and preferably each VLAN is a single IP subnet. Furthermore, the designated network devices may be access points (APs), wireless APs, routers, switches or special software running on severs or virtual machines.

DETAILED DESCRIPTION

In general, embodiments of the invention are based on the concept of using designated network devices, such as APs, at the local, subnet level to collect and filter service advertisements (services advertised using a mDNS service advertisement protocol, for example), send the filtered service advertisements to a higher level designated network device for creation of a list of services available across a multiplicity of subnets, and then send the list to the local level designated network devices to allow for proxy service advertisements (proxy advertisements are permitted in mDNS service advertisement protocol) from across the multiplicity of subnets to be transmitted on all subnets. Detailed examples are provided of the present invention for service advertisement protocols using mDNS, such as Bonjour. However, the concepts and teaching of the present invention, as stated above, are not limited to implementation with Bonjour. For example, embodiments of the invention may be implemented with service advertisement protocols such as UPnP. Furthermore, the concepts and teaching of the present invention may be implemented with NetBIOS Name Service.

A process for managing service advertisement across a plurality of subnets according to some embodiments of the present invention may include the following steps: collecting service advertisements on the local network level by designated network devices and creating link-level tables of the available services for each subnet with a designated network device (note that not all subnets will necessarily have a designated network device, since a designated device is only needed on subnets with services for which service advertisements are desired to be transmitted across the plurality of subnets); filtering the local service advertisements in the tables by the designated network devices to provide filtered listings of services; sending the filtered listings from each designated network device to a designated master network device (and preferably to a designated back-up master network device) and combining the filtered listings at the designated master network device to form a table of filtered service advertisements; and sending the table of filtered service advertisements to all designated network devices, such that each designated network device maintains a service discovery proxy table listing the filtered services on the plurality of subnets. This process is explained in more detail with reference toFIGS. 4-8.

InFIG. 4, a designated network device (DD1) is shown collecting service advertisements on the local network level for both VLAN10and VLAN20. These local level service advertisements are provided by a service advertisement protocol such as Bonjour using mDNS. DD1creates link-level service tables (LLST)—LLST-10and LLST-20, for the subnets VLAN10and VLAN20, respectively. LLST-10and LLST-20are stored in memory on DD1. In this example, LLST-10lists services1-3which are advertised on VLAN10and LLST-20lists services4-6which are advertised on VLAN20.FIG. 4represents part of a larger network which includes a plurality of subnets—VLAN10, VLAN20. . . VLAN50, as illustrated inFIG. 5.

The five subnets inFIG. 5are referred to herein as a service discovery realm. The term realm is used so as to be clear that the grouping of subnets need not in all cases correspond to a complete network—in other words there may be more than one realm within a network. The number of subnets within a realm may be within the range of 2 to tens of thousands or more. On a practical level a limitation to the number of subnets may be determined by the memory and processing requirements in the designated devices required for the service advertisements not in a designated device's subnet. The subnets may be local area networks (LANs) or virtual LANs (VLANs), and preferably each VLAN is a single IP subnet. A realm may correspond to a geographical region, such as one building on a company campus, or to an organizational division, such as an engineering group, where sharing advertised services is beneficial. A realm corresponding to a geographical region is beneficial when services such as printing are being advertised—a user is unlikely to be interested in a printing service across the other side of a large company campus and will only want to see those in close geographical proximity, and thus a realm of limited geographical extent is beneficial. A realm corresponding to a particular organizational division may be beneficial if the division is spread out geographically but wishes to share software tools, datafiles, presentations, etc.

To provide a specific example of a realm, consider Kindergarten through 12thgrade school districts. The realm is likely to be either a single school building, or the entire district. Where districts are reasonably small—for a small city—the district may be a realm. Where the district is county-wide, and may have almost 10,000 APs, there may be multiple realms—these realms may be either a particular slice of the district (elementary/middle/high schools in three realms) or individual schools.

These service discovery realms may be user defined or may be determined automatically. An example of the latter is a large set of cooperative control APs which cover a continuous area which automatically organize into coverage sub-areas, where each sub-area is a realm. A further example is a network for a company with three locations worldwide and the APs self-organize into realms that form continuous coverage areas, in this case three realms—one for each location. When wireless APs are used, the wireless coverage areas of adjacent APs within a realm will often be spatially overlapping.

A designated network device, DD, is needed for each subnet in a realm. The number of designated devices may correspond to the number of subnets in a realm, or, as shown inFIG. 4, multiple subnets may share a common designated device. There may also be a second DD for each subnet which acts as a back-up. Lower level designated devices may be network devices such as access points (APs), a specific example being the cooperative control AP—the HiveAP device—available from Aerohive Networks, Inc. Furthermore, designated devices may be routers, switches and even special software running on servers or virtual machines. The realm level designated devices may also by APs, or may be controllers in networks that have centralized control. Furthermore, the realm level designated devices may be any of the network devices described above for lower level designated devices. A network device, such as an AP, may double as both a lower level and a realm level designated device. Where there are many suitable network devices on a subnet an election process may be used to designate one device and a back-up. For example, the first AP coming up on a VLAN is the DD, and the second the back-up, or the device with the lowest MAC address is the DD and the next lowest is the back-up. Similarly, for each realm a master realm device and a back-up device are designated. In one embodiment, the set of lower level designated devices elect one of the set to be realm master and a second to be back-up realm master. Two realm level devices are preferred to provide for seamless backup when the master dies. Having two realm level devices also reduces the O(N∧2) problem of synchronizing between subnets to O(N). (If you have N devices, you need to have N*(N−1) connections between all of them in a full mesh, but if you have designated devices acting as master and backup master, you only need 2N connections—the load on the network is reduced.)

To share information between designated devices, a communication protocol built on top of the Internet Protocol (IP) can be used. The communication carries a list of services to be shared along with the network address for each service. By building the communication protocol between designated devices on IP, it can span any physical distance covered by an IP network and traverse a network built out of nearly any networking component available for sale today.

InFIG. 6, the designated device DD1is shown filtering the local service advertisements on LLST-10and LLST-20to provide corresponding lists of filtered services for each subnet—partial realm service tables PRST-10and PRST-20. The filtering is executed by a processor on DD1and the partial realm service tables are stored in memory on DD1. (The tables are preferably also stored in memory on a back-up designated device. The tables may also be stored on disk.) Filter rules may be consistent throughout a realm or may be custom for each subnet within a realm. An example of a filter rule for (1) a realm corresponding to a single building on a campus is to allow all printing services to be advertised providing the building is not too large, and (2) a realm including geographically disparate locations is to exclude all printing services, thus only printing services on a local level will be advertised. Filters may be used to restrict access to certain services by not advertising them beyond their local network. In the example inFIG. 6, the filter removes services1and3from LLST-10and services4and6from LLST-20, thus service2is included in PRST-10and service4is included in PRST-20. The designated device DD1then sends the partial realm service tables to a master realm designated device (MRDD).

Filtering rules may be based on regular expressions. For example: match “_ipp._tcp” exactly will match exactly one service—the IPP (Internet Printing Protocol); match “_i*_.tcp” will match any TCP service that begins with the letter I, and thus will match IPP as above, but it will also match “_ipodconfiguration._tcp”; or match “*._tcp” will match any TCP service.

InFIG. 7, the designated devices DD1, DD2, . . . DD5are all shown sending partial realm service tables to the master realm DD and the back-up realm DD, where they are stored in memory. The realm level DDs separately combine the PRSTs to create a realm service discovery table (RSDT) which is stored in memory. (The tables—PRSTs and RSDT—are preferably also stored in memory on a back-up master designated device. The tables may also be stored on disk.) The master realm DD then sends the RSDT to each DD for each subnet—the RSTD is stored in memory on each designated device. (The tables are preferably also stored in memory on a back-up designated device. The tables may also be stored on disk.) Note that inFIG. 7separate designated devices DD1and DD2are shown for VLAN10and VLAN20, although in alternative configurations VLAN10and VLAN20may have a common designated device, as shown inFIG. 4. Furthermore, a single designated devices may be used if it can be plugged into a trunk port that is connected to all VLANs, in which case it receives all service advertisements, and can maintain the entire network state table without having to synchronize between devices.

The back-up master designated device may be triggered into action on receipt of a message that the designated master network device is not communicating with the designated network devices or by being unable to communicate with the master device over several seconds, in which case the designated back-up master network device sends the realm service discovery table to the designated network devices on the plurality of subnets in the realm.

InFIG. 8, the master realm DD is shown sending the RSDT to DD1—the same designated device that collected and filtered the local level advertisements on the subnet. DD1then creates a service discovery proxy table which includes the services available realm-wide, excluding those available on the local subnet. The service discovery proxy table is stored in memory on DD3. For example, DD3creates a proxy table including the services available on VLAN10, VLAN20, VLAN40and VLAN50, excluding the services available locally on VLAN30. As shown inFIG. 9, DD3then transmits the service discovery proxy table to its local subnet—VLAN30. This transmitting may be efficiently executed by periodically transmitting mDNS messages on VLAN30to advertise all services in the proxy table. InFIG. 9, DD3is shown advertising on VLAN30services2,5,11and14which are available on VLAN10, VLAN20, VLAN40and VLAN50, respectively. Note that the RSDT received by the DD which covers the DD's subnet is used for comparison to assist in determining when a new service needs to be reported to the master realm DD for adding to the RSDT or when an old service is no longer being advertised and needs to be reported to the master realm DD for removal from the RSDT. Typically it is desired that RSDTs are republished with all updates approximately every 5 seconds. For example, when a new service is added to a subnet, the service advertisement would be identified as new by comparison with the subnet's RSDT, if it passes the filter information is then sent to the realm master designated device identifying the addition of a new service. From the realm master designated device the service advertisement is sent out to all designated devices on all subnets in the realm and proxy advertised on these subnets. It is desirable to have this updating process completed within approximately 5 seconds. Note that on the subnet of the new service, the service creator continues sending a service advertisement every couple of seconds for this new service; however, it is not this repeating service advertisement that is propagated to the realm level, merely the information that the service needs to be added or removed from the RSDT. Consequently, the process of the present invention produces a lesser load on routers compared to networks in which the routers allow forwarding or duplicating of mDNS advertisements, as described above with reference toFIG. 2.

FIG. 10is used to illustrate the application of the present invention to the network topology ofFIGS. 1-3. AP1and AP2may be designated network devices for VLAN1and VLAN2, respectively. AP2may double as a designated master network device, and AP1may double as a designated back-up master network device. The process of the present invention may be applied to this network as described above, to provide service advertisement across both VLAN1and VLAN2without requiring an L3 switch specially adapted for forwarding or duplication of mDNS advertisements. Furthermore, filtering of service advertisements may be readily carried out according to the present invention. For example, the service advertisement from the printer on VLAN2is blocked by the L3 switch, but is collected by AP2and incorporated into a table of services. The table is sent to AP1so that the printer service may be proxy advertised on VLAN1by AP1. Furthermore, the student application _game._tcp which is advertised on VLAN1is collected by AP1, and may be filtered so that it is not added to a table of services on VLAN1(and thus is not sent to AP2for proxy advertisement on VLAN2). As indicated by the double-headed arrow, the communication between AP1and AP2controls service advertisement for services beyond the local subnet.

Further refinements to the process described above may include setting advertisement criteria based on proximity to an AP. For example, a service is only proxy advertised if it is within one AP hop in the air for a wireless network or if the service is on a neighboring AP in the air of an AP on a VLAN. This may be implemented on a network with APs which receive or acquire information regarding which APs are neighboring APs.

Yet further refinements to the process described above may include using IP filtering to enable services separately to advertisement of services. To enable IP filtering involves controlling routing and switching. For example, returning to the teacher/student example ofFIGS. 1-3, when you configure “allow printing advertisements from teacher VLAN to student VLAN,” you would also open up ports in the firewall to allow the printing traffic.

The process for managing service advertisement across a plurality of subnets, as described above may be implemented by software loaded into memory of the various designated devices—the designated devices on each subnet, the master realm designated device and the back-up devices. The software is executed by processors on said designated devices to perform the described process. Although the present invention has been described with the designated devices on both the local and realm level carrying out the processing and storing of data, some of the processing and storing may be in the cloud. For example, the master realm DD and back-up realm DD may be virtual devices in the cloud.