Enhanced adjacency detection protocol for wireless applications

Abstract

An Adjacency Detection Protocol (ADP) whereby a node in a wireless network may collect information about its neighbors. The collected information enables the establishment of link layer connectivity between a node and its neighbors and also is useful for translating network layer addresses into link addresses. The collected information finds further use in preventing medium contention among adjacent nodes and in handling collisions.

What is claimed is:  
     
         1 . In a wireless packet communication network comprising a plurality of nodes, wherein a first node may directly communicate with some nodes and not with others, a method for preventing contention over a shared communications medium comprising the steps of: 
 receiving, at said first node, a packet from a second node including an estimated receiver processing delay of said second node; thereafter    receiving, at said first node, a request to send (RTS) packet sent by a third node and addressed to said second node; and thereafter    responding, at said first node, to said RTS packet, by inhibiting transmission at said first node for a time period, wherein said time period represents an estimate of time required at said third node to reply to said RTS packet with a clear-to-send (CTS) packet and is determined in accordance with said estimated receiver processing delay.    
     
     
         2 . In a wireless packet communication network comprising a plurality of nodes, wherein a first node may directly communicate with some nodes and not with others, a method for preventing contention over a shared communications medium comprising the steps of: 
 receiving, at said first node, a packet from a second node including an estimated receiver processing delay of said second node; thereafter    receiving, at said first node, a clear to send (CTS) packet sent by a third node and addressed to said second node, said CTS packet including a length of data to be transmitted from said second node to said third node; and thereafter    responding, at said first node, to said CTS packet, by inhibiting transmission at said first node for a time period, wherein said time period is determined in accordance with said length of data and said estimated receiver processing delay of said second node.    
     
     
         3 . A first node adapted to transmit and receive data packets in a wireless communication network, said first node comprising: 
 means for receiving a packet from a second node including an estimated receiver processing delay;    means for receiving a request to send (RTS) packet sent by a third node and addressed to said second node; and    means for responding to said RTS packet by inhibiting transmission at said first node for a time period, wherein said time period represents an estimate of time required at said third node to reply to said RTS packet with a clear-to-send packet and is determined in accordance with said estimated receiver processing delay.    
     
     
         4 . A first node adapted to transmit and receive data packets in a wireless communication network, said first node comprising: 
 means for receiving a packet from a second node including an estimated receiver processing delay of said second node;    means for receiving a clear to send (CTS) packet sent by a third node and addressed to said second node, said CTS packet including a length of data to be transmitted from said second node to said third node; and    means for responding to said CTS packet, by inhibiting transmission at said first node for a time period, wherein said time period is determined in accordance with said length of data and said estimated receiver processing delay of said second node.    
     
     
         5 . In a wireless packet communication network, a method for collecting, at a selected node, information about adjacent nodes with which said selected node may directly communicate, said method comprising the steps of: 
 a) receiving a first link protocol message sent by a first adjacent node; thereafter    b) responding to said first link protocol message by electronically storing an entry including a link layer address of said first adjacent node in a link table, said indication including an indication of a candidate link to said first adjacent node; 
 setting a first timer to count for a first predetermined time period;  
 transmitting a second link protocol message including a link layer address of said first adjacent node;  
   c) if said first timer expires prior to receipt of any third link protocol message from said first adjacent node, deleting said link table entry; and    d) if a third link protocol message including parameters of said first adjacent node is received prior to expiration of said first timer, changing said candidate link indication to a good link indication.    
     
     
         6 . The method of  claim 5  wherein said (d) step comprises the substeps of: 
 if said third link protocol message replying to said second link protocol message is received prior to expiration of said first timer,  
 (d1) extracting parameters of said first adjacent node from said third link protocol message; and  
 (d2) storing said parameters as a part of said link table entry.  
 
     
     
         7 . The method of  claim 5  wherein said (d) step comprises the substeps of: 
 if said third link protocol message replying to said second link protocol message is received prior to expiration of said first timer,  
 (d1) invoking a network layer protocol to obtain an network layer address of said first adjacent node,  
 (d2) electronically storing, at said selected node, said network layer address of said first adjacent node and said link layer address of said first adjacent node as an entry in an address resolution table.  
 
     
     
         8 . The method of  claim 7  wherein said (d1) step comprises invoking a Reverse Address Resolution Protocol (RARP) program.  
     
     
         9 . In a wireless packet communication network, apparatus for collecting, at a selected node, information about adjacent nodes with which said selected node may directly communicate, said apparatus comprising: 
 a) means for receiving a first link protocol message sent by a first adjacent node;    b) means for responding to said first link protocol message by 
 electronically storing an entry including a link layer address of said first adjacent node in a link table, said indication including an indication of a candidate link to said first adjacent node; and  
 setting a first timer to count for a first predetermined time period;  
 transmitting a second link protocol message including a link layer address of said first adjacent node; thereafter  
   c) means for, if said first timer expires prior to receipt of any third link protocol message from said first adjacent node, deleting said link table entry; and    d) means for, if a third link protocol message including parameters of said first adjacent node is received prior to expiration of said first timer, changing said candidate link indication to a good link indication.    
     
     
         10 . The apparatus of  claim 9  further comprising: 
 means for, if said third link protocol message replying to said second link protocol message is received prior to expiration of said first timer, 
 extracting parameters of said first adjacent node from said third link protocol message; and  
 storing said parameters as a part of said entry.  
 
 
     
     
         11 . The apparatus of  claim 9  further comprising means for: 
 if said third link protocol message replying to said second link protocol message is received prior to expiration of said first timer,  
 invoking a network layer protocol to obtain a network layer address of said first adjacent node,  
 electronically storing, at said selected node, said IP address of said first adjacent node and said link layer address of said first adjacent node as an entry in an address resolution table.  
 
     
     
         12 . The method of  claim 11  wherein said invoking means comprises means for invoking a Reverse Address Resolution Protocol (RARP) program.  
     
     
         13 . In a wireless packet communication network, a method for collecting, at a selected node, IP address information about adjacent nodes with which said selected node may directly communicate, said method comprising the steps of: 
 establishing a link between a selected node and a first adjacent node using a link layer protocol, wherein a link layer address of said first adjacent node is obtained; thereafter    invoking, responsive to successful establishment of a link in said establishing step, a network layer protocol to obtain a network layer address of said first adjacent node; and thereafter    storing said network layer address of said adjacent node and said link layer address of said adjacent node as an entry in an address resolution table.    
     
     
         14 . The method of  claim 13  wherein said invoking step comprises invoking a Reverse Address Resolution Protocol (RARP) routine to obtain an IP address of said first adjacent node.  
     
     
         15 . In a wireless packet communication network, apparatus for collecting, at a selected node, IP address information about adjacent nodes with which said selected node may directly communicate, said apparatus comprising: 
 means for establishing a link between a selected node and a first adjacent node using a link layer protocol, wherein a link layer address of said first adjacent node is obtained;    means for invoking, responsive to successful establishment of a link in said establishing step, a network layer protocol to obtain a network layer address of said first adjacent node; and    means for storing said network layer address of said adjacent node and said link layer address of said adjacent node as an entry in an address resolution table.    
     
     
         16 . The apparatus of  claim 15  wherein said invoking means comprises means for invoking a Reverse Address Resolution Protocol (RARP) routine to obtain an IP address of said first adjacent node.