CS/ECE 438: Communication Networks Fall 2006 Final Exam Study Guide The final exam will be on Thursday, Dec 14th, 1:30pm-4:30pm in 1310 DCL. The exam will start at 1:30pm sharp so please arrive a bit early so you don’t waste time getting a seat. There will be no books, cheat sheets, calculators, or any other aids allowed on the final. Below is a list of topics that will be covered on the final. The final is comprehensive, so the topics listed on the midterm study guide apply as well. In addition to these questions, you are expected to know how to solve the problems on all the homeworks. • Routing vs. Forwarding • Dijkstra’s algorithm • Link state routing • Distance vector routing o How they work o Advantages / disadvantages of each o Count-to-infinity problem / poison reverse • BGP o Why hierarchical routing? o What’s done by intra-AS and what’s done by inter-AS protocols? • RIP, OSPF • Broadcast & Multicast o Why at network layer? o Reverse path forwarding o Controlled flooding o Spanning trees o Shortest path trees • IGMP o What it does and doesn’t do o What types of messages are there o Soft state • Multicast routing o Core-based trees o Source-based trees o PIM: sparse vs. dense mode, what are they, why are there two? • Transport layer o What does it provide? o TCP vs. UDP demultiplexing • UDP o Functions, checksum• Reliable data transfer o Be able to identify problems in rdtx.y given a state machine o Be able to replicate sender state machine given the receiver and vice versa o Go-back-N, selective repeat • TCP o Timeout estimation (EWMA + distance variation) o TCP ACK structure o 3-way handshake and connection teardown o Identify purpose of states in TCP state diagram (don’t have to memorize the whole diagram) o Sliding window: what sender windows and receiver windows are for o Difference between flow control and congestion control o Fast retransmit • Congestion control o What is congestion? o Why is it bad? o Congestion window o AIMD o ACK clocking o Slow-start & fast recovery o Why is TCP fair? • Congestion avoidance o Why is it better than control? o DECbit / ECN o RED (don’t need to remember formula for maxP, count, …) o TCP Vegas: what’s the basic idea, what are alpha & beta? • QoS o Why is QoS needed? o Why is QoS not deployed? o Packetized weighted-fair queueing o Playback buffer o Understand graphs with A(t), D(t), Q(t) in deterministic router model o Leaky bucket o Intserv: T-spec, R-spec, RSVP messages, soft-state o DiffServ: compare with IntServ, what advantages / disadvantages • Performance analysis o TCP delay modeling: don’t memorize the formulas, but understand how they were derived o Probability mass function, probability density function, cumulative distribution function, expected value o Properties of exponential & Poisson distributions, Poisson point process o Little’s law o What’s an M/M/1, M/D/4, etc. system? o Understand the steps in M/M/1 analysis, don’t have to memorize
View Full Document
Unlocking...