Welcome

This notebook contains my personal notes for CS6250: Computer Networks, offered at the Georgia Institute of Technology. A summary of the course follows:

This project-based course will explore research topics in computer networking, primarily at the IP layer and above. Students will gain exposure to burgeoning areas of computer networking and learn how to use the tools commonly used for networking research, today.

Course links

Lesson 1

The following are questions and answers from the Exam 1 Study Guide for Lesson 1:

  • What are advantages and disadvantages of a layered architecture?

    • Layered architectures provide the following advantages:

      • Scalability
      • Modularity
      • Flexibility

    • Layered architectures provide the following disadvantages:

      • Some layers' functionality depends on the information from other layers, violating the goals of separation.
      • One layer may duplicate lower layer functionalities. For example, error recovery occurring in multiple layers.
      • Additional overhead is incurred by the abstraction necessary between layers.

  • What are the differences and similarities of the OSI model and five-layered Internet model?

    • The OSI model and the Five-layered Internet model contain the following similarities:

      • Physical Layer
      • Data Link Layer
      • Network Layer
      • Transport Layer

    • The OSI model and the Five-layered Internet model are different in that the Five-layered Internet model condenses the Application Layer, Presentation Layer, and the Session Layer into the Application Layer.

  • What are sockets?

    • The interface between the application layer and the transport layer.

  • Describe each layer of the OSI model

    • Application Layer

      • Includes multiple protocols:
        • HTTP
        • SMTP
        • FTP
        • DNS
      • This layer offers multiple services depending upon the applications' implementations. Each major application is tied to a protocol. At this layer, packets of information are referred to as messages.

    • Presentation Layer

      • Plays the intermediate role of formatting the information that it receives from the layer below and delivers it to the Application layer.

    • Session Layer

      • Layer responsible for managing different transport streams that belong to session between end-user applications.

    • Transport Layer

      • Responsible for end-to-end communication between end-point hosts. This layer implements two transport protocols, TCP and UDP.
      • Packets of information at this layer are referred to as segments.

    • Network Layer

      • Responsible for moving datagrams from one Internet host to another. This layer implements the IP protocol, defining the structure of datagrams, how datagram information is processed, and routing protocols used to determine routes between hosts.
      • Packets of information at this layer are referred to as datagrams.

    • Data Link Layer

      • This layer is responsible for moving frames from one node to the next, after receiving the Network Layer's datagram. This layer offers services across the link between two nodes (e.g. reliable delivery).
        • Example protocols implemented at this layer are:
        • Ethernet
        • Point to Point Protocol (PPP)
        • IEEE 802.11
      • Packets of information at this layer are referred to as frames.

    • Physical Layer

      • This layer facilitates the interaction with the actual hardware and is responsible for transferring bits of a frame between two nodes connected through a physical link.
      • Main protocols include:
        • Twisted-pair copper wire
        • Coaxial
        • Single-mode fiber optics

  • What is encapsulation, and how is it used in a layered model?

    • Encapsulation

      • At each layer the message is a combination of two parts:
        • The payload which is the message from the layer above
        • The new appended header information

    • De-encapsulation

      • At the receiving end, the process is reversed, with headers being stripped off at each layer.

  • What is the end-to-end (e2e) principle?

    • The e2e principle suggests that specific application-level functions usually cannot, and preferably should not be built into the lower levels of the system at the core of the network.

  • What are the examples of a violation of e2e principle?

    • Violations of the e2e principle typically refer to scenarios where it is not possible to implement a functionality entirely at the end hosts, such as NAT and firewalls.

  • What is the EvoArch model?

    • A research model that can help to study layered architectures and their evolution in a quantitative manner. Through this model researchers were able to explain how the hierarchical structure of the layer architecture eventually lead to the hourglass shape.

  • Explain a round in the EvoArch model

    • Introduce new nodes and place them randomly at layers
    • Examine all layers from top to bottom and perform:
      • Connect new nodes at each layer by choosing substrates (lower layer node) based on the generality probabilities of the layer below and choosing products (higher layer) based on the generality probability of the current layer
      • Update the value of each node at this layer
      • Examine all nodes in order of decreasing value in the layer and remove nodes that should die
    • Stop when we reach a given number of nodes

  • What are the ramifications of the hourglass shape of the internet?

    • Many technologies that were not originally designed for the internet have been modified so that they have versions that can communicate over the internet (such as Radio over IP).
    • It has been a difficult and slow process to transition to IPv6, despite the shortage of public IPv4 addresses.

  • Repeaters, hubs, bridges, routers operate on which layers?

    • Repeaters and hubs operate on Layer 1 (Physical layer).
    • Bridges operate on Layer 2 (Data-link layer).
    • Routers operate on Layer 3 (Network layer)

  • What is a bridge, and how does it “learn”?

    • A device with multiple inputs/outputs that transfers frames from an input to one or multiple outputs. It learns from each frame it receives by populating a forwarding table so that it forwards frames on specific ports instead of broadcasting everywhere.

  • What is a distributed algorithm?

    • Direct nodes send information to one another, and then they resend their results back after performing their own calculations, so the calculations are not happening in a centralized manner.

  • Explain the Spanning Tree Algorithm

    • Runs in rounds. Each node first thinks it is the root. Each node sends a configuration message with the sending node’s ID, root as perceived by this node, and number of hops from this node to its root. When a node receives a message, it updates its root if it finds a lower ID root, better path to the root, or equal path to the root if the sender of the message has a lower ID.

  • What is the purpose of the Spanning Tree Algorithm?

    • Prevent forwarding loops by excluding links that lead to loops (i.e. helps to prevent broadcast storms).

Lesson 2

