Jump to content

User:WikiLinuz/Notes

From Wikipedia, the free encyclopedia

TCP reset attack

[edit]

For 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

[edit]

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

[edit]

Potential nominees

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

Currently active ones

[edit]
  1. Binary search tree
  2. Trie

Sources

[edit]

Bittorrent

[edit]
  1. Bram Cohen (10 January 2008). "The BitTorrent Protocol Specification".
  2. David Harrison (10 January 2008). "Index of BitTorrent Enhancement Proposals".

Distributed cache

[edit]
// collapsed //
  1. 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.
  2. 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.
  3. 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.
  4. 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.
See also: 1 and 2
  1. Rajesh Nishtala; Hans Fugal; Steven Grimm; Marc Kwiatkowski (3 April 2013). "Scaling Memcache at Facebook". USENIX Symposium on Networked Systems Design and Implementation. Facebook.
  2. Qi Huang; Ken Birman; Robbert van Renesse; Sanjeev Kumar (November 2013). "An analysis of Facebook photo caching". SOSP '13: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principle. Association for Computing Machinery. doi:10.1145/2517349.2522722.
  3. Sathya Gunasekar; Nathan Beckmann; Benjamin Berg; Jimmy Lu (26 October 2021). "Kangaroo: Caching Billions of Tiny Objects on Flash". ACM Symposium on Operating Systems Principles. Facebook, Carnegie Mellon University, Microsoft Research.
  4. Carlos E. Gomez; Maria del Pilar Villamil; Harold E. Castro; Lourent d'Orazio (2009). "DHTCache: A Distributed Service to Improve the Selection of Cache Configurations within a Highly-Distributed Context, Data Management in Grid and Peer-to-Peer Systems". International Conference on Data Management in Grid and P2P Systems. 5697. Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-03715-3_5. ISBN 978-3-642-03715-3.
  5. Lorent d'Orazio; Febrice Jouanot; Cyril Labbe; Claudia Roncancio (November 2005). "Building adaptable cache services". MGC '05: Proceedings of the 3rd international workshop on Middleware for grid computing. New York: Association for Computing Machinery. doi:10.1145/1101499.1101502. ISBN 1595932690.
  6. Panos Kalnis; Wee Siong Ng; Beng Chin Ooi; Dimitris Papdias (June 2002). "An adaptive peer-to-peer network for distributed caching of OLAP results". Association for Computing Machinery. doi:10.1145/564691.564695. ISBN 1581134975. {{cite journal}}: Cite journal requires |journal= (help)
  7. C Grimm; J. S Vockler; H Pralle (30 September 1998). "Load and traffic balancing in large scale cache meshes". Computer Networks and ISDN Systems. 30 (16–18). University of Hanover, Institute for Computer Networks and Distributed Systems. doi:10.1016/S0169-7552(98)00197-4 – via Elsevier.
  8. Parulian; Muhammad Zarlis; Benny BenyaminNasution (July 2019). "Comparation of distributed cache and centralized cache on web proxy". 723. Universitas HKBP Nommensen. {{cite journal}}: Cite journal requires |journal= (help)
  9. Reuven Cohen; Itai Dabran. "The "Last-Copy" Approach for Distributed Cache Pruning in a Cluster of HTTP Proxies". International Workshop on Protocols for High Speed Networks. Berlin, Heidenberg: Springer. doi:10.1007/3-540-47828-0_6. ISBN 978-3-540-43658-4.
  10. Aguilar, Jose; Leiss, Ernst (19 October 2001). "A Web Proxy Cache Coherency and Replacement Approach". Web Intelligence: Research and Development. Berlin, Heidelberg: Springer. doi:10.1007/3-540-45490-X_8. ISBN 978-3-540-42730-8.
  11. Lamparter, Bernd; Fouquet, Isabell (1999). "Distributed Cache Index". Kommunikation in Verteilten Systemen (KiVS). Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-60111-8_36. ISBN 978-3-540-65597-8.
  12. Kawai, Eiji (2019). "Acceleration of WWW Service with Distributed Cache Technology". Pennsylvania State University. {{cite journal}}: Cite journal requires |journal= (help)
  13. Huang, Yuan Qiang (September 2014). "Design and Implementation of Distributed Cache System in Cluster Environment". 635–637. Beijing, China: China National Petroleum Corporation. doi:10.4028/www.scientific.net/AMM.635-637.1530. {{cite journal}}: Cite journal requires |journal= (help)
  14. Liu, Shenling; Zhang, Chunyuan (16 September 2017). "DCC: Distributed Cache Consistency". Data Science. Springer. doi:10.1007/978-981-10-6388-6_31. ISBN 978-981-10-6388-6.
  15. Yoshida, Akitoshi (19 May 1998). "MOWS: distributed Web and cache server in Java". Computer Networks and ISDN Systems. 29 (8–13). Mannheim, Germany: University of Mannheim, Elsevier. doi:10.1016/S0169-7552(97)00025-1.
  16. Xinhua, E.; Zhu, Benjie (February 2018). "A Distributed Cache Update Deployment Strategy in CDN". Journal of Physics: Conference Series. 1004.
  17. Lio, Masmitsu; Hirata, Kouji; Yamamoto, Miki (2017). Content Download Method with Distriuted Cache Management (PDF). International MultiConference of Engineers and Computer Scientists. Vol. 2. Hong Kong: International Association of Engineers. ISBN 978-988-14047-7-0. ISSN 2078-0958. Archived (PDF) from the original on 12 July 2020. Retrieved 27 December 2021. {{cite conference}}: |archive-date= / |archive-url= timestamp mismatch; 13 July 2020 suggested (help)

Miscellaneous/off-topic

[edit]
  1. Erin Green (7 January 2015). "Inside Wikipedia's translation to HHVM". Facebook.
See also: 1
  1. Gabriel Wicke (4 March 2013). "Parsoid: How Wikipedia catches up with the web". MediaWiki.
IP Volume Inc

A wild wild west Dutch bulletproof hoster (AS202425 based in Seychelles, virtually impenetrable) - wildly known for hosting child abuse material on the open web (cybercrime, etc.), and refusing to remove those.

Ephemeral storage

[edit]

Binary search tree

[edit]

Height

[edit]

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 :[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

[edit]

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.