We claim:
1. A FIFO buffer providing reduced access times without introducing any latency overhead, comprising:
FIFO means capable of storing n data words, each m bits wide, having an m bit wide data input terminal;
read data selection means connected to data output terminals of the FIFO means and having two data output terminals providing simultaneous access to a selected storage location;
odd read pointer generating means for providing the selection input to the data selection means for selecting data at an odd read address;
even read pointer generating means for providing the selection input to the data selection means for selecting data at an even read address;
multiplexing means coupled to each of the two data output terminals of the read data selection means for selecting one of the outputs of the read data selection means as the final output of the FIFO; and
state controlling means coupled to the multiplexing means for controlling the selection of the final FIFO output and to the odd and even read pointer generating means.
2. The improved FIFO buffer of claim 1, further comprising FIFO status providing means coupled to a selected read pointer means for generating FIFO status signals.
3. The improved FIFO buffer of claim 1, further comprising adder means coupled to the selected read pointer generating means to increment the read address for generating the next read address.
4. The improved FIFO buffer of claim 1 wherein said state maintaining means can have two states namely, odd and even.
5. A method for reducing the access times of a FIFO buffer without introducing latency overhead, comprising the steps of:
providing a FIFO capable of storing n data words, each m bits wide, having an m bit wide data input terminal;
connecting a read data selector to an output of the FIFO and providing simultaneous access to a selected storage location at an odd address and a selected storage location at an even address;
providing selection inputs to the read data selector for selecting an odd read address and an even read address;
multiplexing the output of the read data selector to enable selection of a desired one of the outputs of the read data selector as the final output of the FIFO; and
controlling the state of the FIFO to select one of the multiplexer output as the final output of the FIFO and to control the selection input to the read data selector for selecting an odd read address and an even read address.
6. The method of claim 5, further comprising generating FIFO status signals.
7. The method of claim 5, further comprising generating the next read address by incrementing the current read address.
8. The method of claim 5 wherein said state can be odd or even.
9. A synchronous FIFO buffer, comprising:
a FIFO circuit configured to receive, store, and output data;
a data select circuit coupled to the FIFO circuit to receive data from the FIFO circuit and having a first data output for outputting even data and a second data output for outputting odd data;
a multiplexer circuit coupled to the first and second data outputs of the data select circuit and having a control input and a read data output;
a finite state machine having an output coupled to the control input of the multiplexer circuit, the finite state machine configured to generate a control signal to control the output of the multiplexer circuit; and
a pointer circuit coupled to the finite state machine and configured to generate a read address that is output to the data select circuit.
10. The FIFO circuit of claim 9, wherein the data select circuit is configured to receive a next word from the FIFO circuit and assign it to one of the first data output and the second data output that is not in current use.
11. The FIFO buffer of claim 9, wherein the finite state machine comprises a single D-flip-flop.
12. The FIFO buffer of claim 9, wherein the finite state machine is configured to maintain two states, an odd state and an even state.
13. The FIFO buffer of claim 9, wherein the pointer circuit comprises an odd read pointer circuit and an even read pointer circuit, each coupled to the data select circuit and configured to select an odd read address and an even read address, respectively.
14. A FIFO buffer circuit, comprising: a FIFO circuit configured to receive, store, and output words to a first data bus and a second data bus, and control means coupled to the FIFO circuit and the first and second data outputs and configured to fetch a next word from the FIFO and assign it to one of the first data output and the second data output that is not currently in use.
15. The FIFO buffer of claim 14, wherein the control means comprise a finite state machine coupled to a multiplexer, the multiplexer having the first data output and the second data output as inputs and a read data output as an output.
16. The FIFO buffer of claim 15, wherein the finite state machine comprises a D-flip-flop.
17. A method for reducing access time to a FIFO buffer, comprising:
fetching a next word from a FIFO circuit and assigning it to one of a first data out bus and a second data out bus that is not currently in use.
18. A method for providing access to a FIFO buffer, comprising:
providing simultaneous access to a selected storage location at an odd address and a selected storage location at an even address from an output of a FIFO circuit;
providing selection inputs to a read data selector for selecting an odd read address and an even read address;
multiplexing an output of the read data selector to enable selection of a desired one of the outputs of the read data selector as the final output of the FIFO circuit; and
controlling the state of the FIFO to select one of the multiplexer output as the final output of the FIFO and to control the selection input to the read data selector for selecting an odd read address and an even read address.
19. The method of claim 18, comprising controlling the state of the FIFO with a finite state machine configured to have two states, an odd state and an even state.
20. The method of claim 19, further comprising generating a next read address by incrementing a current read address.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A communication unit to transmit and receive information within a communications network and to control transference of said information to reduce network overhead traffic comprising:
a transmitter to transmit outgoing information to at least one other communication unit within said network;
a receiver to receive incoming information from at least one other communication unit within said network;
a storage unit to store routing information; and
a processor to control said transmission and reception of said outgoing and incoming information, wherein said processor includes:
a traffic control module to facilitate transmission of a network message based on occurrence of a first type of network condition indicating a change in at least one of routing and topology within said communications network and to selectively facilitate transmission of said network message in response to occurrence of a second type of network condition, wherein said network message includes an update message to synchronize said routing information within storage units of said communication units of said communications network, wherein transmission of said network message to synchronize said routing information is performed upon occurrence of said first type of network condition, wherein transmission of said network message to synchronize said routing information in response to occurrence of said second type of network condition is performed upon the earlier of expiration of a maximum allowable time interval for transmission of said network message and a rate of occurrence of said second type of network condition attaining a desired level, and wherein said traffic control module includes:
a rate compare module to compare a quantity of occurrences of said second type of network condition within a predetermined time interval to a rate threshold value to determine attainment of said desired level by said rate of occurrence.
2. The unit of claim 1, wherein said communications network includes an ad-hoc wireless network.
3. The unit of claim 1 further including:
a transmission timer to measure a predetermined time interval for transmissions; and
an interval timer to measure elapsed time;
wherein said processor further includes:
a recordation module to maintain a quantity of occurrences of said first and second types of network conditions and a quantity of expirations of said interval timer, wherein entries stored in said storage unit are associated with update messages received from other communication units and corresponding quantities of occurrence of said first and second types of network conditions; and
a retrieval module to retrieve entries from said storage unit associated with said received update messages.
4. The unit of claim 3, wherein said update message includes a Link State Advertisement.
5. The unit of claim 1, wherein said communications network includes at least one group each including at least one said communication unit, and wherein said second type of network condition includes a change in a size of a group.
6. The unit of claim 3, wherein said traffic control module includes:
a transmission module to examine each retrieved entry and to facilitate transmission of a corresponding update message in accordance with said quantity of occurrences of said first type of network condition associated with that entry indicating an occurrence of said first type of network condition.
7. The unit of claim 6, wherein said traffic control module further includes:
a delay transmission module to examine each retrieved entry and to selectively facilitate transmission of a corresponding update message in response to one of said expiration of said maximum allowable time interval and said rate of occurrence of said second type of network condition attaining said desired level.
8. The unit of claim 7, wherein said delay transmission module further includes:
a time compare module to compare said quantity of timer expirations to a timer threshold value to determine said expiration of said maximum allowable time interval.
9. The unit of claim 8, wherein said delay transmission module further includes said rate compare module, and wherein said rate compare module is configured to perform said determination of attainment of said desired level in response to determining that said maximum allowable time interval has not expired.
10. The unit of claim 3, wherein said processor further includes:
a reset module to reset said quantity of occurrences of said first and second types of network conditions and said quantity of interval timer expirations in response to transmission of said network message.
11. The unit of claim 1, wherein said incoming and outgoing information is in the form of Radio Frequency (RF) signals.
12. A method of controlling transference of information between a communication unit and other units within a communications network to reduce network traffic comprising:
(a) transmitting a network message from a communication unit upon occurrence of a first type of network condition indicating a change in at least one of routing and topology within said communications network, wherein said network message includes an update message to synchronize routing information within storage units of said communication units of said communications network; and
(b) selectively transmitting said network message from said communication unit in response to occurrence of a second type of network condition, wherein transmission of said network message to synchronize said routing information in response to occurrence of said second type of network condition is performed upon the earlier of expiration of a maximum allowable time interval for transmission of said network message and a rate of occurrence of said second type of network condition attaining a desired level, and wherein a quantity of occurrences of said second type of network condition within a predetermined time interval is compared to a rate threshold value to determine attainment of said desired level by said rate of occurrence.
13. The method of claim 12, wherein said communications network includes an ad-hoc wireless network.
14. The method of claim 12, wherein said communication unit includes:
a transmission timer to measure a predetermined time interval for transmissions; and
an interval timer to measure elapsed time;
wherein step (a) further includes:
(a.1) maintaining a quantity of occurrences of said first and second types of network conditions and a quantity of expirations of said interval timer, wherein entries stored in said storage unit are associated with update messages received from other communication units and corresponding quantities of occurrence of said first and second types of network conditions; and
(a.2) selectively retrieving entries from said storage unit associated with said received update messages.
15. The method of claim 14, wherein said update message includes a Link State Advertisement.
16. The method of claim 12, wherein said communications network includes at least one group each including at least one said communication unit, and wherein said second type of network condition includes a change in a size of a group.
17. The method of claim 14, wherein step (a) further includes:
(a.3) examining each retrieved entry and transmitting a corresponding update message in accordance with said quantity of occurrences of said first type of network condition associated with that entry indicating an occurrence of said first type of network condition.
18. The method of claim 17, wherein step (b) further includes:
(b.1) examining each retrieved entry and selectively transmitting a corresponding update message in response to one of said expiration of said maximum allowable time interval and said rate of occurrence of said second type of network condition attaining said desired level.
19. The method of claim 18, wherein step (b) further includes:
(b.1.1) comparing said quantity of timer expirations to a timer threshold value to determine said expiration of said maximum allowable time interval.
20. The method of claim 19, wherein step (b) further includes:
(b.1.2) determining attainment of said desired level in response to determining that said maximum allowable time interval has not expired.
21. The method of claim 14 further including:
(c) resetting said quantity of occurrences of said first and second types of network conditions and said quantity of interval timer expirations in response to transmission of said network message.
22. The method of claim 12, wherein said information transferred between said communication units is in the form of Radio Frequency (RF) signals.
23. A communications network comprising:
a plurality of communication units for transferring information therebetween, wherein each communication unit includes a storage unit to store routing information, wherein network messages are transmitted based on occurrence of a first type of network condition indicating a change in at least one of routing and topology within said communications network and selectively transmitted in response to occurrence of a second type of network condition, wherein said network message includes an update message to synchronize said routing information within storage units of said communication units of said communications network, wherein transmission of said network message to synchronize said routing information is performed upon occurrence of said first type of network condition, wherein transmission of said network messages to synchronize said routing information in response to occurrence of said second type of network condition is performed upon the earlier of expiration of a maximum allowable time interval for transmission of said network messages and a rate of occurrence of said second type of network condition attaining a desired level, and wherein said communication units compare a quantity of occurrences of said second type of network condition within a predetermined time interval to a rate threshold value to determine attainment of said desired level by said rate of occurrence.
24. The network of claim 23, wherein said communications network includes an ad-hoc wireless network.
25. The network of claim 23, wherein each communication unit further includes:
a transmission timer to measure a predetermined time interval for transmissions; and
an interval timer to measure elapsed time;
wherein said communication units maintain a quantity of occurrences of said first and second types of network conditions and a quantity of expirations of said interval timer, and entries stored in said storage unit are associated with update messages received from other communication units and corresponding quantities of occurrence of said first and second types of network conditions.
26. The network of claim 25, wherein said update message includes a Link State Advertisement.
27. The network of claim 23, wherein said communications network includes at least one group each including at least one said communication unit, and wherein said second type of network condition includes a change in a size of a group.
28. The network of claim 25, wherein said communication units examine each entry associated with a received update message within a corresponding storage unit and transmit a corresponding update message in accordance with said quantity of occurrences of said first type of network condition associated with that entry indicating an occurrence of said first type of network condition.
29. The network of claim 25, wherein said communication units examine each entry associated with a received update message within a corresponding storage unit and selectively transmit a corresponding update message in response to one of said expiration of said maximum allowable time interval and said rate of occurrence of said second type of network condition attaining said desired level.
30. The network of claim 29, wherein said communication units compare said quantity of timer expirations to a timer threshold value to determine said expiration of said maximum allowable time interval.
31. The network of claim 30, wherein said communication units determine attainment of said desired level in response to determining that said maximum allowable time interval has not expired.
32. The network of claim 25, wherein said communication units reset said quantity of occurrences of said first and second types of network conditions and said quantity of interval timer expirations in response to transmission of said network message.
33. The network of claim 23, wherein said transferred information is in the form of Radio Frequency (RF) signals.