Flooding algorithm (original) (raw)
Záplavový algoritmus je v informatice název algoritmu pro distribuci (materiálu) do všech částí grafu. Název konceptu je odvozen od konceptu zaplavení při povodni. Záplavové algoritmy jsou používány v počítačových sítích (např. při směrování) a v počítačové grafice (např. ). Záplavové algoritmy jsou používány i pro řešení matematických problémů (hledání cesty z bludiště) a mnoha problémů v teorii grafů.
| Property | Value |
|---|---|
| dbo:abstract | Záplavový algoritmus je v informatice název algoritmu pro distribuci (materiálu) do všech částí grafu. Název konceptu je odvozen od konceptu zaplavení při povodni. Záplavové algoritmy jsou používány v počítačových sítích (např. při směrování) a v počítačové grafice (např. ). Záplavové algoritmy jsou používány i pro řešení matematických problémů (hledání cesty z bludiště) a mnoha problémů v teorii grafů. (cs) Flooding (deutsch: fluten) bzw. Flutalgorithmus ist der einfachste Algorithmus zur Informationsverteilung in einem Verteilten System. Voraussetzung ist einzig eine zusammenhängende Topologie. In einem Netz von anfangs nicht informierten Knoten senden ein oder mehrere Initiatorknoten eine Nachricht an alle ihre Nachbarn. Ein Knoten, der die Nachricht erhält und bisher noch nicht informiert wurde, sendet die Nachricht ebenfalls an alle seine Nachbarn, nicht aber zurück an den Absender. Nach einer Weile sind alle Knoten informiert. Da informierte Knoten keine weiteren Nachrichten aussenden, terminiert der Algorithmus. (de) La inundación (en inglés: flooding) consiste en un algoritmo simple de enrutamiento en el cual se envían todos los paquetes entrantes por cada interfaz de salida, excepto por la que se ha recibido. Debido a como funciona el algoritmo de enrutamiento se garantiza que un paquete es entregado (si este puede ser entregado). Este algoritmo de enrutamiento es muy fácil de implementar, aunque con un enfoque bruto e ineficiente. Se aplica en las tramas de descubrimiento, en los puentes de red (bridges) por encaminamiento desde el origen y los transparentes, cuando la dirección de destino es desconocida. Usenet y peer-to-peer (P2P) utilizan las inundaciones, así como los protocolos de enrutamiento como OSPF (Open Shortest Path First), DVMRP (Distance Vector Multicast Routing Protocol) y redes ad-hoc inalámbricas. (es) A flooding algorithm is an algorithm for distributing material to every part of a graph. The name derives from the concept of inundation by a flood. Flooding algorithms are used in computer networking and graphics. Flooding algorithms are also useful for solving many mathematical problems, including maze problems and many problems in graph theory. Different flooding algorithms can be applied for different problems, and run with different time complexities. For example, the flood fill algorithm is a simple but relatively robust algorithm that works for intricate geometries and can determine which part of the (target) area that is connected to a given (source) node in a multi-dimensional array, and is trivially generalized to arbitrary graph structures. If there instead are several source nodes, there are no obstructions in the geometry represented in the multi-dimensional array, and one wishes to segment the area based on which of the source nodes the target nodes are closest to, while the flood fill algorithm can still be used, the jump flooding algorithm is potentially much faster as it has a lower time complexity. Unlike the flood fill algorithm, however, the jump flooding algorithm cannot trivially be generalized to unstructured graphs. (en) In informatica il flooding è un protocollo di instradamento usato dai router che inoltrano un pacchetto in ingresso su tutte le linee ad eccezione di quella da cui proviene.Ogni pacchetto in arrivo viene inoltrato su ogni linea di uscita eccetto quella da cui è arrivato. Questo algoritmo genera un vasto numero di pacchetti duplicati; in effetti, un numero infinito, a meno di non prendere qualche misura per fermare il processo. Per evitare l'invio infinito di pacchetti duplicati si possono utilizzare due accorgimenti: * contatore di salto: si inserisce nel pacchetto un contatore da decrementare ad ogni nuovo router attraversato. Idealmente il valore di tale contatore deve essere uguale al percorso minimo fra sorgente e destinazione ma non conoscendo la topologia della rete si può assegnare un valore uguale al diametro della rete. * numero di sequenza: ogni router deve conoscere la presenza degli altri router e per ogni router dovrà solo controllare che il pacchetto proveniente da quello abbia un numero sequenza maggiore del precedente. Per evitare la crescita all'infinito si adotta una soglia k che riassume la ricezione di tutte le sequenze fino ad appunto k. Raggiunta la soglia il numero si azzera. (it) Um algoritmo de inundação é um algoritmo para distribuir informação para todos nós de um grafo. Cada nó age como um receptor e transmissor de mensagens, e cada mensagem recebida é retransmitida para todos os vizinhos do nó, exceto pelo nó do qual a mensagem foi originada. Algoritmos podem atuar forma mais robusta, adicionando rotinas para evitar transmitir duas vezes para um mesmo nó e para evitar laços infinitos, permitindo que a mensagem eventualmente expire no sistema. Outra variação do algoritmo é responder uma mensagem indicando o recebimento para cada mensagem enviada. Desta forma, o emissor original da mensagem pode saber quando toda a rede recebeu a mensagem, e, alternativamente, quem recebeu a mensagem. (pt) |
| dbo:wikiPageExternalLink | https://arxiv.org/abs/1305.5756 https://web.archive.org/web/20131211173036/http:/users.eastlink.ca/~sharrywhite/Download.html |
| dbo:wikiPageID | 203468 (xsd:integer) |
| dbo:wikiPageLength | 1926 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1066089777 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:Glossary_of_graph_theory dbr:Graph_(discrete_mathematics) dbc:Flooding_algorithms dbr:Spanning_tree dbr:Water_retention_on_mathematical_surfaces dbr:Jump_flooding_algorithm dbr:Flood dbr:Flood_fill dbr:Flooding_(computer_networking) dbr:Graph_theory dbr:Array_data_structure dbr:Spanning_Tree_Protocol dbr:Maze dbr:Time_complexities |
| dbp:wikiPageUsesTemplate | dbt:Short_description |
| dct:subject | dbc:Flooding_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatRoutingAlgorithms yago:WikicatRoutingProtocols yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Communication100033020 yago:Direction106786629 yago:Event100029378 yago:Message106598915 yago:Procedure101023820 yago:Protocol106665108 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Rule106652242 yago:WikicatAlgorithms |
| rdfs:comment | Záplavový algoritmus je v informatice název algoritmu pro distribuci (materiálu) do všech částí grafu. Název konceptu je odvozen od konceptu zaplavení při povodni. Záplavové algoritmy jsou používány v počítačových sítích (např. při směrování) a v počítačové grafice (např. ). Záplavové algoritmy jsou používány i pro řešení matematických problémů (hledání cesty z bludiště) a mnoha problémů v teorii grafů. (cs) Flooding (deutsch: fluten) bzw. Flutalgorithmus ist der einfachste Algorithmus zur Informationsverteilung in einem Verteilten System. Voraussetzung ist einzig eine zusammenhängende Topologie. In einem Netz von anfangs nicht informierten Knoten senden ein oder mehrere Initiatorknoten eine Nachricht an alle ihre Nachbarn. Ein Knoten, der die Nachricht erhält und bisher noch nicht informiert wurde, sendet die Nachricht ebenfalls an alle seine Nachbarn, nicht aber zurück an den Absender. Nach einer Weile sind alle Knoten informiert. Da informierte Knoten keine weiteren Nachrichten aussenden, terminiert der Algorithmus. (de) Um algoritmo de inundação é um algoritmo para distribuir informação para todos nós de um grafo. Cada nó age como um receptor e transmissor de mensagens, e cada mensagem recebida é retransmitida para todos os vizinhos do nó, exceto pelo nó do qual a mensagem foi originada. Algoritmos podem atuar forma mais robusta, adicionando rotinas para evitar transmitir duas vezes para um mesmo nó e para evitar laços infinitos, permitindo que a mensagem eventualmente expire no sistema. Outra variação do algoritmo é responder uma mensagem indicando o recebimento para cada mensagem enviada. Desta forma, o emissor original da mensagem pode saber quando toda a rede recebeu a mensagem, e, alternativamente, quem recebeu a mensagem. (pt) A flooding algorithm is an algorithm for distributing material to every part of a graph. The name derives from the concept of inundation by a flood. Flooding algorithms are used in computer networking and graphics. Flooding algorithms are also useful for solving many mathematical problems, including maze problems and many problems in graph theory. (en) La inundación (en inglés: flooding) consiste en un algoritmo simple de enrutamiento en el cual se envían todos los paquetes entrantes por cada interfaz de salida, excepto por la que se ha recibido. Debido a como funciona el algoritmo de enrutamiento se garantiza que un paquete es entregado (si este puede ser entregado). Este algoritmo de enrutamiento es muy fácil de implementar, aunque con un enfoque bruto e ineficiente. Se aplica en las tramas de descubrimiento, en los puentes de red (bridges) por encaminamiento desde el origen y los transparentes, cuando la dirección de destino es desconocida. (es) In informatica il flooding è un protocollo di instradamento usato dai router che inoltrano un pacchetto in ingresso su tutte le linee ad eccezione di quella da cui proviene.Ogni pacchetto in arrivo viene inoltrato su ogni linea di uscita eccetto quella da cui è arrivato. Questo algoritmo genera un vasto numero di pacchetti duplicati; in effetti, un numero infinito, a meno di non prendere qualche misura per fermare il processo. Per evitare l'invio infinito di pacchetti duplicati si possono utilizzare due accorgimenti: (it) |
| rdfs:label | Záplavový algoritmus (cs) Flooding-Algorithmus (de) Inundación de red (es) Flooding algorithm (en) Flooding (it) Algoritmo de inundação (pt) |
| owl:sameAs | freebase:Flooding algorithm yago-res:Flooding algorithm wikidata:Flooding algorithm dbpedia-cs:Flooding algorithm dbpedia-de:Flooding algorithm dbpedia-es:Flooding algorithm dbpedia-it:Flooding algorithm dbpedia-pt:Flooding algorithm dbpedia-sr:Flooding algorithm https://global.dbpedia.org/id/kCvK |
| prov:wasDerivedFrom | wikipedia-en:Flooding_algorithm?oldid=1066089777&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Flooding_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Flood_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Flooding_algorithm_(computer_graphics) |
| is dbo:wikiPageWikiLink of | dbr:BitTorrent dbr:List_of_graph_theory_topics dbr:Geographic_routing dbr:Usenet dbr:Query_flooding dbr:Spanning_tree dbr:Jump_flooding_algorithm dbr:Link_state_packet dbr:Flood_fill dbr:Flood_(disambiguation) dbr:Flooding_algorithm_(computer_graphics) dbr:MAC_flooding dbr:Multicast dbr:Scalable_Source_Routing dbr:Wireless_sensor_network dbr:ZHLS-GF dbr:Multicast_routing |
| is rdfs:seeAlso of | dbr:Flooding_(computer_networking) |
| is foaf:primaryTopic of | wikipedia-en:Flooding_algorithm |