The following are questions and answers from the Exam 1 Study Guide for Lesson 2:

  • What does the Transport Layer provide?

    • The Transport Layer provides an end-to-end connection between two applications that are running on different hosts, regardless if the hosts are in the same network.

  • What is a packet for the Transport Layer called?

    • Packets at the Transport Layer are called segments.

  • What are the two main protocols within the Transport Layer?

    • The two main protocols within the Transport Layer are:
      • Transmission Control Protocol (TCP)
      • User Datagram Protocol (UDP)

  • What is multiplexing, and why is it necessary?

    • The Transport Layer utilizes ports to implement multiplexing, allowing hosts to utilize the network for multiple applications. Multiplexing allows multiple streams of information to exist on the same network, and the division of the streams to different applications at the endpoint is achieved using ports.

  • Describe the two types of multiplexing/demultiplexing

    • The two types of multiplexing / demultiplexing are connectionless and connection-oriented:
      • connectionless multiplexing / demultiplexing uses UDP and only requires the destination IP address and destination port.
      • connection-oriented multiplexing / demultiplexing uses TCP and requires the source IP address, source port, destination IP address and destination port.

  • What are the differences between UDP and TCP?

    • TCP provides end-to-end communication and reliability.
    • UDP offers no congestion control or similar mechanisms and no connection management overhead. The Application Layer must implement these features, if necessary.

  • When would an application layer protocol choose UDP over TCP?

    • UDP is useful for real-time applications that are sensitive to delays. The following are some applications / protocols that utilize UDP:
      • Remote file servers
      • Streaming multimedia
      • Internet telephony / VOIP
      • Network management
      • Routing protocols (e.g. RIP)
      • Name translation (i.e. DNS)

  • Explain the TCP Three-way Handshake

    • The TCP three-way handshake is the TCP protocol's method of initiating a connection with a host. TCP segments contain flags that are used to send TCP specific messages related to the protocol. For the three-way handshake, the flags SYN and ACK are used. The host initiating the connection begins by sending the remote host a SYN TCP message. The remote host responds with a SYN, ACK TCP message. Finally, the initiating host responds with an ACK TCP message, establishing the session - from there the Application Layer takes over to utilize the session for TCP-centric applications.

    • The initial SYN TCP message and the SYN, ACK message from the server both contain a random sequence number. Each number will be incremented by 1 each time the two hosts communicate using TCP.

  • Explain the TCP connection tear down

    • When the client is ready to close the connection, it sends a FIN TCP segment to the server. The server responds with an ACK TCP segment. When the server has completed its destruction of the TCP connection, it sends a FIN TCP segment to the client, and the client responds with ACK.

  • What is Automatic Repeat Request or ARQ?

    • TCP segments contain a segment number, allowing both hosts to know which segments were sent or received. Using TCP, hosts can acknowledge that they receive specific segments, allowing sending hosts to know if the receiver received all of the segments or if the receiver missed specific segments. If a specific segment is not acknowledged by the receiver, the sender can assume the segment didn't reach the receiver - after a timeout it will resend the segment. This is ARQ.

  • What is Stop and Wait ARQ?

    • This is what I described in the previous paragraph - sending and receiving with a timeout for acknowledged segments.

  • What is Go-back-N?

    • A modification of Stop and Wait ARQ that is more performant. Essentially, the receiver only acknowledges the most recently received, in order segment. So if the sender sends 10 segments, and the receiver acknowledges segment 7, then the receiver knows that maybe 8, 9, or 10 were either received out of order or lost entirely. Thus, the sender will resend the entire window of 1-10 segments. The receiver will disregard 1-7 because it already has them, but will hopefully acknowledge segment 10, meaning it got the entire window of segments.

  • What is selective ACKing?

    • This is another mutation of the above protocols, however, the receiver can now receive segments out of order. The sender can now know that some segments were dropped or corrupted on their trip to the receiver. Once the entire window is received by the receiver, it will place the segments back into the correct order and proceed to the Application Layer.

  • What is fast retransmit?

    • This occurs when the receiver is encountering duplicate acknowledgements for segments that have already been acknowledged by the receiver. The sender will resend the segment experiencing duplicate acknowledgements.

  • What is transmission control and why do we need to control it?

    • Transmission control is used to control how much data is sent over a link by applications in used by each host on the network. Transmission control implements fairness on the network and congestion control for Layer 3 devices that provide connectivity.

  • What is flow control and why do we need to control it?

    • Flow control controls the transmission rate to protect a receiving host's network buffer from overflowing with information. It's possible that a receiving host is involved with multiple processes and does not read data from its network buffer instantly. This could cause an accumulation of data that overflows its buffer.

  • What is congestion control?

    • While Flow control is concerned about one specific host, Congestion Control is concerned with protecting the entire network from congestion. Given multiple devices using the same link, Congestion Control aims to avoid the link reaching max capacity, thus causing dropped packets and retransmissions.

  • What are the goals of the congestion control?

    • The goals of congestion control are as follows:
      • Efficiency - high throughput and network utilization.
      • Fairness - every host should get a fair share of the network bandwidth.
      • Low delay
      • Fast convergence - network flow should be able to quickly converge to fair allocation.

  • What is network-assisted congestion control?

    • Network-assisted congestion control involves Layer 3 devices providing feedback to hosts on the congestion of the network. This is usually implemented by sending diagnostic ICMP messages.

  • What is end-to-end congestion control?

    • The network does not provide any feedback to hosts about the congestion of the network to end points. Hosts must infer network behavior and adapt their transmission rate.

  • How does a host infer congestion?

    • Two methods, both implemented via TCP:
      • Round trip delay - time based inference of network congestion. Difficult to implement because round trip time varies wildly.
      • Packet loss - the TCP messages that have to be re-sent, the more we can infer that network congestion exists. This was the first method of network congestion implemented in TCP.

  • How does a TCP sender limit the sending rate?

    • TCP uses a congestion window, similar to the receive window for flow control by receiving hosts. TCP probes and adapts the congestion window, increasing to try and achieve the highest through, and decreasing when enough segments are dropped.

  • Explain Additive Increase/Multiplicative Decrease (AIMD) in the context of TCP

    • TCP uses addition to increase the number of packets sent in the congestion window when the network is not experiencing congestion. Once congestion is detected, the window is decreased by some multiplicative value, generating a sawtooth pattern of traffic over time.

  • What is a slow start in TCP?

    • Instead of using addition to establish the initial size of the congestion window, TCP will exponentially increase the congestion window until congestion is experienced.

  • Is TCP fair in the case two where connections have the same RTT? Explain

    • Yes as both will increase and decrease window sizes as needed to balance.

  • Is TCP fair in the case where two connections have different RTTs? Explain

    • No, a shorter RTT would increase the window faster.

  • Explain how TCP CUBIC works

    • TCP CUBIC uses a cubic function for the calculation of its congestion window. When TCP CUBIC detects congestions, it exercises a multiplicative decrease on its congestion window. Afterwards, it greatly increases its congestion window and plateaus until no congestion is detected. It then increases the congestion window again.

  • Explain TCP throughput calculation

    • Bandwidth (BW) is bound by ((Data and Time per Cycle Calculation) / (Round Trip Time (RTT))) * 1 / sqrt(Probability of Packet Loss)

Lesson 3

The following are questions and answers from the Exam 1 Study Guide for Lesson 3:

  • What is the difference between the forwarding and routing?

    • Forwarding - refers to transferring a packet from an incoming link to an outgoing link within a single router.
    • Routing - refers to how routers work together using routing protocols to determine the good paths (or good routes as we call them) over which the packets travel from the source to the destination node.

  • What is the main idea behind a link state routing algorithm?

    • In a link state routing algorithm / protocol, link costs and the network topology are known to all nodes.
    • Based upon Djikstra's algorithm.
    • Start with N’ just containing the source node. Initialize all paths to infinity except directly attached nodes. Perform iterations and update whenever we find lower costs until every node is examined and added to N’.

  • What is an example of a link state routing algorithm?

    • Open Shortest Path First (OSPF)

  • Walk through an example of the link state routing algorithm

    • At each iteration, look among nodes not yet in N’, select the node with least cost from the previous iteration. Update distance for all immediate neighbors of this node using the lowest cost paths.

  • What is the computational complexity of the link state routing algorithm?

    • O(n^2)

  • What is the main idea behind distance vector routing algorithm?

    • Based upon the Bellman-Ford algorithm.
    • Iterative (continues until no more updates)
    • Asynchronous (nodes do not have to be synchronized with each other)
    • Distributed (no need to know network topology or have some central point of calculation)

  • Walk through an example of the distance vector algorithm

    • Each node maintains its own distance vector with costs to reach every other node in the network. They send each other their distance vectors and update accordingly if there are shorter paths found between what was already in its distance vector and newly received information.

  • When does count-to-infinity problem occur in the distance vector algorithm?

    • When a large change occurs across a link, causing an infinite number of updates to be propagated across nodes. This can continue to happen until the nodes' tables eventually converge. This can happen if nodes have large positive or negative numbers.

  • How does poison reverse solve the count-to-infinity problem?

    • When one node knows there is a path through another node, it will poison the opposite path so it is never taken. When bad news comes, it will take the opposite path and pass on this information so the new path is quickly used and the previous path becomes poisoned. This solves the problem with 2 nodes but is not guaranteed to work for 3 or more nodes that are not directly connected.

  • What is the Routing Information Protocol (RIP)?

    • Based on the Distance Vector protocol and uses hop count as the metric (each link = 1 cost). Uses RIP response message instead of distance vectors. Each node maintains a RIP Table (Routing Table), which will have one row for each subnet in the AS. Uses UDP.

  • What is the Open Shortest Path First (OSPF) protocol?

    • A routing protocol that uses the link-state routing algorithm to find the best path between source and destination router. Advancement of RIP. Uses flooding of link-state info and Dijkstra. Advances include authentication of messages, option to use multiple same cost paths, and support for hierarchy within a single routing domain.

  • How does a router process advertisements?

    • The router checks if advertisement is new or duplicate by referring to the link-state database. If its new, it updates this database and runs OSPF based on current topology. It floods the LS update and updates FIB.

  • What is hot potato routing?

    • When there are equally good egress points (network exits) - choose the one that is the shortest (closest) path cost away.

