| 021 | Mon | 6pm-9pm | Chung Hall Room 135 |
| 022 |
Fri |
8am-11am |
Chung Hall Room 135 |
Lab Assignments |
30% |
Midterm |
25% |
|
Final exam (3 hours)
|
45% |
Lecture Topic (linked to sample
questions)
|
Text Readings (from 3rd Ed.)
|
Important concepts |
Supplementary References |
Introduction |
1.1 - 1.4
|
Layering, OSI model, Internet,
Local Area Networks, Wide Area Networks. The concept of a "protocol"
involving two or more autonomous processes, using message exchanges to
carry out some cooperative task. The
three army problem as an example of a protocol for synchronizing
the actions of two processes through unreliable message exchanges;
proof that it must fail (there can be no last message in the
exchange....). |
A
Brief History of NTP Time IEEE 1588 Precision Time Protocol |
Physical Layer |
2.1 - 2.2 |
Nodes and network interface
cards, properties of links (copper wire, optical fiber, wireless radio
frequencies). Propagation delay and
space-time diagrams. Limitations to
transmssion distance because of attenuation
and dispersion. Encoding
methods used in different versions of Ethernet: Manchester (10 Mbps),
4B/5B (100Mbps), PAM-5 (Gigabit). |
How
1000BASE-T
Ethernet
Works |
Framing / Synchronization |
2.3, 2.6.2 |
Asynchronous
ASCII
on a serial
link. Synchronous transmission with byte-oriented
framing (sentinals
plus character stuffing), bit-oriented
framing (flags plus bit
stuffing). Ethernet frame format.
Finite-state
machines
to
encode/decode
the bit-stuffing process. |
|
Data Link Layer Flow Control |
2.5 |
Simplex,
half-duplex,
full-duplex
transmission. The need for flow
control when Alice wishes to
transmit faster than Bob can handle. The need for Alice to indicate she
has no data to send right now (as opposed to "0" or "1"). The
importance of pipelining (as
opposed to
"stop-and-wait") as the bandwidth-delay product increases. Reasoning
about the correctness of data link protocols: Bartlett's "Alternating
Bit Protocol", and Knuth's "Verification
of
Link-Level
Protocols" |
Alternating
Bit
Protocol Notes on Knuth's Verification Article |
| Error Recovery |
2.4
|
Parity
codes,
two-dimensional
parity
versus
burst errors, polynomial (CRC) |
|
Medium Access Control |
2.6 - 2.8 |
Ethernet
CSMA/CD,
Token
Ring,
CSMA/CA
in 802.11 wireless networks. Why carrier sense isn't
perfect.
Why collision detection work in wired networks, but not in wireless
networks. |
|
Packet Switching |
3.1 - 3.5 |
Evolution
of
LAN
topologies from physical bus/tree (Ethernet) or ring
structure to "star" wiring to an active electronic "hub". Components of a switch: input ports,
packet buffers, path selection logic, interconnection fabric, output
ports. The advantage of output buffering over input buffering to combat
"Head-of-the-Line" blocking. Interconnection
fabrics: crossbars, banyan network, Batcher sorter. Transparent bridges: the concept of
a "broadcast domain"; use of "flat" MAC addresses; self-learning MAC
address filtering tables with "content addressible memory" (aka "CAM"
or "associative memory"); the importance of avoiding cycles in the
network graph through the Spanning Tree algorithm. VLANs using port numbers or tags to
partition a network into logically disjoint pieces. Virtual Circuit-switching, which
requires a "call setup" to reserve resources along a fixed
source-destination path so that each packet need only carry a small
virtual circuit ID --- as opposed to "datagrams" where each packet
carries a full source/destination header and can find its way
independently through the network; historical use of virtual cirucuits
in ISDN and ATM; current use in MPLS. |
|
| Material
above
may
be
included on the midterm test |
|||
Internetworking |
4.1 - 4.5, 9.1 |
The Internet Protocol (IP) forms
an overlay network designed to sit on top of many different network
technologies, and managed by different organizations. Advantange of IP encapsulation over translating gateways
at network boundaries is to avoid the "N-squared problem". However, it
means you can't assume the underlying network technologies provide more
than basic service (unreliable datagrams). IP uses hierarchical, structured addresses, as opposed to "flat" MAC addresses at layer 2 bridges. Initially, addresses were defined as Class A (8-bit network number starts with "0"), Class B (16-bit network number starting with "10") and Class C (24-bit network number starting with "110"). Now, addresses are in such short supply that we use CIDR ("Classless InterDomain Routing") to allow the network part to have any length (e.g., "a.b.c.d/N" where 1<N<32 is the number of bits in network number). The Internet has no central authority with power over everything; it is a loose confederation of Autonomous Systems (ASs), each of which is owned by different organizations and hence subject to different operating policies. Packet forwarding between ASs is defined by contractual agreements, not some global algorithm applied to the whole world. The biggest ASs form the default-free core of the Internet (they have routes to every legal IP network in the world). Others ASs may have customer-provider links (up towards the core, down towards their own customers) or peer-to-peer links (shortcuts to neighboring systems). We can classify ASs as: Transit (service providers that carry traffic that neither starts nor ends locally); Stub (customers that just want an uplink from their internal network to the world); and Multi-Homed (customers with several uplinks to different service providers for reliability, but they are not service providers). Note that each AS is has a unique number, but these AS numbers have nothing to do with the addresses carried in an IP datagram. Routing within a single AS is typically handeld by certain well-known automated route-update protocols: Distance Vector (aka RIP) and Link State (aka OSPF). Once the routing tables have been initialized, the packet forwarding decision is based on the longest prefix matching algorithm. Routing between ASs is handled by the BGP ("Border Gateway Protocol"); paths generated by BGP generally follow customer-provider links up from the source AS towards the core and then down towards the destination AS. Not all paths in the Internet are usable, for example, you can't take a shortcut through a Multi-Homed AS to reach a third location. DHCP allows hosts to ask for the temporary use of an IP address from a local server to reduce the amount of human intervention required. Similarly, Network Address Translation (NAT) can be used by an organization to share a single public IP address among many computers on a private network. DNS is used to find the IP address associated with a particular domain name (i.e., "bass.cs.ucr.edu" --> "138.23.169.40"); ARP is used to find the MAC address associated with a particular IP address located on the same subnet. IP does not assume that the underlying networking technology supports hop-by-hop flow control or other methods to prevent congestion at a bottleneck link in the middle of the Internet. In this case, IP routers often just start dropping packets, assuming that TCP sources will react to the packet loss by reducing their rates (see last section). |
|
End-to-End Protocols |
5.1 - 5.2, 5.4 |
Finally, no new set of addresses
required, because lower layers handle end-to-end delivery! Basic issues include (1) multiplexing (eg, port numbers to allow different programs to have network connections open at the same time), (2) reliability, (3) application-level flow control, (4) IP-level congestion control (see last section). UDP only handles multiplexing, although an application using UDP could add the other features if it wanted to. UDP only protects the header with an error-detection checksum in case the application would prefer noisy data over nothing. TCP handles all four of these issues. It builds a connection-oriented, reliable, ordered byte stream between the two endpoints. TCP connection state machine features three-way handshake for initial connection (with "clock based" initial sequence number guards against delayed duplicate problem), bidirectional data transfer if you wish, and graceful termination. Sequence numbers count bytes, not packets. TCP error-detection segment covers the entire segment, including the data field. Basic TCP sliding window algorithm handles application-level flow control. Sender generates data segments containing the sequence number of first byte plus length, receiver generates acknowledgements that contain next byte expected (cumulative ACK) plus advertised window. |
|
Congestion Control |
6.1 - 6.5 |
Advanced
features
of
TCP
sliding window algorithm handle IP-level congestion
control. Sender uses congestion
window to restrict the number of packets sent below the
receiver's advertised window to avoid overloading the bottleneck link
along the path. It is always a multiple of the maximum segment size (MSS). Slow start phaseinitializes the
congestion window to 1 MSS, then grows it by one MSS for every ACK
received. (Thus congestion window size doubles after every RTT.) After
a packet loss is detected, switch to congestion
avoidance
phase by reducing the congestion window by half, then
allowing it to grow by 1 MSS if all packets in the current window are
received without a loss. (Thus window changes via additive increase, multiplicative decrease.) If a packet loss is detected when its timeout expires, we must repeat the slow start phase because the network is now has no traffic from this flow (because timeouts are much larger than a typical RTT). However, the Fast Retransmit Algorithm can detect a packet loss by seeing 3 duplicate ACKs. Dynamics of TCP congestion control are tricky: (1) the congestion window size never really stabilizes, and instead follows a "saw tooth" pattern; (2) its adjustment method depends on the RTT, therefore a TCP flow with a small RTT will tend to steal bandwidth from a TCP flow with a large RTT. Some IP routers use RED (aka "Random Early Detection") to drop a few randomly chosen packets if the buffer is heavily occupied but not overflowing to tell TCP flows to slow down a bit. "Victim" is randomly chosen from the buffer, rather than always dropping the newly-arriving packet, so heavier flows are more likely to be chosen. There is an IP option called ECN (aka "Explicit Congestion Notification", which was modeled after the old "DEC bit" congestion notification method) where the router sets a bit in the IP header of the "victim" and does not drop it. At the destination, the receiver copies the ECN bit to the ACK so it eventually reaches the TCP source. Unfortunately, because it is an option, few implementations of TCP use it (and those that do are punished for doing so!), so it is rarely used. Layer 2 bridges are starting to develop their own concestion control methods. PAUSE frames were developed about 10 years ago. They can be used to stop all traffic on a single Ethernet link for a specified time. This is too crude to be useful, since PAUSEing a link between two switches because one client is overloaded would disconnect the whole network. Currently, work is underway to develop a layer 2 mechanism similar to ECN. This method, first introduced as Cisco's Backwards Congestion Notification (or BCN) protocol, will allow a congested switch to send a rate-reduction command to an individual source node across a multi-hop path. |