Facebook 这个岗位虽然叫 Network Engineer，但是它的 OA 基本只考了 BGP 这一个协议，而且考得十分的深入。如果没有直接相关经历，可能很难通过它的考核。不过总结出的这份资料对我以后还是蛮有用的。

Computer Networks

Chapter 1

1. Routing & forwarding:
   • Routing: Determines source-destination route taken by packets;
   • Forwarding: Move packets from router’s input to appropriate router output.
2. Circuit switching (dedicated resources & not sharing) vs packet switching.
3. Delay: d_nodal = d_proc + d_queue + d_trans + d_prop
   • d_proc: Check bit errors, determine output;
   • d_queue: Waiting at output link for transmission;
   • d_trans: packet length / bandwidth;
   • d_prop: distance / speed of light.
4. Layers:
   • Application: Message;
   • Transport: Segment;
   • Network: Datagram;
   • Link: Frame;
   • Physical: Bits on the wire.

Chapter 2

1. TCP & UDP:
   • TCP: Reliable transport, flow control (won’t overwhelm receiver), congestion control (throttle sender when network overloaded), connection-oriented;
   • UDP: Unreliable data transfer;
   • SSL provides encrypted TCP connection (Integrity & authentication). SSL is at app layer.
2. HTTP connections can be persistent (multiple objects over single TCP connection) or non-persistent (at most one object over single TCP connection, need at least 2 RTT).
3. Client <– POP/IMAP/HTTP –> Mail server <– SMTP –> Mail server <– POP/IMAP/HTTP –> Client.
4. DNS (Doomain name system) is an app-layer protocol. It’s distributed and hierarchical.

   • Iterated query (left) & recursive query (right):

     

   • Types:

     • A: Name: ranthot.cn, value: 8.8.8.8, type: A, TTL: …;
     • NS: Name: ranthot.cn, value: ns1.registrar.com, …;
     • CNAME: Name: ranthot.cn, value: servereast.backup2.ranthot.cn, …;
     • MX: Name: ranthot.cn, value: mailserver.ranthot.cn, ….

Chapter 3

1. Transport layer: Logical communication between processes; Network layer: Logical communication between hosts.
2. Multiplexing & demultiplexing:
   • Multiplexing: Handle data from multiple sockets, add transport header;
   • Demultiplexing: Use header info to deliver received segments to correct socket.
3. Internet checksum: Add together, add carryout, then one’s complement.
4. RDT (Reliable data transfer):
   • 
5. Go-back-N & selective repeat:
   • Go-back-N: Send N unacked packets in pipeline; Receiver only sends cumulative ACK; Sender has timer for oldest unacked packet;
   • Selective repeat: Send N unacked packets in pipeline: Receiver send individual ack for each; Sender has timer for each packet.
6. TCP segment structure:
   • 
7. Timeout interval for TCP:
   • EstimatedRTT = (1 - α) * EstimatedRTT + α * SampleRTT, α can be 0.125;

   • DevRTT = (1 - β) * DevRTT + β *

     SampleRTT - EstimatedRTT

     , β can be 0.25;

   • TimeoutInterval = EstimatedRTT + 4 * DevRTT.
8. TCP fast retransmit: If sender receives 3 ACKs for same data (triple duplicate ACK), resend unacked segment with smallest seq # without waiting for the timeout.
9. TCP flow control: Receiver “advertises” free buffer space by including rwnd (free buffer space size).
10. TCP building a connection and closing a connection:
    • 
11. TCP congestion control:
    • MSS: Maximum segment size;
    • AIMD: Additive increase (increase cwnd by 1 MSS every RTT until loss); Multiplicative decrease (cut cwnd in half after loss);
    • Slow start: Initially cwnd = 1 MSS, double cwnd every RTT until first loss event;
    • TCP Reno & TCP Tahoe:
      • 
    • TCP is fair.
12. ECN (Explicit congestion notification): Two bits in IP header marked by router to indicate congestion.

Chapter 4

1. Data plane & control plane:
   • Data plane: Per-router function, forwarding function;
   • Control plane: Network-wide logic, two approaches:
     • Traditional routing algorithms: Implemented in routers;
     • SDN (Software-defined networking): Implemented in (remote) server.
2. Destination-based forwarding is using longest prefix matching: Often preformed using TCAMs (ternary content addressable memories).
   • Content addressable: Present address to TCAM, retrieve address in one clock cycle, regardless of table size.
3. Switching fabrics: Memory, bus, crossbar.
4. HOL (Head-of-the-Line) blocking.
5. Input buffer overflow and output port buffer overflow can both lead to queueing delay and loss.
6. IP datagram format:
   • 