Lesson 4

The following are questions and answers from the Exam 1 Study Guide for Lesson 4:

  • Describe the relationships between ISPs, IXPs, and CDNs

    • ISPs (Internet Service Providers) are the “backbone” network over which smaller networks can connect. IXPs (Internet Exchange Points) are physical interconnection infrastructures that are used by multiple networks (such as ISPs and Content Distribution Networks (CDNs)) to interconnect.

    • CDNs are networks created by content providers (such as Shopify/Netflix) to reduce connectivity costs and provide greater control for the content provider on how the content is delivered to the end-users. They may have multiple data centers with hundreds of servers distributed across the world.

  • What is an AS?

    • Autonomous System (AS) - a group of routers that operate under the same administrative authority. An ISP (or CDN) can operate as a single AS or multiple. Each AS has its own set of policies/strategies based on their needs and doesn’t need to share this info with other ASes.

  • What kind of relationship does AS have with other parties?

    • Competition and cooperation. T1 ISPs compete with each other, T2 with each other, etc - there is a hierarchy but this hierarchy is becoming more flat over time thanks to evolutions such as IXPs and CDNs. Competing ISPs also need to cooperate so that the Internet can work on a global scale.

  • What is BGP?

    • For traffic to go between ASes, BGP (Border Gateway Protocol) is used which is primarily based on incentives (money) - ASes do whatever makes the most sense for them from a financial standpoint.

  • How does an AS determine what rules to import/export?

    • It's entirely a business decision for both importing and exporting routes. ASes are incentivized to advertise customer routes, peer routes none, and provider routes none. For importing routes from other ASes, ASes are incentivized to import customer routes most, peer routes less, and provider routes none.

  • What are were original the design goals of BGP? What was considered later?

    • The original design goals were:

      • Scalability - quick convergence and loop-free pathing

      • Express routing policies - allow ASes to implement policies, filter and rank routes, and keep these decisions confidential

      • Allowing cooperation among ASes - allows ASes to make local decisions while keeping these decisions confidential from other ASes

      • Security was not originally considered when implementing BGP, requiring security measures to be added later as the Internet grew in size and complexity.

  • What are the basics of BGP?

    • A pair of routers, BGP peers, exchange routing info over a semi-permanent TCP port connection (BGP session). This starts with an OPEN message and is followed by the routers sending each other announcements from their own routing tables.

    • There are two types of BGP messages:

      • UPDATE - announcements of new routes/updates to existing routes; withdrawal of previous routes due to a failure or change in routing policy
      • KEEPALIVE - message exchanged to keep a current session going

    • BGP routes - main components: reachable IP prefix field, AS-PATH (route passed through from destination), and NEXT-HOP (IP of next-hop router along the path towards the destination). In iBGP the NEXT-HOP is the address of the nearest border router.

  • What is the difference between iBGP and eBGP?

    • eBGP - external BGP; BGP session between pair of routers in two different ASes
    • iBGP - internal BGP; BGP session between routers in the same AS

  • What is the difference between iBGP and IGP-like protocols (RIP or OSPF)?

    • iBGP is used to propagate information about what ASes can be reached by the gateway routers in the current AS. IGP-like protocols are used to establish paths between the internal routers of an AS based on specific costs within the AS.

  • How does a router use the BGP decision process to choose which routes to import?

    • The actual policies are based on the business goals of the AS, but they all follow the same process to select the best routes based on the policy in place. The router compares a list of attributes, between a pair of routes, in top down order - if two attributes are equal then it moves down to the next attribute and so on.
    • LocalPref is at the top and set by the local AS’ administrator based on business relationships/preference of specific AS. Higher number = higher preference. Controls which routers are used as exit points (outgoing traffic).
    • MED (Multi-Exit Discriminator) is another important attribute and is set by the neighboring ASes. Lower MED value = higher preference. A neighboring AS with multiple links can tag routes with MED values to indicate which routers are used as entry points (which links are preferred for inbound traffic).
    • LocalPref = outbound; MED = inbound

  • What are 2 main challenges with BGP? Why?

    • Scalability and misconfigurations or faults. An error can result in an excessively large number of updates which can lead to route instability, overloading, outages, etc.
    • ASes can reduce this risk by limiting routing table size with filtering to encourage route aggregation and limiting the number of route changes with flap damping (suppresses route updates for a period of time when a threshold is reached which can be set individually for prefixes according to a specific strategy).

  • What is an IXP?

    • Internet Exchange Points - physical infrastructures that provide the means for ASes to interconnect and directly exchange traffic with one another.

  • What are four reasons for IXPs increased popularity?

    1. They can handle large traffic volumes comparable to T1 ISPs
    2. Play an important role in mitigating DDoS attacks as they can play the role of a “shield” such as with BGP blackholing
    3. Provide a plethora of research opportunities into the evolution of the Internet landscape
    4. Active marketplaces with many services beyond interconnection - they have been evolving from simple interconnection hubs to technology innovation hubs
    • Keeps traffic local when both on the same IXP, lower costs, incentives from big players.

  • Which services do IXPs provide?

    1. Public peering
    2. Private peering (separate from public)
    3. Route servers and service level agreements (many participants on a network can use it with a single agreement/BGP session)
    4. Remote peering through resellers (third parties can resell their connection to IXP to networks that use less traffic/in distant area)
    5. Mobile peering
    6. DDoS blackholing (customer can trigger this to alleviate DDoS effects)
    7. Free value-added services such as nameservers, local time, DNS root name servers, etc.

  • How does a route server work?

    • Route servers help to make peering more manageable. In summary, a Route Server (RS):

      • Collects and shares routing information from its peers or participants that connects with (i.e. IXP members that connect to the RS).
      • Executes it’s own BGP decision process and also re-advertise the resulting information (I.e. best route selection) to all RS’s peer routers.

    • A typical routing daemon maintains a Routing Information Base (RIB) which contains all BGP paths that it receives from its peers - the Master RIB. The router server also maintains AS-specific RIBs to keep track of the individual BGP sessions they maintain with each participant AS.

    • RSes maintain two types of route filters:

      • Import filters are applied to ensure that each member AS only advertises routes that it should advertise
      • Export filters which are typically triggered by the IXP members themselves to restrict the set of other IXP member ASes that receive their routes.

