EECS 122Spring 2004University of CaliforniaBerkeley What are the basic differences between Circuit and Packet Switching? Understand Packet Switch network hierarchy: LAN, MAN, WAN What is the motivation behind layering? What are the different layers and the corresponding key protocols? What are the main performance metrics? Howa re they defined and what are the relationships among them? PhysicalInterfacePhysicalInterfaceSynchronous unreliable bit pipeData LinkControlData LinkControlAsynchronous reliable bit pipePhysical LinkNetworkNetworkAsynchronous routed pathFH DataPhysicalInterfaceSynchronous unreliable bit pipeData LinkControlAsynchronous reliable bit pipePhysical LinkNetworkAsynchronous routed pathFH DataTransport TransportPH Data PH DataTH DataEnd Node Router End NodeApplication ApplicationData Link: !" #$ %&! " !#'$ ( $"%#))"'#( *+"#"'#"' %#+"#"%#))"'#''%+"#$, -.( !" .( !#/" .( ((. ( # What does Shannon’s theorem for the channel capacity state? How do the basic data encoding schemes (NRZ, NRZI, 4B/5B, etc.) work? How do the basic error detection schemes (parity, CRC, etc.) work? $% #&What’s the motivation behind shared media protocols?Ethernet: Why is Ethernet an improvement over Aloha? How does Ethernet MAC work? What’s the relationship between the maximum propagation time and the minimum frame size? How do hubs, bridges, and switches operate? What are the key differences among them? Why is the Spanning Tree algorithm required? How does it work? $% #& 802.11 (Wi-Fi) What are the basic physical layer protocols used by 802.11? How doe the 802.11 MAC work? What’s the efficiency of 802.11 MAC? What are the differences between Ethernet and 802.11 MAC protocols? Why are they necessary? Understand the key 802.11 MAC ideas: RTS/CTS, NAV, different IFS, etc. !Ethernet: CSMA/CD Wait until channel is idle; try; if collide, stop, wait, repeat Idea: CS should improve efficiency if fast enough Wait random multiple of 512 bit times (exponential back off) Analysis: Efficiency 1/(1 + 5a), a = PROP/TRANS'()*++%$%,-%&If medium is idle for DIFS interval after a correctly received frame and backoff time has expired, transmission can begin immediatelyIf previous frame contained errors, medium must be free for EIFSIf medium is busy, access is deferred until medium is idle for DIFS and exponential backoffBackoff counter is decremented by one if a time slot is determined to be idleUnicast data must be acknowledged as part of an atomic exchange'()*++.%, Virtual Carrier Sensing using Network Allocation Vector (NAV)/ / Understand the addressing scheme What’s the motivation behind CIDR? How does ARP work? How do NAT and DHCP work? Understand the operation of the key routing protocols (RIP, OSPF, BGP)? What are the pros/cons of each algorithm?/ / "%%&0%&01 2 % & 0& %3 03+13% %3 03+$45 06 32 0230 %3 03+032'7( !(( % Addressing reflects internet hierarchy 32 bits divided into 2 parts: Class A Class B Class C %01 network host 00network host 1160network host 1240~2 million nets256 hosts801 0%/ " $%/"& Problem: Class B is facing address space exhaustion If multiple Class C addresses are given out, routing table size needed can be too large Solution: Assign consecutive Class C addresses and in essence allow network address length to be flexible Example: A corporation needs 16 Class C addressesCIDR scheme could assign network addresses 192.4.16 to 192.4.31, i.e., in the range11000000 00000100 00010000 00000000 11000000 00000100 00011111 00110001 They share the first 20 bits of 192.4.16.0Routing tables store the 20 bit prefix(Convention: 192.4.16.0/20 = prefix)/ BC6785431212101311643213243613OSPFRIPIGRPBGP Intradomain Formulate the routing problem as a Shortest Path Problem Link State v/s Distance VectorInterdomain BGP Path Vector, Policies%! Dijkstra: Link State Use a flooding protocol to discover the entire topology Find the shortest paths in order of increasing path length from node i.Bellman Ford: Distance Vector D(i,d) = minjN(i){c(i,j) + D(j,d)}BGP: Path Vector Policy routing: Receive and advertise entire routes AS identifiers describe the path to a CIDR prefix, Why is a scheduling scheme like WFQ needed? Understand the properties of WFQ: Bandwidth sharing, Work-conservative scheduling, etc. What’s the relationship between GPS and PGPS (same as WFQ)? Understand (at a high level) the algorithm for the WFQ practical implementation based on the GPS finish times2
View Full Document
Unlocking...