CPSC 441, Fall 2014
Information About the Second Test

The second and final test will take place in class on Wednesday, November 19. It will cover course material through Friday, November 14. From the textbook, this includes parts of Chapters 3, 4, and 5, starting from Section 3.4. We have generally concentrated more on Internet protocols than on general principles, and we have covered less detail as we proceeded deeper into the protocol stack. The main readings included Chapter 3, Sections 3.4, 3.5, and 3.7; Chapter 4, Sections 4.1.1, 4.2, 4.4, 4,5 and 4.6; and Chapter 5, Sections 3, 4, and 7. You are responsible for earlier material to the extent that the new material builds on it.

The test will include mainly longer and shorter essay-type questions. The last question on the test will be a long, summary essay dealing with everything that we have covered from the beginning of the course. You will not be asked to write any Java code. However, there might be some questions about the Java API for UDP programming (Lab 5). There might be some questions about other labs, in particular Lab 7, which covered things that are not in the book. I do not expect you to memorize the format of TCP, IP, or Ethernet headers, but you should be familiar with the important fields in those headers.

Here are some of the terms and ideas that you should know for the test:

sliding window protocol
sequence numbers
ACK numbers
cumulative ACKs
TCP connection setup and tear down
   three-way handshake:  SYN, SYNACK, ACK
   FIN packets for closing the connection
TCP header fields
   source and destination port numbers
   sequence and acknowledgement numbers
   flags (SYN, ACK, FIN, RST)
   receive window size
MTU (Maximum Transmission Unit), maximum packet size 
MSS (Maximum Segment Size), maximum length of application data
TCP services
   reliable two-way connection
   flow control
   congestion control
reliable communication
   all packets delivered to upper level protocol, in order
   uses sequence numbers and ACK numbers
   uses retransmission
   duplicate ACKs and fast retransmit
RTT (Round Trip Time)
retransmission timeout:
   EstimatedRTT = (1/8)*EstimatedRTT + (7/8)*SampleRTT
   DevRTT = (1/4)*DevRTT + (3/4)*abs(EstimatedRTT - SampleRTT)
   TimeoutInterval = EstimatedRTT + 4*DevRTT
flow control
   avoid sending more data than receiver can handle
   uses receive window size, rwnd, from TCP header
congestion control in TCP
   avoid overloading routers by backing off transmission rate when packet loss occurs
   no explicit feedback from routers
   uses congestion window, cwnd; number of un-ACKed bytes <= max(rwnd,cwnd)
   slow start:  start with cwnd = 1 MSS, double cwnd for every RTT
   slow start ends upon packet loss or when cwnd > ssthresh
   congestion avoidance: increase cwind linearly until packet loss;
      upon retransmission, set ssthresh = 0.5*cwnd and go back to slow start;
      upon fast retransmit, cwnd = cwnd/2, return to congestion avoidance after next non-dupp ACK
The Network Layer: transmission of datagram across a network possibly through routers
two basic network types:  datagram networks and virtual circuit networks
forwarding vs. routing
a router has interfaces on multiple networks and forwards packets between networks
forwarding tables (also called routing tables)
gateway router for a network
NAT (Network Address Translation) and how it helped extend the life of IPv4
    32-bit IP addresses, divided into network ID and host ID
    network numbers such as and
    netmasks such as and
    IPv4 header fields: 
        version number
        fields having to do with datagram fragmentation
        TTL (Time-to-live), used to avoid infinite looping
        upper level protocol
        source and destination IP addresses
    ICMP (Internet Control Message Protocol), used for example by ping and traceroute
Some of the many changes in IPv6:
    128-bit IP numbers
    no fragmentation
    no options in header
why IPv6 is necessary
routing algorithms; find paths from source routers to destination routers
Bellman-Ford Equation:  d_x(y) = min( c(x,v) + d_v(y) ), min taken over neighboring nodes v
link state algorithms:
   every node has full knowledge and computes shortest paths
   requires broadcast from every node about state of links to neighbors
distance vector algorithms:
   distance vector at a node holds current best estimate of distance (cost) to other nodes
   only requires direct communication (exchange of distance vectors) between neighboring nodes
   nodes update their distance vectors based on information from neighbors' distance vectors
autonomous systems (AS)
differences between intra-AS and inter-AS routing
BGP (border gateway protocol)

The Link layer   
two kinds of link:  point-to-point and broadcast
broadcast implied shared media and the Media Access Problem
types of multiple access used for broadcast media:
    channel partitioning protocols:
       TDM: Time Division Multiplexing
       FDM: Frequency Division Multiplexing
       CDMA: Code Division Multiple Access (used in some cellular data networks)
    taking turns protocol:
       Token Ring, extinct (?) competitor to Ethernet
       polling by a master node (Bluetooth for example)
    random access protocols
       implies possibility of collisions, with random delay before retransmission
       CSMA: Carrier Sense Multiple Access
       CSMA/CD:  Carrier Sense Multiple Access with Collision Detection (traditional Ethernet)
       CSMA/CA:  Carrier Sense Multiple Access with Collision Avoidance (WiFi)
    a link-layer protocol with many physical protocols (thinwire, 10-BASE-T, 100-BASE-SX, etc.)
    MAC address (Media Access Control)
    48-bit unique MAC address, built into Ethernet interface
    the address FF:FF:FF:FF:FF:FF (all 1's) is used for broadcast
    current LAN technology is switched Ethernet
Ethernet switches:
    eliminate collisions
    switches do NOT have Ethernet addresses
    use point-to-point full duplex connection to each host;
    provide packet switching, based on ethernet addresses
    plug-and-play; require no configuration; they are self-learning
       learns by inspecting source Ethernet addresses in arriving packets
    forward broadcast packet to all links, except the one it arrived on
    forward non-broadcast packet just to appropriate link, IF KNOWN;
       otherwise, forward it to all links
Ethernet frame format:
    preamble (seven 10101010's followed by one 10101011), for synchronizing clocks
    destination and source Ethernet address
    type of data
    CRC (Cyclic Redundancy Check), for error detection
ARP (Address Resolution Protocol)
    finds the Ethernet address associated with a given IP address
    host broadcasts an ARP query with the IP address;
        the Ethernet adapter for that IP responds directly to the host
    host stores the information in an ARP table
datagrams going out of the local network are addressed to the router's Ethernet
router strips off Ethernet header of incoming packet and add a new one to outgoing packet

UDP programming API in Java
    differences from TCP programming (no connections, possible packet loss, etc.)
    messages are just byte arrays
    class DatagramSocket, with methods send(datagram) and receive(datagram)
    the method datagramSocket.setSOTimeout(milliseconds) and why it exists
    class DatagramPacket
        constructor new DatagramPacket(data,length,address,port) for packets to be sent;
        methods getData(), getLength(), getAddress(), and getPort() for received packets
Topics from Lab 7 that you should be familiar with:
    NFS (Network File System)
    DHCP (Dynamic Host Configuration Protocol)
    NAT and port forwarding