Lesson 5

The following are questions and answers from the Exam 1 Study Guide for Lesson 5:

  • What are the basic components of a router?

    • Input/output ports, switching fabric, and the routing processor

  • Explain the forwarding (or switching) function of a router

    • The router’s action of transferring a packet from an input link interface to the appropriate output link interface. Forwarding takes place at very short timescales (typically a few nanoseconds), and is typically implemented in hardware.

  • The switching fabric moves the packets from input to output ports. What are the functionalities performed by the input and output ports?

    • Inside the forwarding data plane (hardware) we have three main components:
      • Input ports - first they physically terminate the incoming links to the router, then they decapsulate packets, and finally (most importantly) they perform the lookup function by consulting the forwarding table to forward the packet to the appropriate output port through the switching fabric
      • Switching fabric - moves packets from input to output ports
      • Output ports - receive and queue packets from the switching fabric and send them over to the outgoing link

  • What is the purpose of the router’s control plane?

    • Inside the control plane (software), we have the routing processor which implements the routing protocols, maintains the routing tables, and computes the forwarding tables.

  • What tasks occur in a router?

    • Lookup - router looks at destination IP and consults forwarding table (FIB) to determine output link using longest prefix matching algorithms
    • Switching - aka forwarding this is the most important task of a router where the router transfers the packet from the input link to the output link.
    • Queuing - after the packet has been switched to a specific output port, it needs to be queued if the link is congested
    • Header validation and checksum - router checks the packet’s version number, decreases time-to-live field, and recalculates the header checksum
    • Route processing - routing processor uses routing protocols (such as OSPF/RIP) to build the forwarding tables
    • Protocol processing - routers need to use some protocols to implement their functions including SNMP, TCP and UDP, and ICMP

  • List and briefly describe each type of switching. Which, if any, can send multiple packets across the fabric in parallel?

    1. Via memory - routing processor controls this method which involves the packet being copied to the processor’s memory, consulting the forwarding table, and copied the packet to the output’s port buffer. One packet at a time.
    2. Via bus - no routing processor involved - the input port puts an internal header which designates the output port and sends the packet to the shared bus. All output ports receive the packet but only the designated one keeps it. One packet at a time.
    3. Via interconnection network - crossbar switch used so that multiple packets can be carried at the same time as long as they are using different input and output ports.

  • What are two fundamental problems involving routers, and what causes these problems?

    1. Bandwidth and Internet population scaling - caused by the increasing number of devices that connect to the Internet, heavier traffic from new apps, new technologies such as optical links that can handle higher volumes of traffic.
    2. Services at high speeds - new apps may require new services such as protection against delays in presence of congestion and protection during attacks/failures. Offering these services at very high speeds is a challenge for routers.

  • What are the bottlenecks that routers face, and why do they occur?

    • Many bottlenecks including exact lookups, prefix lookups, packet classification, switching limitations, and security. Most are caused by scaling issues - the need for high speed and service guarantees.

  • What is CIDR, and why was it introduced?

    • Classless Internet Domain Routing - introduced to help with scaling as we ran out of IP addresses so it allows IP addresses of arbitrary-length prefixes. This helped decrease router table size but introduced the longest-matching-prefix lookup problem.

  • Name 4 takeaway observations around network traffic characteristics. Explain their consequences

    1. There are a large number of concurrent flows of short duration - therefore a caching solution would not work efficiently.
    2. Lookup speed is very important, a large part of the computational cost for lookup is in accessing memory.
    3. An unstable/inefficient routing protocol can lead to time increases
    4. Memory usage trade-off - either use fast, expensive memory (cache in software/SRAM) or cheaper but slower memory (DRAM)

  • Why do we need multibit tries?

    • Unibit tries require too many memory accesses while multibit tries solve this by using a stride. A stride is the number of bits that we check at each step.

  • What is prefix expansion, and why is it needed?

    • Expanding a given prefix to more prefixes so that we don’t miss out on any prefixes. Gives more speed with a cost of increased database size.

  • What are the benefits of variable-stride versus fixed-stride multibit tries?

    • More optimized - takes up less space in prefix database, less memory access, more flexible.

Lesson 6

The following are questions and answers from the Exam 1 Study Guide for Lesson 6:

  • Why is packet classification needed?

    • Packet classification is needed to accomplish quality of service guarantees and security guarantees that longest prefix matching based on destination IP alone cannot do. This allows handling packets based on other criteria such as TCP flags and source addresses.

  • What are three established variants of packet classification?

    1. Firewalls - filter out unwanted traffic and enforce other security policies
    2. Resource reservation protocols - used to reserve bandwidth between source and destination
    3. Routing based on traffic type - used to avoid delays for time-sensitive applications

  • What are the simple solutions to the packet classification problem?

    • Linear search - reasonable for a few rules (such as in a firewall) but otherwise inefficient.
    • Caching - cache the results so that future searches can run faster.
    • Passing labels - done in the header and typically at the edges which saves time.

  • How does fast searching using set-pruning tries work?

    • Build a trie on destination prefixes and then at every leaf-node we “hang” the source tries that are compatible (or whatever other dimension we are considering for packet classification). To match a prefix, we first traverse the destination trie and then the source trie while keeping track of the lowest-cost matching rule.

  • What’s the main problem with the set pruning tries?

    • Memory explosion - a source prefix can occur in multiple destination tries

  • What is the difference between the pruning approach and backtracking approach for packet classification with a trie?

    • Set pruning has a high cost in memory with a lower cost in time. Backtracking saves memory but costs more in time. Each rule is only stored once.

  • What’s the benefit of grid of tries approach?

    • It is a middle-ground approach that balances the memory and time costs by using precomputation with switch pointers. These are basically shortcuts.

  • Describe the “Take the Ticket” algorithm

    • Each output line maintains a distributed queue for all input lines that want to send packets to it. When an input line wants to send a packet to a specific output line, it requests a ticket. The input line waits for the ticket to be served. At that point, the input line connects to the output line, the crosspoint is turned on, and the input line sends the packet.

  • What is head-of-line problem?

    • The other lines are stuck in the line waiting for their turn - the entire queue is blocked by the progress of the head of the queue.

  • How to avoid head-of-line problem using knockout scheme?

    • Break up the packets into a fixed size (cell). Have the fabric running N times faster than the input links where k is the expected number of cells received by an output link. For cases where the expectation is violated, randomly pick the output that is chosen. Complex to implement.

  • How to avoid head-of-line problem using parallel iterative matching?

    • All inputs send requests in parallel to all outputs they want to connect with. This is the request phase. In the grant phase, the outputs randomly pick an input out of its requestors. In the accept phase, inputs randomly pick an output to send to. This way, all of the inputs are sending packets from the start.

  • Describe FIFO with tail drop

    • Packets are sent to the output ports. The output ports are FIFO and any packets that overflow the buffer (tail of the queue) are dropped. This results in fast scheduling decisions but loss of packets.

  • What are the reasons to make scheduling decisions more complex than FIFO?

    • To provide quality of service (QoS) guarantees on measures such as delay and bandwidth. To provide additional (router) support for congestion. To promote fair sharing of links among competing flows.

  • Describe Bit-by-bit round Robin scheduling

    • Gives bandwidth and delay guarantees. We calculate the packet finishing time for each packet and send the packet with the smallest finishing round number based on the previous round of the algorithm.

  • Bit-by-bit Round Robin provides fairness, what’s the problem with this method?

    • Requires introducing extra time complexities such as keeping track of the finishing time (requires priority queue). The extra complexities make it hard to implement at gigabit speeds.

  • Describe Deficit Round Robin (DRR)

    • Solves some of the time complexities of bit-by-bit round robin by using a deficit counter instead of performing all the calculations of finishing time. This ensures fairness.

  • What is a token bucket shaping?

    • Used for the scenarios where we want bandwidth guarantees for flows in the same queue without separating them. Limits the burstiness of a flow by limiting the average rate and limiting the maximum burst size. The technique assumes a bucket per flow that fills with tokens at a rate R per second with a max of B tokens. Additional tokens are dropped. When packets arrive, they can go through if there are enough tokens, otherwise it must wait for more tokens to fill the bucket.

  • In traffic scheduling, what is the difference between policing and shaping?

    • Policing is a modified version of token bucket shaping - when a packet arrives it needs to have tokens at the bucket already there. If the bucket is empty, the packet is dropped.

    • Policing - sawtooth wave pattern.

    • Shaper - keeps excess in a queue or buffer so traffic is delayed instead of dropped. Smooth/shaped curve instead of sawtooth.

  • How is a leaky bucket used for traffic policing and shaping?

    • Similar to a bucket with a hole - constant flow of network traffic out of the bucket where the bucket can be seen as the buffer, water represents packets, and the leak rate is the rate at which packets are allowed to enter the network. If the packet will not cause overflow to the bucket, the packet is added (conforming) to the bucket. Otherwise it is discarded (non-conforming).

    • Irrespective of the input rate of packets, the output rate is constant which leads to uniform distribution of packets sent to the network.

