Broadcast in Wireless multi-hop Networks - Revision history

192.168.3.56: /* Why broadcasting? */

2005-01-28T12:28:07Z

Why broadcasting?

← Older revision		Revision as of 12:28, 28 January 2005
Line 6:		Line 6:
	=== Why broadcasting? ===		=== Why broadcasting? ===

	Broadcasting is a common technique to realize many network ~~issues~~ such as		Broadcasting is a common technique to realize many network functions such as
	*paging,		*paging,
	*sending alarm signals,		*sending alarm signals,
	*routing (e.g., [[DSR]], [[ZRP]], [[AODV]]),		*routing (e.g., [[DSR]], [[ZRP]], [[AODV]]),
	*providing [[Multicast\|multicast]] in rapidly changing topologies.		*providing [[Multicast\|multicast]] in rapidly changing topologies.


	=== Broadcasting by flooding ===		=== Broadcasting by flooding ===

141.20.193.140: /* Conclusion */

2005-01-27T13:43:19Z

Conclusion

← Older revision		Revision as of 13:43, 27 January 2005
Line 108:		Line 108:

	Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] - you'll find nice pictures that might help you seeing things clearer :)		Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] - you'll find nice pictures that might help you seeing things clearer :)
	<br>If you are interested in the results of performance simulations, please take a look at [1].		<br>If you are interested in the results of performance simulations, please take a look at [[http://sar.informatik.hu-berlin.de/teaching/2004-w%20Ad-Hoc%20Networks/readings/11.pdf 1]].


	== Credits ==		== Credits ==

*a at 22:48, 23 January 2005

2005-01-23T22:48:55Z

← Older revision		Revision as of 22:48, 23 January 2005
Line 95:		Line 95:
	*a member who can communicate with a member of another cluster is called ''gateway''		*a member who can communicate with a member of another cluster is called ''gateway''
	*when two heads meet, the one with the larger ID gives up his head role		*when two heads meet, the one with the larger ID gives up his head role


	In a cluster, the head's rebroadcast can cover all other hosts in that cluster if its transmission experiences no collision. So, a non-gateway member does not need to rebroadcast messages. To propagate the broadcast message to hosts in other clusters, gateway hosts should take the responsibility. Both, cluster heads and gateways, use any of the above mentioned probabilistic, counter-based, distance-based or location-based schemes to determine whether to rebroadcast or not.		In a cluster, the head's rebroadcast can cover all other hosts in that cluster if its transmission experiences no collision. So, a non-gateway member does not need to rebroadcast messages. To propagate the broadcast message to hosts in other clusters, gateway hosts should take the responsibility. Both, cluster heads and gateways, use any of the above mentioned probabilistic, counter-based, distance-based or location-based schemes to determine whether to rebroadcast or not.

*a at 22:47, 23 January 2005

2005-01-23T22:47:46Z

← Older revision		Revision as of 22:47, 23 January 2005
Line 31:		Line 31:
	*'''The broadcast is spontaneous.'''<br>Any mobile host can issue a broadcast operation at any time.<br>Preparing any kind of global topology knowledge is prohibitive due to host mobility and the lack of synchronization.		*'''The broadcast is spontaneous.'''<br>Any mobile host can issue a broadcast operation at any time.<br>Preparing any kind of global topology knowledge is prohibitive due to host mobility and the lack of synchronization.
	*'''The broadcast is unreliable.'''<br>No acknowledgement mechanisms will be used.		*'''The broadcast is unreliable.'''<br>No acknowledgement mechanisms will be used.


	=== Redundant Rebroadcasts ===		=== Redundant Rebroadcasts ===
Line 58:		Line 59:
	#lack of CD (''collision detection'')		#lack of CD (''collision detection'')
	#*→host finishes its transmission, even if bits have been garbled		#*→host finishes its transmission, even if bits have been garbled


	Reducing redundant rebroadcasts and differentiating the timing of rebroadcasts are the two major ideas to alleviate the ''Broadcast Storm Problem''.		Reducing redundant rebroadcasts and differentiating the timing of rebroadcasts are the two major ideas to alleviate the ''Broadcast Storm Problem''.
Line 102:		Line 104:
	eliminate many redundant rebroadcasts when the host distribution is dense. If location information is available,		eliminate many redundant rebroadcasts when the host distribution is dense. If location information is available,
	the location-based scheme is dominant because it reduces redundancy w/out compromising the reachability.		the location-based scheme is dominant because it reduces redundancy w/out compromising the reachability.


	Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] - you'll find nice pictures that might help you seeing things clearer :)		Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] - you'll find nice pictures that might help you seeing things clearer :)

*a at 22:45, 23 January 2005

2005-01-23T22:45:18Z

*a at 22:44, 23 January 2005

2005-01-23T22:44:14Z

