Bis Tut 4 Flashcards
Communication Internet TCP/IP reference model
Flooding
- Zu allen Nachbarn exklusive dem von dem bekommen
- zu allen Nachbarn, aber mit sequence number -> nicht 2x versendet
Distance vector routing (DVR)
- Distanzvektoren von A - E eintragen
- delay den günstigsten samt Link
Distance vector routing (DVR)
count-to-infinity problem
The more routers participate, the longer convergence takes Bandwidth is used during convergence
bandwidth per (full-duplex) cable is used up by distance vector routing
Link-State routing
- “hello”-packets are sent regularly to document the router’s aliveness
- Send “echo”-packet to X to measure delay to neighbor X
- Nachbarn mit Kosten
- network is flooded with these Link-State packets (hier für A) - Immer zeitgleich
- Dijkstra - nur positive Kantengewichte, alle Nachbarn kostenaufsteigend besuchen und andere Nachbarn in Warteschlage
Slow Start & Flow Control
datagrams are being sent “slowly” in the beginning in order to achieve an equlibrium without overloading or overburdening the network
- one MSS will be sent
- Every acknowledged burst of data will double the cWnd
- Threshold
Hamming distance
unterschiedlicher Stellen
Knuth Morris Pratt KMP
Left to right
Boyer-Moore with occurrence heuristic (oh)
Right to left
- rightmost position of c in w
- die wo gleich = 0
Boyer-Moore with match heuristic (mh)
Boyer-Moore with combined heuristic (ch)
except for the “0” entries
Tries (from „retrieval“)
retrieval of words by character based
comparissons
Example: {wer, weiß, wo, wir, sind}
PATRICIA Tree
nodes with only one descendant are eliminated (ggf. Infoverlust)
Sistring (semi-infinite string)
- substring of characters
- don’t necessarily contain the whole remaining string, but has to be distinguishable
PAT-Tree
Efficient Search Structures
Editing distance (also known as Levenshtein distance)
to transform s[1…i] into t[1…j]
Dijkstra
kürzester Abstand zur Wurzel als nächstes
