Date: 3/18/99
Place: 1 Pimentel Hall
Time: 5-6:30pm

See the midterm scores (posted 3/30/99)...

Rules: closed book and closed notes, except you may bring a single 8.5x11" sheet of paper with you which may have things written down on it on both sides.

I have had several students ask whether my intention is to grill them on very specific details and memorization of three letter acronyms, etc. The answer is no. However, some protocols were the result of specific situations that have arisen over time. For example, the DNS (the domain name system) came about to answer a need for scaling the name space. It would be good to understand the need for such a protocol and its basic theory of operation, but you do not need to regurgitate for me the location of each particular field. My intention is to focus on important concepts, so when you look over the lecture notes look not only for important individual results, but also for common themes.

Additional info: the DUAL algorithm will not be covered on this mid-term. The details of using parity checking for errors will not be covered, nor will the exact operation of the Knockout switch.

• Readings:
  Chp. 1, Chp. 3 (except 3.5 and 3.7), Chp. 4 (except 4.3),
  Chp. 5 (except 5.4), Intro Multicast Notes
  
  
• Lecture 1
  
  LAN typical characteristics
  
  • broadcast, multi-access
    
  why is the Internet challenging to understand?
  notion of controlled sharing, multiplexing
  characteristics of different approaches to multiplexing
  
  • TDM, statistical multiplexing
    
  definition of a protocol, who standardizes and designs protocols?
  what is the IETF? ISO?
  
  
• Lecture 2
  
  protocol layering advantages/disadvantages
  what is a layering violation? are they bad?
  encapsulation
  network design issues: scope, scale, robustness, incremental deployment
  end to end argument, application layer framing
  Internet design philosophy and goals
  major features of Internet design
  fate sharing, robustness to failure
  packet switching, definition of datagram
  soft state vs hard state
  best-effort delivery
  performance metrics
  
  
• Lecture 3
  
  Nyquist and Shannon results
  
  • sampling and noise
    
  link performance (delay, bandwidth, throughput)
  impact of per-packet overhead
  naming, DNS, building hierarchies for scale
  key DNS design features proving ability to scale
  IP addressing structure, prefixes
  (old) notion of address classes
  prefix masks, relationship to subnets
  
  
• Lecture 4
  
  DNS components
  DNS TTL, caching, zone transfers, server redundancy
  operation of a DNS query and reverse query
  negative caching
  
  
• Lecture 5
  
  network nodes, performance of CPUs versus memory, use of cache
  
  • importance of not copying network data
    
  link characteristics (modulation, sharing, 1/2 or full duplex)
  characteristics by which to evaluate digital/digital encodings
  NRZ and NRZI encoding, Manchester, 4B/5B code
  S/N benefit in adding new bits to quantization code
  PCM encoding, linear vs non-linear encodings
  async vs sync transmission
  framing
  data rate of SONET (not details of STS-1 format)
  
  
• Lecture 6
  
  channel coding, errors, ARQ, EC
  computation of parity, CRC, Internet checksum
  Hamming distance, parity check matrix, syndrome
  nice properties of the Internet checksum
  
  
• Lecture 7
  
  purpose and types of MAC protocols
  the "a" parameter
  CDMA benefits/drawbacks
  CSMA in various forms including CSMA/CD
  exponential backoff, Ethernet
  purpose of min./max. frame size in Ethernet
  capture effect
  frame structure and addressing of Ethernet
  service provided by Ethernet
  
  
• Lecture 8
  
  Bridges (purpose and definition)
  transparent bridges, operation of "learning" and station caches
  nastiness of loops in bridged networks
  Spanning Tree algorithm for bridges
  handling of failures in ST computation
  
  
• Lecture 9
  
  switces (really a type of bridge)
  virtual circuit versus packet or cell
  
  • RTT setup, possible losses for packets
    
  evaluation metrics for switching hardware
  buffering in switches (why and what is good/bad)
  HOL with input buffered switches
  the Knockout swich design constraints
  self-routing fabrics... Banyan (why interesting?)
  Batcher/sorting networks and Batcher-Banyan
  
  
• Lecture 10
  
  notion of Internetworking (network of networks)
  datagram abstraction, possible delivery problems w/datagrams
  IP addressing mapping & ARP operation
  IP fragmentation and reassembly, notion of MTU and Path MTU
  IP protocol header interesting features
  
  • (TTL, src/dst addresses, frag info, header checksum)
    
  direct delivery
  indirect delivery
  
  
• Lecture 11
  
  
  operation of IP source and record route options
  purpose of and types of ICMP messages
  
  • redirect and dest unreachable, in particular
    
  • use in path MTU discovery and traceroute
    
  
  
• Lecture 12
  
  structure of routing and forwarding tables
  longest prefix match algorithm
  
  • use of P tries for this algorithm
    
  tag switching approaches
  
  • claimed benefits
    
  • general operation
    
  MPLS
  
  • use of VC in ATM cases
    
  • label merging
    
  
  
• Lecture 13
  
  IP multicast model
  
  • benefits
    
  • scaling properties
    
  the mbone
  
  • use of IP in IP tunneling
    
  link layer multicast
  
  • common implementation (multicast hash filter)
    
  IP multicast on Ethernet
  
  • non-unique encoding of groups
    
  IGMP protocol
  
  • needed to know about group membership on leaf subnets
    
  • queries from routers to hosts
    
  • hosts reply to groups, suppress other host responses
    
  Wide Area Multicasting intro
  
  • downsides for ST and flooding approaches
    
  
  
• Lecture 14
  
  wide area multicasting
  
  • source-based trees
    
    • operation of RPM, pruning, grafting
      
  • shared trees
    
  • trade-offs between these
    
  scope control for IP multicast
  
  • TTL scoping and thresholds
    
  • expanding ring search
    
  • administrative scope
    
• Lecture 15
  
  key questions for routing
  DV and LS routing approaches
  
  • operation of each
    
  • problems with DV approaches
    
  • approaches to limit C2I problem
    
    • path vectors
      
    • split horizon
      
    • triggered updates
      
    • source tracing
      
  • Dijkstra shortest path algorithm
    
  • Lollipop sequence space
    
  comparison of DV vs LS routing
  
  
• Lecture 16
  
  costs and metrics, static or dynamic, oscillatory behavior
  why was RIP 1 insufficient?
  high-level points for RIP and OSPF
  IGRP
  
  • why developed?
    
  • composit metrics
    
  • holddown
    
  • route poisoning
    
  
  
• Lecture 17
  
  DUAL algorithm
  formation of Internet routing hierarchy
  BGP
  
  • purpose
    
  • path vector using AS #'s
    
  • policy
    
  • scale
    
  Internet growth problems
  
  • problems with routing table size and class B address space
    
  • also complete address depletion
    
  • use of multiple class C
    
  • aggregation of these, implication of non-portable addresses