Lesson 7

The following are questions and answers from the Exam 2 Study Guide for Lesson 7:

  • What spurred the development of Software Defined Networking (SDN)?

    • SDN arose as part of the process to make computer networks more programmable . Due to a diversity of equipment and the requirement to handle different proprietary technologies from different vendors for different network devices, SDN works to redesign networks to make them more manageable.

  • What are the three phases in the history of SDN?

    1. Active networks
    2. Control and data plane separation
    3. OpenFlow API and network operating systems

  • Summarize each phase in the history of SDN.

    1. Packaging of code in network packets to create flows / QoS for different packet types. Most of this occurred at the edge of the network. Code was executed inside of Virtual Machines. Backbone network managers were not comfortable with arbitrary code execution by any developer on network nodes.

    2. Packet forwarding was implemented directly in the hardware. This era tailored to administrators being able to control / manage routing decisions. Emphasized programmability in the control domain rather than the data domain.

    3. The vision of fully programmable networks for research is realized, and then actually used by businesses / ISPs. Abstracted away the specifics of vendor software / proprietary products and allowed the entire network to be treated as one programmable entity. Lead to the rise of network operating systems and distributed state management.

  • What is the function of the control and data planes?

    • The control plane contains the logic that implements the forwarding behavior of routers such as routing protocols and network middlebox configurations.
    • The data plane performs the actual forwarding as dictated by the control plane.

  • Why separate the control from the data plane?

    • Independent evolution and development - prior to their separation, any changes to the control plane had to be met with upgrades to the hardware.
    • Control from high-level software programs - software computes the forwarding tables in SDN, allowing us to use high-order or more abstract programming languages to implement routing algorithms. This also makes debugging and checking the behavior of the network easier.

  • Why did the SDN lead to opportunities in various areas such as data centers, routing, enterprise networks, and research network?

    1. Data centers - SDN assists in the management of large data centers with thousands of servers and VMs.
    2. Routing - SDN has the capability to make routing decisions using multiple criteria, and can easily update a router's state for the implementation of BGP policies. This provides mre control over path selection.
    3. Enterprise networks - SDN improves security applications for enterprise networks. An example being dropping attack traffic at strategic locations within the network to mitigate the effects of a DDoS attack.
    4. Research networks - SDN enables research networks to coexist with production networks (they so easy to create and tear down).

  • What is the relationship between forwarding and routing?

    • In forwarding, the router inspects the packet coming in from a port, consults the routing table, and sends the packet to the output port dictated by the forwarding table. Forwarding is a function of the data plane.
    • In routing, routers use routing algorithms to generate the forwarding table, implementing policies and using these algorithms to determine the best path for traffic. Routing is a function of the control plane.

  • What is the difference between a traditional and SDN approach in terms of coupling of control and data plane?

    • In the traditional approach, the control and data planes are closely coupled. The router runs routing algorithms and generates the forwarding table . In the SDN approach, the remote controller computers and distributes forwarding tables. The controller is physically separated from the router.

  • What are the main components of SDN network and their responsibilities?

    • SND-controlled network elements - infrastructure layer, responsible for forwarding traffic using rules computed by the SDN control plane.
    • SDN controller - logically centralized entity that behaves as an interface between the network elements and the network-control applications.
    • Network-control applications - programs that manage the underlying network by collecting information about the network elements with the help of the SDN controller.

  • What are the four defining features in an SDN architecture?

    • Flow-base forwarding - rules for packets can be computed based on any number of header field values in various layers (transport, network, link).
    • Separation of data and control planes
    • Network control functions - controller maintains up-to-date network state information and provides it to the network-control applications. This enables network-control applications to monitor and control network devices.
    • Programmable network - enables the implementation of sophisticated routing applications to include network management, traffic engineering, security, automation, analytics, etc.

  • What are the three layers of SDN controller?

    • Communication layer - comms between the controller and the network elements
    • Network-wide state-management layer - stores information about the network state
    • Interface to the network-control application layer - communication between controller and network-control applications

