Abstract:
A system and method for providing network data and system upgrades to individual nodes within an ad-hoc network without requiring network-wide information broadcasts. The system and method identifies adjacent devices authorized to share system and upgrade information. Nodes are directed to prepare and transmit requests for upgrade information from adjacent devices, such that upgrade information may be passed, from one node to the next, reaching each node in the network. The node-to-node upgrade propagation thereby replaces traditional network-wide broadcasts of upgrade information.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to a system and method for providing network data and system upgrades to individual devices within an ad-hoc network without requiring network-wide information broadcasts. More particularly, the present invention relates to a system and method for creating and broadcasting requests for data and upgrades between adjacent devices, wherein an individual device can update system parameters from information provided by adjacent devices, where such transfers are authorized.  
           [0003]    2. Description of the Related Art  
           [0004]    In recent years, a type of mobile communications network known as an “ad-hoc” network has been developed. In this type of network, each user terminal (hereinafter “mobile node”) is capable of operating as a base station or router for other mobile nodes, thus eliminating the need for a fixed infrastructure of base stations. Accordingly, data packets being sent from a source mobile node to a destination mobile node are typically routed through a number of intermediate mobile nodes before reaching the destination node.  
           [0005]    More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other, as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network and communicate with other types of user terminals, such as those on the public switched telephone network (PSTN) and on other networks, such as the Internet. Details of these types of ad-hoc networks are described in U.S. patent application Ser. No. 09/897,790 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, filed on Jun. 29, 2001, in U.S. patent application Ser. No. 09/815,157 entitled “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, filed on Mar. 22, 2001, and in U.S. patent application Ser. No. 09/815,164 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, filed on Mar. 22, 2001, the entire content of each being incorporated herein by reference.  
           [0006]    Generally, all nodes in a wireless ad-hoc peer-to-peer network provide similar services and functionality. Although each node can provide similar services, the workload is typically distributed across many nodes rather than centralized at a single location in the peer-to-peer network. Therefore peer-to-peer networks distinguish themselves from infrastructure networks where one or more nodes offer a superset of the functionality of the rest of the network. Infrastructure nodes in these networks typically can handle Dynamic Host Configuration Protocol (DHCP), Address Resolution Protocol (ARP), as well as other services that depend on broadcast traffic. Dynamic Host Configuration Protocol is defined by IETF RFC 2131 and 2132, and is used by a client node to automatically obtain network settings from a central server. These network settings include the client&#39;s IP address, the address of Domain Name Servers (DNS), the IP address of default gateways, and many other network settings. Address resolution protocol is defined by STD 0037 and RFC 0826, and is used by a network node to map IP addresses to MAC addresses so IP traffic can be delivered to specific hardware. These infrastructure nodes are normally discovered by broadcast traffic advertisements from their client nodes in a network.  
           [0007]    Peer-to-peer networks typically do not contain specialized infrastructure nodes. The IEEE 802.11 standard offers a peer-to-peer mode in addition to an infrastructure mode. Details of the 802.11 standards are set forth in ISO/IEC 8802-11, ANSI/IEEE 802.11 “Information Technology—Telecommunications and Information Exchange Between Systems—Local and Metropolitan Area Network Specific Requirements”, Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications, the entire contents of which being incorporated herein by reference. Also, a description of the 802.11 standard is found in a book by Bob O&#39;Hara and Al Petrick entitled  IEEE  802.11  Handbook: A Designer&#39;s Companion,  IEEE, 1999, the contents comprising this description being incorporated herein by reference.  
           [0008]    Although broadcast communication may be used to identify and configure nodes within the ad-hoc network, wireless ad-hoc routing networks typically avoid repeating broadcast traffic in an effort to avoid “broadcast storms” which can flood the transmission medium with traffic and cripple the ability of the network to perform. Broadcast traffic reception is usually limited to nodes in the immediate listening area of the transmitting node. Since ARP and DHCP depend on broadcast traffic, ad-hoc routing networks sometimes “tunnel” this broadcast traffic in directed packets to known infrastructure nodes where it can be handled. Traditional non-ad-hoc networks do not encounter the broadcast problem because their nodes communicate directly with each other.  
           [0009]    However, wireless peer-to-peer ad-hoc routing networks do not contain infrastructure nodes and therefore do not have the option to tunnel their broadcast traffic. Hence, DHCP, ARP and other broadcast network protocols must be handled in another way. In a traditional wired network, system information is usually broadcast to all devices, while upgrades are sent individually from a central location. In an ad-hoc network, however, it is undesirable to broadcast to all devices of the network since the network could become flooded. Accordingly, a need exists for a system and method where adjacent devices within the ad-hoc network, as well as the infrastructure, may be used to distribute system information directly to adjacent devices upon request without the need for network-wide broadcasts.  
         SUMMARY OF THE INVENTION  
         [0010]    An object of the present invention is to provide a system and method for self-propagating information in an ad-hoc peer-to-peer network.  
           [0011]    Another object of the present invention is to provide a system and method for locating adjacent nodes, or “neighbor” nodes, of a node requesting network data and system upgrades in an ad-hoc network.  
           [0012]    Still another object of the present invention is to provide a system and method for preparing and transmitting a request for specific information between a requesting node and neighbor nodes.  
           [0013]    Still another object of the present invention is to provide a system and method for preparing and transmitting specific information data packets between neighbor nodes and requesting nodes, such that requesting nodes may update network and system information.  
           [0014]    These and other objects are substantially achieved by providing a system and method for identifying adjacent devices within the network which may provide data upgrades. The system and method creates and broadcasts requests for data upgrades between adjacent devices which respond with the requested information. An individual device can update system parameters from information provided by adjacent devices where such transfers are authorized, without network-wide broadcasts. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0015]    These and other objects, advantages and novel features of the invention will be more readily appreciated from the following detailed description when read in conjunction with the accompanying drawings, in which:  
         [0016]    [0016]FIG. 1 is a block diagram of an example of an ad-hoc wireless communications network including a plurality of nodes employing an embodiment of the present invention;  
         [0017]    [0017]FIG. 2 is a block diagram of an example of a wireless node as shown in FIG. 1;  
         [0018]    [0018]FIG. 3A is a block diagram of an example of a broadcast request for information by a node in FIG. 1;  
         [0019]    [0019]FIG. 3B is a block diagram of an example of responses to the broadcast request in FIG. 3A;  
         [0020]    [0020]FIG. 3C is a block diagram of an example of a request for specific information by a node in FIG. 1; and  
         [0021]    [0021]FIG. 3D is a block diagram of an example of a specific response to the broadcast request in FIG. 3C.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0022]    [0022]FIG. 1 is a block diagram illustrating an example of an ad-hoc packet-switched wireless communications network  100  employing an embodiment of the present invention. Specifically, the network  100  includes a plurality of mobile wireless user terminals  102 - 1  through  102 - n  (referred to generally as nodes  102  or mobile nodes  102 ), and can, but is not required to, include a fixed network  104  having a plurality of access points  106 - 1 ,  106 - 2 , . . .  106 - n  (referred to generally as nodes  106  or access points  106 ), for providing nodes  102  with access to the fixed network  104 . The fixed network  104  can include, for example, a core local access network (LAN), and a plurality of servers and gateway routers, to provide network nodes with access to other networks, such as other ad-hoc networks, the public switched telephone network (PSTN) and the Internet. The network  100  further can include a plurality of fixed routers  105 - 1  through  105 - n  (referred to generally as nodes  105  or fixed routers  105 ) for routing data packets between other nodes  102 ,  106  or  105 . It is noted that for purposes of this discussion, the nodes discussed above can be collectively referred to as “nodes  102 ,  105  and  106 ”, or simply “nodes”.  
         [0023]    As can be appreciated by one skilled in the art, the nodes  102 ,  105  and  106  are capable of communicating with each other directly, or via one or more other nodes operating as a router or routers for packets being sent between nodes, as described in U.S. Pat. No. 5,943,322 to Mayor, which is incorporated herein by reference, and in U.S. patent application Ser. Nos. 09/897,790, 09/815,157 and 09/815,164, referenced above.  
         [0024]    As shown in FIG. 2, each node  102 ,  105  and  106  includes a transceiver  108 , including a transmitter and a receiver, which collectively can be referred to as a modem. The transceiver is coupled to an antenna  110  and is capable of receiving and transmitting signals, such as packetized signals, to and from the node  102 ,  106  or  105 , under the control of a controller  112 . The packetized data signals can include, for example, voice, data or multimedia information, and packetized control signals, including node update information.  
         [0025]    Each node  102 ,  105  and  106  further includes a memory  114 , including a read only memory (ROM) for storing information pertaining to the operation of the node, and a random access memory (RAM) for storing information such as routing information pertaining to itself and other nodes in the network  100 . The nodes  102 ,  105  and  106  exchange their respective routing information, referred to as routing advertisements or routing table information, with each other via a broadcasting mechanism periodically, for example, when a new node enters the network  100 , or when existing nodes in the network  100  move.  
         [0026]    As further shown in FIG. 2, certain nodes, especially mobile nodes  102 , can include a host  116  which may consist of any number of devices, such as a notebook computer terminal, mobile telephone unit, mobile data unit, or any other suitable device. Each node  102 ,  105  and  106  also includes the appropriate hardware and software to perform Internet Protocol (IP) and Address Resolution Protocol (ARP), the purposes of which can be readily appreciated by one skilled in the art. The appropriate hardware and software to perform transmission control protocol (TCP) and user datagram protocol (UDP) may also be included.  
         [0027]    Each node of the network in FIG. 1 is required to maintain current network information for proper operation. For instance, the Admission Control (AC) module of transceiver  108  acts on packets flowing between the IP stack module of the host  116  and the IP stack module and the traffic control (TC) module of transceiver  108 . In doing so, the AC module relies on local broadcasts, ad hoc routing updates, and unicast requests for information to provide services to the IP stacks. Further details of the operations and protocols are set forth in a U.S. Provisional Patent Application of Eric A. Whitehill entitled “Embedded Routing Algorithms Under the Internet Protocol Routing Layer in a Software Architecture Protocol Stack”, Serial No. 60/297,769, filed on Jun. 14, 2001, the entire content of which is incorporated herein by reference.  
         [0028]    As discussed in the Background section, if a mobile node  102  in network  100  of FIG. 1 were to broadcast a request for information, such as an ARP request to all the wireless nodes on the network, including all mobile nodes  102  and IAPs  106 , such a broadcast could overload the radio network. Therefore, in an embodiment of the present invention shown in FIG. 2, when a host  116  sends a request for information, the subscriber device transceiver  108  intercepts the request and determines a neighbor node, or nodes, which may provide the information. Once a neighbor node or nodes are determined, the transceiver forwards the request for information directly to the neighbor node for resolution, instead of performing a traditional broadcast of the request. Specifically, the requesting node  102  unicasts the request for information to the neighbor nodes which are capable of responding.  
         [0029]    The neighbor node or nodes, resolve the query by looking first in the neighbor node&#39;s own cache tables, or, if necessary, by querying other adjacent nodes. The neighbor node then returns a message to the requesting node  102  containing the requested information. Specifically, the neighbor node unicasts a reply to the requesting node  102 . In addition to reducing network wide broadcasts, an additional benefit results in that the transfer of a unicast message from the neighbor node to the requesting node is much more reliable than the transfer of a broadcast message.  
         [0030]    In yet another embodiment of the present invention, the requesting node may request a listing of data neighbor nodes are authorized to provide. The neighbor nodes, may in turn, provide a list of current data to the requesting node, thereby allowing the requesting node to determine from the data received if data revisions are required, and thereafter requesting the specific data revisions required.  
         [0031]    In an embodiment of the present invention shown in FIG. 3A, when a mobile node  102 - 7  joins an ad-hoc network it can query its neighbors  102 - 5 ,  102 - 6  and  105 - 2 , to determine the network&#39;s current state. This can be as simple as obtaining network time values, for operations requiring synchronization, or obtaining network configurations, such as channel usage, carrier location in an area and so forth. In addition, it is possible for nodes to negotiate the correct software and upgrade one another if needed.  
         [0032]    In FIG. 3A, when mobile node  102 - 7  is initialized, it performs a neighborhood discovery process, which determines the proximity of nodes  102 - 5 ,  102 - 6  and  105 - 2 . Once the node has an established list of neighbor devices, it can query them for their system parameters. When the neighbor nodes  102 - 5 ,  102 - 6  and  105 - 2 , receive such a request, they create response packets and send them to the requesting node  102 - 7 . The response packets will contain the information each neighbor node is authorized to share regarding the system data.  
         [0033]    Once all response packets are gathered together, node  102 - 7  can determine whether it needs to update any of its parameters and which neighbor node is authorized to provide the required data updates. If none of the neighbors are able and/or willing to provide the updates, then node  102 - 7  can query the infrastructure, such as nodes  106 , for the required information. The infrastructure in the network  100 , such as the IAPs  106   s  points, will typically maintain the system information and any network upgrades.  
         [0034]    Once a candidate is identified, node  102 - 7  can contact the neighbor node and request specific information from that neighbor. If new software is available then a session can be established to transfer the software to the requesting node as well. Once the software has been downloaded, then the controller  112  of node  102 - 7  can perform the upgrade.  
         [0035]    As shown in FIG. 3A, node  102 - 7  can request information from its neighbors, nodes  102 - 5 ,  102 - 6  and  105 - 2 , at any point in time. The request can be triggered on initialization, by time, or by a specific event. Once the trigger is active, node  102 - 7  sends a special broadcast to its neighbors, nodes  102 - 5 ,  102 - 6  and  105 - 2 , asking for specific information, such as current software versions or system parameters. If nodes  102 - 5 ,  102 - 6  and  105 - 2  are authorized to respond to the request, each will create a response packet containing the parameters, or list of parameters authorized to provide, and transmit the packet to the requesting node  102 - 7 , as shown in FIG. 3B. In FIG. 3B, neighbor nodes  102 - 6  and  105 - 2  have prepared and sent response packets to the requesting node  102 - 7 . For illustration purposes, node  102 - 5  lacks authorization to provide the requested information, therefore no response packet is prepared or sent to the requesting node.  
         [0036]    As shown in FIG. 3B, requesting node  102 - 7  receives and reads each response packet to discover what upgrades are required, and which neighbor node is authorized to transfer such upgrades. The requesting node  102 - 7  then requests those items of information it is seeking in FIG. 3C.  
         [0037]    In FIG. 3C, node  102 - 7  prepares and sends a request for specific information packets to node  102 - 6 . For illustration purposes, node  102 - 7  determined no information was required from node  105 - 2 , therefore no further requests are made to node  105 - 2 . Node  102 - 6  reads the request packet from node  102 - 7 , then initiates transfer of the data to the requesting node in FIG. 3D. The transferred data may be a single packet or multiple packets as required and each packet may be acknowledged separately or in blocks. Once all the data is received, the requesting node  102 - 7  acts on the information. This may be as simple as updating its clock or as complex as overwriting the current software load and performing a restart.  
         [0038]    Also, nodes within the network can be configured to require the requesting node to authenticate themselves or prove authorization for the service being requested. In such an embodiment, proper authentication must be given to the nodes requesting updates. Such node authentication may be provided along with access authorization for nodes entering the network, or may be provided elsewhere.  
         [0039]    Furthermore, the network infrastructure may introduce an upgrade program for all mobile nodes that travels from node to node, validating system information. The network will execute this special program to determine if the information in any node is invalid, at which point the software will request updates from the infrastructure. The propagated upgrade program may be initially broadcast to only those nodes in the proximity of the infrastructure originating the upgrade and thereafter, each node will distribute the upgrades as described above. The system or individual nodes of the network may be enabled or disabled for auto-upgrading and propagation of information from one node to another.  
         [0040]    In addition, the present invention may also be utilized for sending information services. For instance, if two neighbor nodes represent devices having subscribed to the same news service, then each may update the other with the latest news, weather, and stock information. Paid advertising can be distributed in a similar fashion. In a first mode, such as peer-to-peer networking without any infrastructure, as a new unit enters the network it can compare its status with its neighbors, including system software. If a new version of software is available then it can be shared by all the systems in the group using the process as well.  
         [0041]    Although only a few exemplary embodiments of the present invention have been described in detail above, those skilled in the art will readily appreciate that many modifications are possible in the exemplary embodiments without materially departing from the novel teachings and advantages of this invention. Accordingly, all such modifications are intended to be included within the scope of this invention as defined in the following claims.