Networks FINAL

Simplified TCP events → Sender Side

(1) Data received from application: Packet → Sequence Number

(2) ACK received

(3) Timeout: One timer → Oldest packets (smallest sequence number)

• Timeout = retransmit

TCP Receiver events → explain?

(1) arrival of in-order segment with expected seq #. All data up to expected seq # already ACKed

• delayed ACK. Wait up to 500ms for next segment. If no next segment, send ACK

(2) arrival of in-order segment with expected seq #. One other segment has ACK pending

• immediately send single cumulative ACK, ACKing both in-order segments

(3) arrival of out-of-order segment higher-than-expect seq. # .Gap detected

• immediately send duplicate ACK, indicating seq. # of next expected byte

(4) arrival of segment that partially or completely fills gap

• immediate send ACK, provided that segment starts at lower end of gap

TCP Fast retransmit

Occurs when the senders gets at least 3 of the same ACKs, it fast retransmits the packets to recover faster since it knows the packet is loss/corrupted

• After receiving 3 additional ACKs for same data, resend unACKed segment with smallest sequence #

• Likely that unACKed segment lost, so don’t wait for timeout

TCP Flow Control

Receiver:

• rwnd = Total capacity - (used buffer) => rwnd = RcvBuffer – [LastByteRcvd – LastByteRead]

Sender:

• Can’t send more data to receiver if rwnd = 0

• With persist timers, if the sender does receive the rwnd = 0, the persist timer starts. If the timer expires, the sender then sends 1 byte of data to probe the receiver and see if there is space.

Define Congestion in Computer Networks

informally: too many sources sending too much data too fast for network to handle

• Lost packets (buffer overflow at routers)

• Long delays (queueing in router buffers)

Additive increase and multiplicate decrease

approach: sender increases transmission rate (window size), probing for usable bandwidth, until loss occurs

• additive increase: increase  cwnd by 1 MSS (Maximum Segment Size) every RTT until loss detected

• multiplicative decrease: cut cwnd in half after loss

TCP Congestion Control: Details

Sender limits transmission: LastByteSent - LastByteAcked <= (less than or equal to) cwnd

• TCP sending rate: send cwnd bytes, wait RTT for ACKs, then send more bytes… rate ~ cwnd / RTT (bytes/sec)

End to End Congestion VS Networks Assisted Congestion

End to End Congestion:

• No explicit feedback from network

• Congestion inferred from end-system observed with loss and delay

• Approach taken by TCP

Networks Assisted Congestion:

• Routers provide feedback to end systems

• Single bit indicating congestion

• Explicit rate for sender to send out

T/F: Standard TCP Congestion Control uses network assisted approach

FALSE

Explain Bandwidth Probing

Increase rate in response to arriving ACK until loss event occurs, then decrease sender’s rate

TCP Tahoe and Reno

Tahoe

• After loss, go to slow start

Reno

• After loss, skips slow start and keeps adding one (no exponential)

Explain TCP congestion control stages

(A) Slow Start:

• cwnd = 1 MSS at beginning, double cwnd every RTT, increment cwnd for every ACK

(B) Congestion Avoidance (CA)

• Check if cwnd > sstresh, if so then switch from exponential to linear

• Both (A) and (B) are Mandatory Taho

(C) Fast Recovery:

• Sender takes account of duplicate ACK

• duplicate ack is when cwnd = +3

• (A), (B), (C) are all in Reno

Main function of Network Layer

Provide Host-to-Host communication

What are the two planes of Network Layer and their functionalities

(1) Data plane (Hardware)

• Local functional in charge of forwarding

• Uses the header ith the forwarding table

(2) Control plane (Software)

• Global functionality in charge of routing

• Two methods:

  • Traditional routing algorithms:

    • Individual routing algorithm components in each and every router interact in the control plane

    • Routing algo function in one router communicates with other router to compute forwarding table values

    • Traditional = routers

  • Software-defined networking:

    • Remote controller computes, installs forwarding tables in routers

    • might be implemented in remote data center managed by ISP or third party

    • Communicates with router by exchanging messages contains forwarding table and some routing information

    • SDN = remote servers

Two types of Control planes Traditional VS SDN approach

Traditional:

• Router does both the routing and forwarding

SDN:

• Remote server has remote controller that computes, installs forwarding tables in routers

