User:WikiLinuz/Notes

TCP reset attack

const char *const SOURCE_IPv4_ADDRESS = "91.198.174.192";
const char *const DESTINATION_IPv4_ADDRESS = "172.16.4.244";
struct __attribute__((__packed__)) ipv4_packet {
  struct __attribute__((__packed__)) {
#if __BYTE_ORDER == __LITTLE_ENDIAN
    unsigned int ihl : 4;
    unsigned int version : 4;
#elif __BYTE_ORDER == __BIG_ENDIAN
    unsigned int version : 4;
    unsigned int ihl : 4;
#endif
    uint8_t tos;
    uint16_t tot_len;
    uint16_t id;
    uint16_t frag_off;
    uint8_t ttl;
    uint8_t protocol;
    uint16_t check;
    uint32_t saddr;
    uint32_t daddr;
  } ip;
  struct __attribute__((__packed__)) {
    uint32_t source_ip;
    uint32_t destination_ip;
    uint16_t source_port;
    uint16_t destination_port;
  } header;
  char ip_payload[512];
};
struct ipv4_packet *craft_ipv4_tcp_packet() {
  struct ipv4_packet *ipv4_tcp = calloc(sizeof(struct ipv4_packet), 1);
  if (!ipv4_tcp) return NULL;
  ipv4_tcp->ip.ihl = 5;
  ipv4_tcp->ip.check = 0;
  ipv4_tcp->ip.daddr = inet_addr(SOURCE_IPv4_ADDRESS);
  ipv4_tcp->ip.saddr = inet_addr(DESTINATION_IPv4_ADDRESS);
  ipv4_tcp->ip.frag_off = 0x000;
  ipv4_tcp->ip.ttl = 64;
  ipv4_tcp->ip.tos = 0;
  ipv4_tcp->ip.protocol = 0x6;
  ipv4_tcp->ip.id = 0x1EF0;
  return ipv4_tcp;
}

AVL Tree

This article also needs to be re-written. The recommended encyclopedic structure:

Definition
- Balance factor
Operations
- Search
- Traversal
- Insert
  - Rotations
- Delete
  - Rotations

Insert::Rotations
LL, RR, RL, LR

Delete::Rotations
R0, R1, R-1, L0, L1, L-1

Remove every C++ nonsense and replace it with (sourced) language-agnostic MOS:ALGO.

GA notes

Potential nominees

Consistent hashing — mostly good, needs a bit of ce.
Hash table#Performance — re-written basically core parts, but needs work starting from "Performance" sub-heading.
Heartbeat (computing) — a picture?

Currently active ones

Sources

Bittorrent

Bram Cohen (10 January 2008). "The BitTorrent Protocol Specification".
David Harrison (10 January 2008). "Index of BitTorrent Enhancement Proposals".

Distributed cache

More information // collapsed // ...

// collapsed //

Kurcewicz, Michal; Sylwestrzak, Wojtek; Wiezbiki, Adam (25 November 1998). "A distributed WWW cache". Computer Networks and ISDN Systems. 30 (22–23). Elsevier, University of Warsaw. doi:10.1016/S0169-7552(98)00243-8 – via ScienceDirect.
Wang, Dongsheng; Huang, Chuanhe (3 October 2018). "Distributed cache memory data migration strategy based on cloud computing". Concurrency and Computation: Practice and Experience. 31 (10). National Natural Science Foundation of China. doi:10.1002/cpe.4828.
Federighi, Craig; Rowe, Lawrence A. (1 April 1994). "Distributed hierarchical storage manager for a video-on-demand system". International Symposium On Electronic Imaging Science & Technology. 2185. San Jose, California: SPIE. doi:10.1117/12.171775.
Benjamin Berg; Daniel S. Berger; Sara McAllister; Sathya Gunasekar (November 2020). The CacheLib caching engine: design and experiences at scale (PDF). USENIX Conference on Operating Systems Design and Implementation. Facebook, Microsoft Research, Carnegie Mellon University.

Miscellaneous/off-topic

Erin Green (7 January 2015). "Inside Wikipedia's translation to HHVM". Facebook.

Ephemeral storage

Binary search tree

Height

This should be probably moved to AVL tree
Height of the binary search tree is defined as the maximum of the heights of left subtree and right subtree incremented by a factor of 1. Following is a recursive procedure for calculating the height of the BST given a root $x$ :^[1]^: 303-304

 Tree-Height(x)
   if x = NIL then
     return -1
   end if
   left_height := Tree-Height(x.left)
   right_height := Tree-Height(x.right)
   if left_height > right_height then
     return left_height + 1
   else
     return right_height + 1
   end if

Hash tables

Remarks from David Eppstein:

A few points:

Space-time tradeoff paragraph of lead: makes no sense to me and not summarizing anything later.
History really deserves more than a three-line summary.
"Ershov had the same idea": Who? When? How was it disseminated?
"finite entries in the hash table": what would an entry that is not finite look like?
There is no overview section saying what a hash table is; the only material about that is in the lead.
Hash function section starts getting into details about desiderata and methods without ever saying clearly what it is: a function, often incorporating a small random seed, for mapping keys to table addresses.
"Uniformity is sometimes difficult to ensure by design, but may be evaluated empirically using statistical tests,": this feels like really out-of-date advice when we now have theoretical methods for guaranteeing correct behavior of hash functions (k-independence). K-independence and universal are written about in two separate paragraphs as if they are two separate things (they are not).

Somewhere around here is the point, about 1/3 of the way of the article, where in a real review I would have given up and quick-failed it because there are just too many points where it is too far from having the appropriate coverage. The next section, on collision resolution methods, for instance, is probably too detailed on some methods and again really misses the big picture, failing both WP:GACR 3a and 3b.

In case you plan to make the necessary significant revisions and might find it helpful, my lecture notes on this material (for one week out of a graduate-level course on data structures) are https://www.ics.uci.edu/~eppstein/261/lecture2a.pdf, https://www.ics.uci.edu/~eppstein/261/lecture2b.pdf, https://www.ics.uci.edu/~eppstein/261/lecture2c.pdf — there's also related material in weeks 1 (the dynamic arrays you need for resizable hash tables) and weeks 3-4 (other hashing-related data structures that are not actually hash tables).

[1]
Thareja, Reema (13 October 2018). "Hashing and Collision". Data Structures Using C (2 ed.). Oxford University Press. ISBN 9780198099307.