Lesson 8

  • Describe the three perspectives of the SDN landscape.

    • A plane-oriented view (management, control, data)
    • The SDN layers
    • A system design perspective

  • Describe the responsibility of each layer in the SDN layer perspective.

    • Data plane - functions and processes that forward data in the form of packets or frames
    • Control plane - functions and processes that determine which path to use by using protocols to populate forwarding tables of data plane elements
    • Management plane - services that are used to monitor and configure the control functionality, e.g. SNMP-based tools

  • Describe a pipeline of flow tables in OpenFlow.

    • Flow tables have three parts: a matching rule, actions to be executed on matching packets, and counters that keep statistics of matching packets. When a packet arrives, the lookup process starts in the first table and ends with either a match in of the tables of the pipeline or with a miss.

  • What’s the main purpose of southbound interfaces?

    • The southbound interfaces or APIs are the separating medium between the control plan and the data plane functionality.

  • What are three information sources provided by OpenFlow protocol?

    1. Event-based messages that are sent by forwarding devices to the controller when there is a link or port change.
    2. Flow statistics are generated by forwarding devices and collected by the controller.
    3. Packet messages are sent by forwarding devices to controller when they do not know what to do with a new incoming flow.

  • What are the core functions of an SDN controller?

    • Topology, statistics, notifications, device management, and shortest path forwarding and security mechanisms.

  • What are the differences between centralized and distributed architectures of SDN controllers?

    • Centralized controller - a single entity that manages all forwarding devices in the network.
    • Distributed controller - a centralized cluster of nodes or a physically distributed set of elements.

  • When would a distributed controller be preferred to a centralized controller?

    • A distributed controller is useful if you're looking for scalability. Centralized controllers are unable to handle a large number of data plane elements.

  • Describe the purpose of each component of ONOS (Open Networking Operating System)

    • ONOS is a cluster-based distributed control-plane operating system. Several ONOS instances run within one cluster, with one being a master, and they all acquire a global network view using the statistics generated by the OpenFlow manager. The ONOS clusters generate a global view and send updates based upon the set policy to the OpenFlow managers - which then act upon the new instructions. Due to its clustered, distributed nature, ONOS is able to achieve fault tolerance and scale-out performance.

  • How does ONOS achieve fault tolerance?

    • A master node is elected for each cluster. Upon the failure of a master node, a new master for the cluster is elected. The work of a failed instance is redistributed to other ONOS nodes in the cluster.

  • What is P4?

    • A high-level programming language to configure switches which works in conjunction with SDN control protocols.

  • What are the primary goals of P4?

    • Reconfigurability - switch packet processing should be modifiable by the controller
    • Protocol independence
    • Target independence - packet processing programs should be programmed independent of the underlying target device, programs written in P4 should be converted into target-dependent programs by a compiler

  • What are the two main operations of P4 forwarding model?

    • Configure - programming of the parser, specify header fields to be processed in each stage of packet processing
    • Populate - allows addition / deletion of the entries in the tables, decides the policies to be applied to matching packets

  • What are the applications of SDN? Provide examples of each application.

    • Traffic engineering - optimize traffic flow to minimize power consumption
    • Mobility and wireless - provides an abstraction layer, decoupling wireless protocols from the management of the data plane entities
    • Measurement and monitoring - enables systems to respond to changes in network conditions
    • Security and dependability - impose security policies on entry points into the network
    • Data center networking - live network migration, troubleshooting, real-time monitoring

  • Which BGP limitations can be addressed by using SDN?

    • Routing using only destination IP prefix
    • Networks have little control over end-to-end paths

  • What’s the purpose of SDX?

    • Application-specific peering
    • Traffic engineering
    • Traffic load balancing
    • Traffic redirection through middleboxes

  • Describe the SDX architecture.

    • SDX virtualized the BGP route server architecture used in traditional internet exchange points. Each autonomous system has the illusion that it has its own virtual SDN switch connecting its border router to every other participant autonomous system.

  • What are the applications of SDX in the domain of wide area traffic delivery?

    • Application specific peering
    • Inbound traffic engineering
    • Wide-are server load balancing
    • Redirection through middle boxes

Lesson 9

  • What are the properties of secure communication?

    • Confidentiality
    • Integrity
    • Authentication
    • Availability

  • How does Round Robin DNS (RRDNS) work?

    • Responding to a DNS request with a list of DNS A records, cycling through records each time.

  • How does DNS-based content delivery work?

    • When a lookup is conducted for a resource / content, the delivery network will determine the best CDN server to service the request and use DNS to point the client to the right IP address.

  • How do Fast-Flux Service Networks work?

    • Based on a rapid change in DNS answers, with a TTL lower than that of RRDNS and CDN. This is done in order to prevent spammers for injecting bad IP addresses into the DNS resolution lifecycle

  • What are the main data sources to identify hosts that likely belong to rogue networks, used by FIRE (FInding Rogue nEtworks system)?

    • Botnet command and control providers
    • Drive-by-download hosting providers
    • Phish housing providers

  • The design of ASwatch is based on monitoring global BGP routing activity to learn the control plane behavior of a network. Describe 2 phases of this system.

    1. Training phase - ASwatch learns the control-plane behavior of a normal AS and a malicious one and learns to differentiate between them.
    2. Operational phase - ASwatch takes an unknown AS and calculates the features for it, assigning it a reputation score.

  • What are 3 classes of features used to determine the likelihood of a security breach within an organization?

    • Rewiring activity - changes in the AS connecting activity, multiple changes in providers / customers looks suspicious
    • IP Space Fragmentation and Churn - inspects advertised prefixes of an autonomous system. Malicious ASes are likely to use small BGP prefixes to partition their IP address space and only exposes a small section of them
    • BGP Routing Dynamics - tracks announcements and withdrawals, which usually follow different patterns for malicious ASes

  • (BGP hijacking) What is the classification by affected prefix?

    • This classification is primarily concerned with the IP prefixes that are advertised by BGP. There are different ways the prefix can be targeted:
      • Exact prefix hijacking
      • Sub-prefix hijacking
      • Squatting

  • (BGP hijacking) What is the classification by AS-Path announcement?

    • An illegitimate autonomous system announces the AS path for a prefix for which it doesn't have ownership rights.
      • Type-0 hijack - AS announcing a prefix not owned by itself
      • Type-N hijack - counterfeit AS announces an illegitimate path for a prefix that it does not own or create a fake path between different ASes
      • Type-U hijack - the hijacking AS does not modify the AS-PATH but may change the prefix

  • (BGP hijacking) What is the classification by data plane traffic manipulation?

    • In this classification of attacks, the attacker attempts to hijack the network traffic and manipulate the redirected network traffic on its way to the receiving AS. Traffic intercepted can be:
      • Dropped (blackholing)
      • Man-in-the-middle
      • Impersonation

  • What are the causes or motivations behind BGP attacks?

    • Human error - misconfiguration / accidents
    • Targeted attack - intentional interception of network traffic (man-in-the-middle) (stealthy)
    • High impact attack - obvious attempt to cause widespread disruption

  • Explain the scenario of prefix hijacking.

    • Malicious autonomous system router advertises a prefix that it doesn't own, taking advantage of its shorter distance to have peer / customer routers change their path for the prefix to the malicious autonomous system.

  • Explain the scenario of hijacking a path.

    • Malicious autonomous system receives a path and alters it, placing itself as the best path to reach a specific autonomous system / prefix. This path will likely be shorter than the original, causing other ASes to use the new hijacked path.

  • What are the key ideas behind ARTEMIS?

    • A configuration file where all prefixes owned by the network are listed for reference.
    • A mechanism for receiving BGP updates, allows the system to receive updates from local routers and monitoring services

  • What are the two automated techniques used by ARTEMIS to protect against BGP hijacking?

    • Prefix deaggregation - announcing more specific prefixes in order to mitigate prefix hijacking
    • Mitigation with multiple origin AS (MOAS) - third party organizations and service providers do BGP announcements for a given network

  • What are two findings from ARTEMIS?

    1. Outsource the task of BGP announcements to third parties
    2. Filtering of prefixes is less optimal when compared against BGP announcements

  • Explain the structure of a DDoS attack.

    • An attempt to compromise a server or network resources with a flood of traffic
    • Attack compromises and deploys flooding servers that send high volumes of traffic to a victim

  • What is spoofing, and how is related to DDoS attack?

    • Impersonating a legitimate server with a spoofed IP address. One method causes a server to flood a target with unsolicited responses to spoofed requests. The other uses the spoofed IP address in the both the source and destination IP, causing the server to send responses / requests to itself.

  • Describe a Reflection and Amplification attack.

    • A reflective attack is sending a bunch of spoofed requests to a server which will then DDoS the target on behalf of the attacker.

  • What are the defenses against DDoS attacks?

    • Traffic Scrubbing Services
    • Access Control List filters
    • BGP Flowspec

  • Explain provider-based blackholing.

    • A customer autonomous system announces a blackholing message to the provider with the host name of the DDoS victim. This usually contains a special community field - the provider will then stop advertising the prefix of the affected host.

  • Explain IXP blackholing.

    • Same as the above, but on an autonomous system scale. The IXP will handling the blackholing and advertise the NULL address to the other ASes peered in the IXP.

  • What is one of the major drawbacks of BGP blackholing?

    • The destination under attack becomes unreachable.
    • The mitigation technique is also ineffective if peer autonomous systems neglect / don't respect BGP Blackholing requests.