7. Network links have MTU (max transfer size), so large IP datagram divided into smaller (fragmented) datagrams and “reassembled” only at final destination.
8. One IP address (32-bit) per interface.
9. Subnet: Device interfaces with same subnet part of IP address, can physically reach each other without intervening router. Isolated islands when you remove the routers.
10. CIDR (Classless InterDomain Routing): a.b.c.d/x.
11. DHCP (Dynamic Host Configuration Protocol): Dynamically get address from a server:
    • Host broadcasts “DHCP discover” (optional);
    • DHCP server responds with “DHCP offer” (optional);
    • Host requests IP address: “DHCP request”;
    • DHCP server sends address: “DHCP ack”;
    • DHCP can return more than just allocated IP address:
      • First-hop router;
      • Name and IP of DNS server;
      • Network mask.
12. NAT (Network address translation): All datagrams leaving local network have same single source NAT IP address, but different source port number.
13. IPv6 datagram format:
    • Fixed-length 40 byte header & no fragmentation allowed;
    • 
    • Tunneling: IPv6 datagram carried as payload in IPv4 datagram among IPv4 routers.
14. OpenFlow: Match + action to unify different kinds of devices (router, switch, firewall, NAT). Examples:
    • 

Chapter 5

1. Dijkstra’s algorithm:
   • A link-state routing algorithm;
   • https://ranthot.cn/2018/10/09/%E7%AE%97%E6%B3%95%E6%9C%9F%E4%B8%AD%E5%A4%8D%E4%B9%A0%E7%AC%94%E8%AE%B0.html;
   • Oscillations possible.
2. Bellman-Ford algorithm:
   • Distance vector algorithm;
   • Each node sends its own distance vector estimate to neighbors, when x receives new DV, it updates its own DV using B-F:
     • D_x(y) = min_v{c(x, v) + D_v(y)}.
   • Iterative, asynchronous, distributed;
   • Count to infinity problem & poisoned reverse & split horizon: https://www.geeksforgeeks.org/route-poisoning-and-count-to-infinity-problem-in-routing/.
3. Scalable routing:
   • AS (Autonomous system).
   • Intra-AS routing, also known as IGP (Interior gateway protocols):
     • RIP (Routing Information Protocol);
     • OSPF (Open Shortest Path First, IS-IS (Intermediate System to Intermediate System) is essentially same as OSPF):
       • Using link-state algorithm (Dijkstra’s algorithm) over IP;
       • Support security, can have multiple same-cost paths, support both uni- and multi-cast, can be hierarchical.
     • IGRP (Interior Gatewat Routing Protocol).
   • Inter-AS routing:
     • BGP (Border Gateway Protocol):
       • eBGP: Obtain subnet reachability information from neighboring ASes;
       • iBGP: Propagate reachability information to all AS-internal routers;
       • Exchange over TCP connection;
       • Hot potatp routing: Choose local gateway with least cost, don’t worry about inter-domain cost.
   • Intra-AS can focus on performance, while for inter-AS, policy may dominate over performance.
4. Problems with traditional routing algorithms: Can’t manipulate routes, do load balancing. But SDN can achieve that.
5. ICMP: Internet control message protocol:
   • Network-layer “above” IP: ICMP carried in IP datagrams;
   • Used to report errors (unreachable host), echo request/reply (ping).
6. SNMP (Simple network management protocol), MIB (Management Information Base).

Chapter 6

1. Link layer implemented in “adaptor” (network interface card NIC) or on a chip.
2. Cyclic redundancy check:
   • Let D be the data, G be r+1 bits generator, R be r CRC bits;
   • R = remainder(D * 2^r / G);
   • Can detect all burst errors less than r+1 bits.
3. MAC protocols:
   • Channel parititioning:
     • TDMA: Time division multiple access;
     • FDMA: Frequency division multiple access;
   • Random access protocols:
     • Slotted ALOHA: If collison, retransmit frame in subsequent slot with probility p until success. Efficiency: 37%;
     • ALOHA: Similiar to slotted ALOHA, but no slots. Efficiency: 18%;
     • CSMA (Carrier sense multiple access):
       • If channel sensed idle: transmit. Collisions can still occur due to delay;
       • CSMA/CD: Collisions detected within short time and aborted; Binary (exponential) backoff after collision.
   • Taking turns: Polling from central site, token passing.
4. MAC address (48 bits).
   • ARP (Address resolution protocol): A wants to send datagram to B, A broadcasts ARP query, B receives it and reply to A with its MAC address, A caches IP-MAC pair.
5. Ethernet: “Dominant” wired LAN technology.
   • Physical topology: bus, star.
6. Switch:
   • Maintain a self-learned switch table;

   • if entry found for dest:
         if dest from which frame arrived:
             drop
         else:
             forward frame
     else:
         flood
     

7. VLAN (Virtual Local Area Network): Multiple virtual LANs over single LAN infrastructure.
8. Multiprotocol label switching (MPLS): High-speed IP forwarding using fixed length label (instead of IP address), using information of both src and dest.