Why Network Layer provided by IP is called “best effort”

• It’s trying its best to provide a service

No guarantees on:

1. Successful datagram delivery to destination

2. Timing or order of delivery

3. Bandwidth available to end-end flow

What are the main functions of input and output ports

Input port functions:

• physical layer: bit-level reception, Physical link Termination

• link layer: Needed to interoperate with other side of link e.g., Ethernet

• switching: using header field values, lookup output port using forwarding table in input port memory.

  • control packets are forwarded to routing processor. Goal: complete input port processing at ‘line speed’

  • input port queuing: if datagrams arrive faster than forwarding rate into switch fabric

Output port functions:

• stores packets received from switching fabric

• Transmit packets on outgoing link

  • Performs necessary link layer and physical layer functions

Discuss destination based forwarding

One of the input port functions for Forwarding is called Destination-based forwarding and it's a forwarding technique that is based only on the destination IP address (just like the traditional approach for the control plane routing algorithms). The internet uses this forwarding approach as it helps determine the next router to go to based on the packet's destination. 

First, the router has a table called the routing table that it uses to map the destination IP address to the next router IP address it hops to. Any time a packet arrives at the router, it reads the desination IP address from the packet header then uses it as a key on the routing table. If a router got a packet with the destination IP address of 192.172.4.16, it would check the routing table for any entry that has 192.172.4.X network to send the packet to the next router. If there is no entry, it uses the "longest prefix matching" to get the closest match with this packet. Then the packet is forwarded to the next router IP address it hops to and this keeps going until it reaches it's destination. 

Main function of Routing processor based on traditional and SDN

Traditional:

• Execute routing protocol

• Maintain routing table and attached link state information

• Computes forwarding table

• Routing on router

SDN:

• Responsible to communicate with Remote controller

• Get Forwarding table and install it in input ports 

• Routing in remote controller

How switch fabric operators work

(1) Memory:

• First generation routers, computers switch under direct control of CPU (oldest so one packet at a time)

• packet copied to system’s memory

• Speed limited by memory bandwidth

• Single memory read write, so two packets can’t be forwarded at the same time, even if different O/P port (ONLY ONE A TIME, One input one output)

(2) Bus:

• Datagram from input port to output port via a shared port

• Input can send multiple in bus, output is one at a time

• If multiple packet at same time all but one must wait as bus can transfer one packet at a time 

• Regardless of different ports or anything, doesn’t matter how many come in and only one gets out

(3) Interconnection network:

• Scaling uses multiple switching “planes” at the same time

• Packets are forwarded through a switching fabric made up of interconnecting paths.

• Multiple packets can be transferred simultaneously, depending on the internal structure.

Why switch fabric speed ideally NR?

N = # of input ports

R = transmission rate of individual link

Because if it’s less than NR, packets get dropped/queued because it can’t switch as fast as the input port are transmitting data. If equal or greater than, then it ensures max throughput and simultaneously transfer packets

Discuss queuing at input port of individual link

Which packet is better and why? (A) FIFO, (B) Priority, (C) Round Robin, (D) Weighted Fair Queuing

(D) Weighted Fair Queueing

• Generalized Round Robin

• Each class (I), has weight, w_i and gets weighted amount of service in each cycle

• Minimum bandwidth guarantee (per-traffic-class)

Usage of TTL

TTL = Time To Live which is remaining max hops to destination router

Why IP protocol needs to compute checksum at every router?

The reason the router has to calculate the IPv4 header checksum again is because the header's element with the TTL (remaining max hops) and the options change. This is all to ensure that the datagram changes are being presented every time the packet goes through the router

Which IPV4 headers are not available in IPV6

Header checksum, Fragmentation, Options field

T/F: Each host at most have one IP address (Hint: Who gets IP address)

FALSE - Host can have different interfaces

Convert IP address to dotted decimal notation: 11111111.00001000.00000001.00000011

Convert each section:

• 11111111 => 255

• 00001000 => 8

• 00000001 => 1

• 00000011 => 3

So in the end you get 255.8.1.3

What is the 32-bit binary equivalent of the IP address 127.0.0.1, 255.255.255.255, 1.0.0.0, and 192.168.1.1?

127.0.0.1 => 01111111.00000000.00000000.00000001

255.255.255.255 => 11111111.11111111.11111111.11111111