Lesson 10

  • What is DNS censorship?

    • Large scale network traffic filtering strategy opted by a network to enforce control and censorship over Internet infrastructure to suppress material which they deem as objectionable.

  • What are the properties of GFW (Great Firewall of China)?

    1. Locality of GFW nodes - majority view is that GFW censorship nodes are present at the edge.
    2. Centralized management - blocklists obtained from two distinct GFW locations show a high possibility of a central GFW management entity that orchestrates blocklists.
    3. Load balancing - GFW load balances between processes based on source and destination IP address.

  • How does DNS injection work?

    • For DNS requests that are blocked by the GFW, the GFW will respond with a fake DNS record to prevent the client from reaching the requested content.

  • What are the three steps involved in DNS injection?

    • DNS probe is sent to a DNS resolver
    • THe probe is checked against the blocklist
    • A fake DNS A record response is sent back if the request matches the blocklist. The direct domain can be blocked, or specific domain keywords can be blocked.

  • List five DNS censorship techniques and briefly describe their working principles.

    1. Packet dropping - all traffic to specific IP addresses are dropped
    2. DNS Poisoning - return no answer or return an incorrect answer
    3. Content inspection - all traffic traverses a proxy and is inspected for objectionable content, if matches -> dropped
    4. Blocking with resets - sends a TCP (RST) to block individual connections that contain requests with objectionable content.
    5. Immediate reset - suspends traffic coming from a source immediately, for a short period of time

  • Which DNS censorship technique is susceptible to overblocking?

    • Packet dropping

  • What are the strengths and weaknesses of “packet dropping” DNS censorship technique?

    • Strengths
      • Easy to implement
      • Low cost
    • Weaknesses
      • Maintenance of the blocklist
      • Overblocking

  • What are the strengths and weaknesses of “DNS poisoning” DNS censorship technique?

    • Strengths
      • No overblocking

  • What are the strengths and weaknesses of “content inspection” DNS censorship technique?

    • Strengths
      • Precise censorship
      • Flexible
    • Weaknesses
      • Not scalable

  • What are the strengths and weaknesses of “blocking with resets” DNS censorship technique?

    • None given.

  • What are the strengths and weaknesses of “immediate reset of connections” DNS censorship technique?

    • None given.

  • Our understanding of censorship around the world is relatively limited. Why is it the case? What are the challenges?

    1. Diverse measurements
    2. Need for scale
    3. Identifying the intent to restrict content access
    4. Ethics and minimizing risks

  • What are the limitations of main censorship detection systems?

    • They either no longer exist or rely upon volunteers performing measurements, which can cause them to get in trouble with their local governments.

  • What kind of disruptions does Augur focus on identifying?

    • This system focuses on IP-based disruptions, not DNS-based manipulations.

  • How does Iris counter the issue of lack of diversity while studying DNS manipulation? What are the steps associated with the proposed process?

    • Iris uses open DNS resolvers located all over the globe.
    • The two main steps are:
      1. Scanning the Internet's IPv4 space for open DNS resolvers
      2. Identifying infrastructure DNS resolvers

  • What are the steps involved in the global measurement process using DNS resolvers?

    1. Perform global DNS queries
    2. Annotating DNS responses with auxiliary information
    3. Additional PTR and TLS scanning

  • What metrics does Iris use to identify DNS manipulation once data annotation is complete? Describe the metrics. Under what condition, do we declare the response as being manipulated?

    1. Consistency metrics
    2. Independent verifiability metrics
    • If neither of these metrics are satisfied, the response is said to be manipulated.

  • How to identify DNS manipulation via machine learning with Iris?

    • Not covered.

  • How is it possible to achieve connectivity disruption using routing disruption approach?

    • Withdrawing previously advertised prefixes using BGP

  • How is it possible to achieve connectivity disruption using packet filtering approach?

    • Block packets meeting a certain criteria disrupting the normal forwarding action.

  • Explain a scenario of connectivity disruption detection in case when no filtering occurs.

    • When no filtering occurs, the measurement machine will see an increase of 2 in the IP ID - this means the two hosts communicated

  • Explain a scenario of connectivity disruption detection in case of the inbound blocking.

    • Traffic from the reflector to the site containing objectionable data is blocked. Thus, the IP ID only increases by 1 because the SYN-ACK from the site never reaches the reflector.

  • Explain a scenario of connectivity disruption detection in case of the outbound blocking.

    • Outbound reset packets from the reflector do not reach the site. The site will continue to send SYN-ACK packets until it receives an ACK, causing the reflector's IP ID to increase by 2 each time.

