How a web search works

  • Traffic pattern
    • Scatter-gather
    • Partition aggregate
  • Implications for networking
    • Data center internal traffic is BIG
    • Tight deadlines for network I/O
    • Congestion and TCP incast
      • TCP incast: when a large number of hosts/flows try to share the same buffer, they overwhelm the buffer and network throughput drops, then latency increases.
    • Need for isolation across applications
    • Centralized control at the flow level maybe difficult
      • Flows are short, not persistent



How hosts find each other on a subnet

  • ARP: Address Resolution Protocol(from IP to Mac Address on the LAN)

How subnets are interconnected


  • The simplest way a LAN can be connected with
  • They don't even exist in networks anymore today
  • A switch for essentially for the same price
  • One creates a broadcust medium among all the connected hosts
    • Flooding when sending packets
    • Collision, additional latency
    • Failure, misconfiguration
    • unwanted traffic

Learning switches

  • perform some amounts of traffic isolation
  • If no entry in forwarding table => Flood the frame on all its output ports
  • Do not eliminate all forms of flooding
  • Spanning tree to avoid looping

Switches and routers(strike a balance: SDN)

  • Switches operate at layer 2(common protocol: Ethernet), more convenient, Routers at 3(common protocol: IP)
  • Switches limitation is broadcast for spanning tree and ARP queries impose high load
  • Routers level are not restricted to spanning tree, one can have multipath routing(packets sent)
  • Switches are automaticly configuring, forwarding fast


  • Architecture

    • Interactive traffic
    • Delayed feedback about congestion
graph LR
S(Source) --> R[Router]
R --> |C|D(Destination)
R --> |bottleneck|D
B(Buffer: 2T*C) --> R
S -->|2T|D
  • Example
    • TCP sender sending packets(rate controlled by window W)
      • additive increase
      • multiplicative decrease
      • AIMD
      • congestion control



  • Actually a collection of tens of independently operated network or autonomous systems(AS's)

  • Type

    • Intradomain routing(inside any single autonomous system)
      • Distance vector
        • RIP(Routing Information Protocol)
      • Link state
    • Interdomain routing(between ****)
  • Scale

    • Gateway Protocol
      • EBGP(External Border Gateway Protocol)
        • Interdomain: Border Gateway Protocol
          • Prefer high "local preference"
          • Shortest AS path length
          • Multi-Exit Discriminator(MED)
            • Lower value
            • Only Comparable among routers from same AS
          • Shortest IGP path
            • Called "hot potato routing"
          • Tiebreak -> "most stable", lowest router ID
      • IBGP(Internal Border Gateway Protocol): routes inside an AS to external destinations
      • IGP(Inter-domain Gateway Protocol): routes inside an AS to internal destinations(IBGP next hop is a next hop IP Address that is reachable via IGP)
    • OSPF(Open Shortest Path Protocol): A routing protocol for Internet Protocol network, using link state routing algorithm
      • Notion: areas, in the backbone network, the network'routers may be divided into levels or areas, the global backbone area is area 0
      • Shortest path inside and among zero routers:
graph LR
subgraph Area1
A1-->|shortest| B1
B1-->|shortest| C1
C1-->|shortest| A1
subgraph Area2
A2-->|shortest| B2
B2-->|shortest| C2
C2-->|shortest| A2
subgraph Area3
A3-->|shortest| B3
B3-->|shortest| C3
C3-->|shortest| A3
zeroRouter1-->|shortest| zeroRouter2
zeroRouter2-->|shortest| zeroRouter3
zeroRouter3-->|shortest| zeroRouter1

Written with StackEdit.