192.168.1.1 => 11000000.1010

What is subnet? What is subnet mask?

Subnet:

• Device interface that can physically reach each other WITHOUT passing through an intervening router

• Isolated network is a subnet (look at picture from slides)

Subnet mask:

• IP addressing assigns address to subnet

• /24 means high-order 24 bits: Subnet is part of IP address

• Ex: subnet 223.1.1.0/24 means you can have 254 usable addresses

How subnets receive IP address?

ICANN: Internet Corporation for Assigned Names and Numbers

• allocates IP addresses, through 5 regional registries (RRs)

• manages DNS root zone, including delegation of individual TLD (.com, .edu , …) management

Classful vs (CIDR)

CIDR: Classless InterDomain Routing

• Generalize the notation for subnet addressing 

• subnet portion of address of arbitrary length

• address format: a.b.c.d/x, where x is # bits in subnet portion of address (x also known as network prefix)

Classful:

• Before CIDR, network prefix was constrained to 8-, 16-, 24-bits in length

  • 8-bit = Class A, 16-bit = Class B, 24-bit = Class C

• Class C can have 256-2(special use)=254 only hosts : Too small 

• Class B can have 65536 - 2 = 65534 too big 

• Disadvantage: Rapid depletion of class B and poor utilization

How DHCP works? What other info it provides?

Also T/F: DHCP is a network protocol?

DHCP: Dynamic Host Configuration Protocol

• Goal: host dynamically obtains IP address from network server when it “joins” network

• allows reuse of addresses (only hold address while connected/on)

DHCP can return more than just allocated IP address on subnet:

• address of first-hop router for client

• name and IP address of DNS sever

• network mask/ subnet mask (indicating network versus host portion of address)

NAT → Scenario

NAT: Network address translation

• all devices in local network share just one IPv4 address as far as outside world is concerned

• Private IP stays private

• Uses translation table

(1) Replace: outgoing datagrams: replace (source IP address, port #) of every outgoing datagram to (NAT IP address, new port #)

(2) Remember: (in NAT translation table) every (source IP address, port #)  to (NAT IP address, new port #) translation pair

(3) Replace: replace (NAT IP address, new port #) in destination fields of every incoming datagram with corresponding (source IP address, port #) stored in NAT table

Longest prefix matching

when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.

Ex: Interface 0 and interface 1

Switching fabrics

• Connects router's input ports to output ports

• transfer packet from input link to appropriate output link

Switching rate: rate at which packets can be transfer from inputs to outputs

• often measured as multiple of input/output line rate

2 types of forwarding

Destination-based forwarding:

• forward based only on destination IP address (traditional)

Generalized forwarding:

• forward based on any set of header field values

Tunneling

When an IPv6 datagram is carried as payload in IPv4 datagram among IPv4 routers (“packet within a packet”)

• When tunneling, put the IPv4 source and destination addresses in the box just like the pic

Routing Protocols

Goal: determine “good” paths (equivalently, routes), from sending hosts to receiving host, through network of routers

graph: G = (N,E)

N: set of routers = { u, v, w, x, y, z }

E: set of links  ={ (u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }

c_a,b: cost of direct link connecting a and b

             e.g., c_w,z = 5, c_u,z = ∞

Routing Algorithm Classification

global: all routers have complete topology, link cost info

• “link state” algorithms

static: routes change slowly over time

decentralized: iterative process of computation, exchange of info with neighbors

• routers initially only know link costs to attached neighbors

• “distance vector” algorithms

dynamic: routes change more quickly

• periodic updates or in response to link cost changes

Dijkstra algorithm (aka How link states work)

computes least cost paths from one node (“source”) to all other nodes

• gives forwarding table for that node

• Start

WILL NEED TO MAKE THIS TABLE FOR ALL DIJKSTRA TABLES

[A] Centralized vs Decentralized Routing

[B] (T/F) Link State is centralized routing algorithm

[C] How link state achieves centralized on decentralized property

[A]

Decentralized:

• Iterative process of computation, exchange of info with neighbors

• Routers initially only know link costs to attached neighbors

Centralized:

• Network topology, link costs known to all nodes

[B] T

[C] Through link state broadcast, all nodes have same info which is all routers know the topology

What is the job of link layer? Packet name?

(1) To send packets from one node to adjacent node

(2) Frames