← Older revision		Revision as of 22:44, 23 January 2005
Line 24:		Line 24:

	Many rebroadcasts are considered to be redundant, since radio propagation is omnidirectional and a physical location may be covered by the transmission ranges of several hosts. As rebroadcasting hosts might be close to each other, heavy contention could exist. Collisions are more likely to occur because the timing of rebroadcasts is highly correlated.		Many rebroadcasts are considered to be redundant, since radio propagation is omnidirectional and a physical location may be covered by the transmission ranges of several hosts. As rebroadcasting hosts might be close to each other, heavy contention could exist. Collisions are more likely to occur because the timing of rebroadcasts is highly correlated.


	== Broadcast Storm Problem - Analysis ==		== Broadcast Storm Problem - Analysis ==
Line 31:		Line 32:
	*'''The broadcast is spontaneous.'''<br>Any mobile host can issue a broadcast operation at any time.<br>Preparing any kind of global topology knowledge is prohibitive due to host mobility and the lack of synchronization.		*'''The broadcast is spontaneous.'''<br>Any mobile host can issue a broadcast operation at any time.<br>Preparing any kind of global topology knowledge is prohibitive due to host mobility and the lack of synchronization.
	*'''The broadcast is unreliable.'''<br>No acknowledgement mechanisms will be used.		*'''The broadcast is unreliable.'''<br>No acknowledgement mechanisms will be used.


	=== Redundant Rebroadcasts ===		=== Redundant Rebroadcasts ===
Line 63:		Line 63:

	Reducing redundant rebroadcasts and differentiating the timing of rebroadcasts are the two major ideas to alleviate the ''Broadcast Storm Problem''.		Reducing redundant rebroadcasts and differentiating the timing of rebroadcasts are the two major ideas to alleviate the ''Broadcast Storm Problem''.


	== Scheme-based Flooding ==		== Scheme-based Flooding ==
Line 98:		Line 99:

	In a cluster, the head's rebroadcast can cover all other hosts in that cluster if its transmission experiences no collision. So, a non-gateway member does not need to rebroadcast messages. To propagate the broadcast message to hosts in other clusters, gateway hosts should take the responsibility. Both, cluster heads and gateways, use any of the above mentioned probabilistic, counter-based, distance-based or location-based schemes to determine whether to rebroadcast or not.		In a cluster, the head's rebroadcast can cover all other hosts in that cluster if its transmission experiences no collision. So, a non-gateway member does not need to rebroadcast messages. To propagate the broadcast message to hosts in other clusters, gateway hosts should take the responsibility. Both, cluster heads and gateways, use any of the above mentioned probabilistic, counter-based, distance-based or location-based schemes to determine whether to rebroadcast or not.


	== Conclusion ==		== Conclusion ==
Line 108:		Line 110:
	Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] - you'll find nice pictures that might help you seeing things clearer :)		Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] - you'll find nice pictures that might help you seeing things clearer :)
	<br>If you are interested in the results of performance simulations, please take a look at [1].		<br>If you are interested in the results of performance simulations, please take a look at [1].


	== Credits ==		== Credits ==

a: / Conclusion */

2005-01-23T22:42:09Z

Conclusion

← Older revision		Revision as of 22:42, 23 January 2005
Line 106:		Line 106:


	Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] ~~for~~ nice pictures that might help you ~~see~~ things clearer :)		Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] - you'll find nice pictures that might help you seeing things clearer :)
	<br>If you are interested in the results of performance simulations, please take a look at [1].		<br>If you are interested in the results of performance simulations, please take a look at [1].

a: / Conclusion */

2005-01-23T22:40:42Z

Conclusion

← Older revision		Revision as of 22:40, 23 January 2005
Line 106:		Line 106:


	Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] for ~~some~~ nice pictures that might help you see things clearer :)		Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] for nice pictures that might help you see things clearer :)
	<br>If you are interested in the results of performance simulations, please take a look at [1].		<br>If you are interested in the results of performance simulations, please take a look at [1].

a: / Broadcasting by flooding */

2005-01-23T22:38:46Z

Broadcasting by flooding

← Older revision		Revision as of 22:38, 23 January 2005
Line 17:		Line 17:

	There are several ways to send a message from one host to all the other hosts.		There are several ways to send a message from one host to all the other hosts.
	Broadcasting done by ~~[[Flooding\|~~flooding]] is a simple and straight-forward approach to deal with this problem.		Broadcasting done by flooding is a simple and straight-forward approach to deal with this problem.
	Unfortunately, if ~~[[Flooding\|~~flooding]] is done blindly, we could observe		Unfortunately, if flooding is done blindly, we could observe
	*redundant rebroadcasts,		*redundant rebroadcasts,
	*heavy contention,		*heavy contention,