Lesson 11

  • Compare the bit rate for video, photos, and audio.

    • Videos have the highest bit rate, with photos being the second and audio being last.

  • What are the characteristics of streaming stored video?

    • Stored video is streamed, interactive, and has continuous playout.

  • What are the characteristics of streaming live audio and video?

    • Similar to streaming stored, however, many simultaneous users are requesting the video. Live audio or video is also delay-sensitive.

  • What are the characteristics of conversational voice and video over IP?

    • Real-time and delay-sensitive, also loss-tolerant

  • How does the encoding of analog audio work (in simple terms)?

    • Quantization, the rough conversion of continuous waves to discrete waves

  • What are the three major categories of VoIP encoding schemes?

    1. Narrowband
    2. Broadband
    3. Multimode

  • What are the functions that signaling protocols are responsible for?

    1. User location
    2. Session establishment
    3. Session negotiation
    4. Call participation management

  • What are three QoS VoIP metrics?

    1. end-to-end delay
    2. jitter
    3. packet loss

  • What kind of delays are including in “end-to-end delay”?

    • Total delay from mouth to ear. This includes:
      • The time it takes to encode the audio
      • The time it takes to put it in packets
      • All the normal sources of network delay that network traffic encounters such as queueing delays
      • Playback delay which comes from the receiver's playback buffer
      • Decoding delay which is the time it takes to reconstruct the signal

  • How does “delay jitter” occur?

    • Buffer sizes, queuing delays, network congestion, etc.

  • What are the mitigation techniques for delay jitter?

    • Maintaining a buffer called the "jitter buffer" or the "play-out-buffer". This mechanism smooths out or hides the variation in delay between different received packets, buffering them and playing them out for decoding at a steady rate.

  • Compare the three major methods for dealing with packet loss in VoIP protocols.

    1. Forward Error Concealment (FEC) - transmitting redundant data alongside the main transmission, allows the receiver to replace lost data with the redundant data.
    2. Interleaving - Mixing chunks of audio together so that if one set of chunks is lost, the lost chunks aren't consecutive.
    3. Error concealment - basically guessing what the lost audio packet might be.

  • How does FEC (Forward Error Correction) deal with the packet loss in VoIP? What are the tradeoffs of FEC?

    • Answered above. The more redundant data transmitted, the more bandwidth is consumed.

  • How does interleaving deal with the packet loss in VoIP/streaming stored audio? What are the tradeoffs of interleaving?

    • The receiving side has to wait longer to receive consecutive chunks of audio , increasing latency.

  • How does error concealment technique deal with the packet loss in VoIP?

    • Answered above.

  • What developments lead to the popularity of consuming media content over the Internet?

    • Bandwidth for the core network and last-mile access links have increased over the years.
    • Compression technologies have become more efficient.

  • Provide a high-level overview of adaptive video streaming.

  • Which protocol is preferred for video content delivery - UDP or TCP? Why?

    • TCP provides reliability, congestion control.

  • What was the original vision of the application-level protocol for video content delivery and why was HTTP chosen eventually?

    • Allows the server to be stateless and the intelligence to download the video is left to the client. Allows content provides to use the already existing CDN. Bypasses middleboxes and firewalls because HTTP is well-known.

  • Summarize how progressive download works.

    • The client sends byte-range requests for part of the video, instead of requesting the entire video. The client pre-fetches some video and stores it in the playout buffer.

  • How to handle network and user device diversity?

    • Using bitrate adaptation - avoids using one static bitrate. Allows clients to determine the bitrate and then increase / decrease based upon network conditions.

  • How does the bitrate adaptation work in DASH?

    • Dynamic Streaming over HTTP (DASH) just uses dynamic bitrate adaptation. Videos are divided into chunks and encoded at multiple bit rates. The client adapts the quality video / bitrate it's requesting from the server based upon network conditions.

  • What are the goals of bitrate adaptation?

    1. Low or zero re-buffering
    2. High video quality
    3. Low video quality variations
    4. Low startup latency

  • What are the different signals that can serve as an input to a bitrate adaptation algorithm?

    • Network throughput
    • Video buffer

  • Explain buffer-filling rate and buffer-depletion rate calculation.

    • The network bandwidth divided by the chunk bitrate is the buffer-filling rate.
    • The buffer-depletion rate or the output rate is simply 1 (1 second). How fast can we watch video.

  • What steps does a simple rate-based adaptation algorithm perform?

    • Estimation of future bandwidth
    • Quantization is the continuous throughput mapped to a discrete bitrate

  • Explain the problem of bandwidth over-estimation with rate-based adaptation.

    • Client requests high quality video, however, the bandwidth has dropped tremendously - causes the video buffer to deplete. The player takes time to converge to the correct bandwidth.

  • Explain the problem of bandwidth under-estimation with rate-based adaptation.

    • Under-estimation can cause the network bandwidth to be monopolized by a greedier client.

Lesson 12

  • What is the drawback to using the traditional approach of having a single, publicly accessible web server?

    1. Users are located all across the globe, interruptions for geographically separated users can be prevalent
    2. Viral videos will cause the server to be overloaded
    3. Single point of failure in the case of a natural disaster

  • What is a CDN?

    • Content Distribution Network - networks of multiple, geographically distributed servers and/or data centers with copies of content that direct users to a server or server cluster that can best serve the user's request.

  • What are the six major challenges that Internet applications face?

    1. Peering point congestion
    2. Inefficient routing protocols
    3. Unreliable networks
    4. Inefficient communication protocols
    5. Scalability
    6. Application limitations and slow rate of change adoption

  • What are the major shifts that have impacted the evolution of the Internet ecosystem?

    1. Increased demand for online content, especially videos
    2. Topological flattening of the Internet

  • Compare the “enter deep” and “bring home” approach of CDN server placement.

    • Enter deep - phrase used to describe placing CDNs deep into the access networks of the world. Makes the distance between the user and the closest server cluster as small as possible. Downside is that it's difficult to manage and maintain so many clusters.
    • Bring home - place fewer, larger clusters at key points - less servers to maintain but the users will experience higher delay and lower throughput

  • What is the role of DNS in the way CDN operates?

    • DNS servers will consult local DNS servers for the ISP / CDN and determine the CDN that contains the requested video. The DNS will proceed to provide the client with the IP address of the CDN cluster / server containing their requested content.

  • What are the two main steps in CDN server selection?

    1. Mapping the client to a cluster
    2. Selecting a server from the cluster

  • What is the simplest approach to select a cluster? What are the limitations of this approach?

    • Selecting the geographically closest cluster
    • Selecting the geographically closest cluster is actually picking the closest cluster to the LDNS which might not be the closest to the client.
    • The closest cluster might not have the best performance either.

  • What metrics are could be considered when using measurements to select a cluster?

    • The end-to-end metrics to be considered for cluster selection are delay and bandwidth.

  • How are the metrics for cluster selection obtained?

    • Active metric collection through probing, pinging.
    • Passive metric collection to track network conditions.

  • Explain the distributed system that uses a 2-layered system. What are the challenges of this system?

    • The cluster selection strategy proposes requires a centralized controller that has a real-time view of the network conditions - difficult to do given the scale of today's networks.
    • This model also needs to have data for different subnet-cluster pairs. Some clients will be deliberately routed to sub-optimal clusters.

  • What are the strategies for server selection? What are the limitations of these strategies?

    • A server could be assigned randomly. Not optimal because a highly stressed server could be selected randomly.
    • Load balancing could be used, but also not optimal

  • What is consistent hashing? How does it work?

    • Distributed hash table used to balance load, assigning roughly the same number of content IDs and requires relatively little movement of these content IDs when nodes join and leave the system.

  • Why would a centralized design with a single DNS server not work?

    • Introduces a single point of failure

  • What are the main steps that a host takes to use DNS?

    1. The user host runs the client side of the DNS application
    2. The browser extracts the hostname and passes it to the client side of the DNS application
    3. DNS Client sends a query containing the hostname of DNS
    4. DNS Client eventually receives a reply which includes the IP address of the hostname
    5. As soon as the host receives the IP address, it can initiate a TCP connection to the HTTP server located at that IP

  • What are the services offered by DNS, apart from hostname resolution?

    1. Mail server / host aliasing
    2. Load distribution

  • What is the structure of DNS hierarchy? Why does DNS use a hierarchical scheme?

    • The DNS hierarchy solves the scalability problem.
    • THe hierarchy has root servers, top level domain servers, authoritative servers, and local DNS servers.

  • What is the difference between iterative and recursive DNS queries?

    • Iterative - the client is referred to a different DNS server in the chain until it can resolve the request
    • Recursive - each DNS server will resolve the hostname on behalf of the client, client doesn't have to submit more than one request

  • What is DNS caching?

    • Saving hostname resolutions locally

  • What is a DNS resource record?

    • A method of storing the hostname to IP address resolution

  • What are the most common types of resource records?

    • Type A - domain name and IP address
    • Type NS - domain name and appropriate authoritative DNS server
    • Type CNAME - alias hostname and canonical name
    • Type MX - alias hostname of a mail server and the canonical name of the mail server

  • Describe the DNS message format.

  • What is IP Anycast?

    • Route a client to the closest server as determined by BGP. Assigns the same IP address to multiple servers and lets BGP handle getting the client to the closest server.

  • What is HTTP Redirection?

    • Just sending a client a 300-level code to request the content from a different server. Useful for load balancing, doesn't require central coordination.