commit b13dad6fde3f7b56ae23e29b3c59c9f6d7bff22b
parent e16fdf760d3fd087b68d2e4a8838852026418527
Author: Alex Balgavy <alex@balgavy.eu>
Date: Tue, 16 Nov 2021 12:11:11 +0100
Update ACN notes
Diffstat:
3 files changed, 64 insertions(+), 0 deletions(-)
diff --git a/content/acn-notes/_index.md b/content/acn-notes/_index.md
@@ -5,3 +5,5 @@ title = 'Advanced Computer Networks'
# Advanced Computer Networks
1. [Intro](intro)
2. [Networking basics](networking-basics)
+3. [Data structures and algorithms used in network designs](data-structures-and-algorithms-used-in-network-designs)
+4. [Network transport](network-transport)
diff --git a/content/acn-notes/data-structures-and-algorithms-used-in-network-designs.md b/content/acn-notes/data-structures-and-algorithms-used-in-network-designs.md
@@ -0,0 +1,47 @@
++++
+title = 'Data structures and algorithms used in network designs'
++++
+# Data structures and algorithms used in network designs
+## How to quickly decide if element exists in a large set
+Used in tasks involving membership detection:
+- access control list (decides if IP address is in blocklist)
+- IP multicast (decides if router port should replicate packet)
+- load balancer (decides if source IP has been assigned to server)
+
+Trivial solutions:
+- unordered list, linear search. O(n) time.
+- ordered list, binary search. O(log n) time.
+
+Hashing:
+- map data to fixed-size values with function
+- hash table indexed by hash values, 1-to-1 mapping
+- constant O(1) time, just computing a function
+- problems: hash collision -- multiple data entries mapped to same hash value
+- choosing good hash functions: deterministic (always same value for same key), efficiently computable, minimize collisions
+ - modulo hashing: $h(x) = x % table_size$, with $table_size$ a prime number
+ - with non-uniformly distributed data, data sharing factors with $table_size$ will be hashed to same values → use prime numbers, which have least factors
+ - other hash functions, e.g. MD5, SHA256
+- handling hash collisions:
+ - data structure that resolves hash collisions
+ - separate chaining: create list of keys that map to same hash value
+ - open addressing: shift values following a given strategy when a collision happens. when trying to find(x), hash and keep looking for x using the strategy until an empty slot is found.
+ - cuckoo hashing: use two hash functions to generate two possible slots for each key, use two hash tables
+ - bloom filter
+
+## How to efficiently count occurrences for large set of elements
+Counting bloom filter:
+- increment counters corresponding to hash values on insert
+- on read, look up counters corresponding to hash values with minimum count
+
+Count-min sketch:
+- three hash functions, each mapped to array of counters (hash tables)
+
+## How to quickly find match on prefix of a string
+Trie: a binary tree where nodes have a part of the prefix
+
+PATRICIA trie: radix trie with radix 2
+
+Direct trie: combine segments in entries
+
+TCAM: hardware implementation
+- supports matching on set of records in constant time
diff --git a/content/acn-notes/network-transport.md b/content/acn-notes/network-transport.md
@@ -0,0 +1,15 @@
++++
+title = 'Network transport'
++++
+# Network transport
+## TCP congestion control
+Congestion control: determine rate to send data on connection, such that network is efficiently utilized, and sender doesn't overrun network capability
+
+In TCP, end hosts control sending rate, based on ACKs.
+
+Packet conservation: for connection to stay in equilibrium, a new packet should not be put into network until an old packet leaves
+
+Reaching equilibrium quickly: TCP slow-start
+- upon receiving ACK, increase congestion window by 1
+
+Packet loss is not good indicator of congestion. Instead, provide a model, estimate parameters for the model based on probing, and decide sending rate using the model.