Line 24:		Line 24:

	Many rebroadcasts are considered to be redundant, since radio propagation is omnidirectional and a physical location may be covered by the transmission ranges of several hosts. As rebroadcasting hosts might be close to each other, heavy contention could exist. Collisions are more likely to occur because the timing of rebroadcasts is highly correlated.		Many rebroadcasts are considered to be redundant, since radio propagation is omnidirectional and a physical location may be covered by the transmission ranges of several hosts. As rebroadcasting hosts might be close to each other, heavy contention could exist. Collisions are more likely to occur because the timing of rebroadcasts is highly correlated.


	== Broadcast Storm Problem - Analysis ==		== Broadcast Storm Problem - Analysis ==

a: / Collisions */

2005-01-23T22:38:12Z

Collisions

← Older revision		Revision as of 22:38, 23 January 2005
Line 46:		Line 46:
	=== Collisions ===		=== Collisions ===

	CSMA/CA requires a host to ''backoff'' right after the transmission of a message, or when a host wants to transmit but the medium is busy and the previous backoff has been done.		[http://en.wikipedia.org/wiki/CSMA/CA CSMA/CA] requires a host to ''backoff'' right after the transmission of a message, or when a host wants to transmit but the medium is busy and the previous backoff has been done.
	<br>The procedure is as follows:		<br>The procedure is as follows:
	*a counter is set to to an integer randomly picked from the current backoff window		*a counter is set to to an integer randomly picked from the current backoff window

← Older revision		Revision as of 22:45, 23 January 2005
Line 1:		Line 1:
	== Introduction ==		== Introduction ==


	Broadcasting in the field of network communication usually means the distribution of messages/data to a number of recipients.		Broadcasting in the field of network communication usually means the distribution of messages/data to a number of recipients.
Line 50:		Line 49:
	*if ''channel clear assessment'' (CCA) detects no channel activity during the past ''slot'': counter-1		*if ''channel clear assessment'' (CCA) detects no channel activity during the past ''slot'': counter-1
	*counter == 0 ↔ backoff procedure finished		*counter == 0 ↔ backoff procedure finished


	Now consider host '''X''' sending a broadcast.		Now consider host '''X''' sending a broadcast.
Line 60:		Line 58:
	#lack of CD (''collision detection'')		#lack of CD (''collision detection'')
	#*→host finishes its transmission, even if bits have been garbled		#*→host finishes its transmission, even if bits have been garbled


	Reducing redundant rebroadcasts and differentiating the timing of rebroadcasts are the two major ideas to alleviate the ''Broadcast Storm Problem''.		Reducing redundant rebroadcasts and differentiating the timing of rebroadcasts are the two major ideas to alleviate the ''Broadcast Storm Problem''.
Line 96:		Line 93:
	*a member who can communicate with a member of another cluster is called ''gateway''		*a member who can communicate with a member of another cluster is called ''gateway''
	*when two heads meet, the one with the larger ID gives up his head role		*when two heads meet, the one with the larger ID gives up his head role


	In a cluster, the head's rebroadcast can cover all other hosts in that cluster if its transmission experiences no collision. So, a non-gateway member does not need to rebroadcast messages. To propagate the broadcast message to hosts in other clusters, gateway hosts should take the responsibility. Both, cluster heads and gateways, use any of the above mentioned probabilistic, counter-based, distance-based or location-based schemes to determine whether to rebroadcast or not.		In a cluster, the head's rebroadcast can cover all other hosts in that cluster if its transmission experiences no collision. So, a non-gateway member does not need to rebroadcast messages. To propagate the broadcast message to hosts in other clusters, gateway hosts should take the responsibility. Both, cluster heads and gateways, use any of the above mentioned probabilistic, counter-based, distance-based or location-based schemes to determine whether to rebroadcast or not.
Line 106:		Line 102:
	eliminate many redundant rebroadcasts when the host distribution is dense. If location information is available,		eliminate many redundant rebroadcasts when the host distribution is dense. If location information is available,
	the location-based scheme is dominant because it reduces redundancy w/out compromising the reachability.		the location-based scheme is dominant because it reduces redundancy w/out compromising the reachability.


	Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] - you'll find nice pictures that might help you seeing things clearer :)		Please consider looking at my [http://informatik.hu-berlin.de/~ahamann/studies/The_Broadcast_Storm_Problem.pdf presentation notes] - you'll find nice pictures that might help you seeing things clearer :)

Broadcast in Wireless multi-hop Networks - Revision history

192.168.3.56: /* Why broadcasting? */

141.20.193.140: /* Conclusion */

*a at 22:48, 23 January 2005

*a at 22:47, 23 January 2005

*a at 22:45, 23 January 2005

*a at 22:44, 23 January 2005

*a: /* Conclusion */

*a: /* Conclusion */

*a: /* Broadcasting by flooding */

*a: /* Collisions */

a: / Conclusion */

a: / Conclusion */

a: / Broadcasting by flooding */

a: / Collisions */