Glossary

• Propagation time (T_p) = calculated from distance and speed of cable
• Distributed Coordination Function mode (DCF) = a WLAN mode
• Point Coordination Function (PCF) = a WLAN mode, better support for real-time traffic due to periodic scheduling
• Basic Service Set (BSS) = a wireless LAN
• Independent BSS (IBSS) = a wireless LAN without an AP
• Extended Service Set (ESS) = a collection of BSS
• Utilization (U) = fraction of time sender busy sending.
• Efficiency (E) = fraction of time sender busy sending useful data (eg. user data, not headers)
• Pipelining capacity = maximum number of frames that can be in flight at a time.
• Ω (Bandwidth delay product BDP) = 2PC where C = max rate of link.
• Round-trip time (RTT) = 2P where P = propagation delay.
• Autonomous system (AS) = a mechanism that allows scalability of Internet.

MAC Layer Protocols

• Pure Aloha Transmit Procedure:
  • transmit
  • start timer and wait for ACK
  • if timeout, then go to exponential backoff, or else success.
  Note that exponential backoff is already a multiple of T_p time.
• Throughput of pure Aloha is G*e^-2G, where G is input rate; e^-2G is the pure Aloha's probability of success.
• Slotted Aloha's throughput is G*e^-G, where G is input rate; e^-G is the slotted Aloha's probability of success.
• CSMA/CD is capable of medium sensing, whereas Aloha is not.
• 5 Key Assumptions of MAC protocol are:
  • Station model - all nodes are independent
  • Single channel model - only 1 transmission can happen on the medium for it to be successful.
  • Collision assumption - collision will happen if more than 1 transmission takes place on the wire.
  • Time model - time can be continuous or slotted.
  • Carrier sense
  Note: also a transmission can reach all nodes on the medium.
• CSMA/CD Transmit Procedure:
  • sense medium, if busy then either non-persistence wait random time or persistent wait random time.
  • if not busy, transmit while detecting collision. If send ends and no collision, then success.
  • If collision during send, send Jamming signal, abort and enter exponential backoff stage.
• Time for collision detection is 2 times propagation time.
• Unlike Aloha, CSMA/CD has no ACK.
• Two nodes in WLAN may not be able to communicate with each other directly.
• WLAN functions in the following modes:
  • Distributed Coordination Function, ad-hoc environment, everyone competes for medium. (DCF) (Mandatory Implementation)
    • With hand-shake: RTS/CTS exchange before data transmission.
    • Without hand-shake: no RTS/CTS mechanism.
  • Point Coordination Function, AP does all scheduling. (PCF) (Optional Implementation)
• WLAN switches to handshake mode for DCF when traffic is high and packet length is long. In this mode sender sends an request to send (RTS) frame to receiver for permission and waits for clear to send (CTS) before sending.
• PCF mode may waste bandwidth if scheduled node does not have traffic. But there is no contention for medium access.
• DCF mode has contention for medium access, hence packet delivery is done by best effort. With hand-shake mode, sender request for permission before sending, but this adds extra cost on overhead. Hand-shake or no hand-shake is decided by individual nodes.
• DCF's backoff mechanism uses a backoff time counter (BTC), which is generated randomly. BTC is decremented by 1 after each aSlotTime. When the medium becomes busy, BTC decrement stops and waits until the medium is free again, then it senses it for another DIFS + aSlotTime time before decrementing BTC further. Transmission resumes when BTC becomes 0.
• DCF waits for random interval after it finishes transmission for fairness purposes.
• In DCF mode, a node may broadcast data frame to every other node. This is done without handshake and no ACK is sent back.
• To enter PCF mode, AP senses the medium to be idle for PIFS time, it then sends out a beacon frame containing how long the AP is going to dominate the channel. Nodes receiving the beacon will update their NAV to this value.
• In PCF mode, AP may send any of the following:
  • data frame
  • CF poll frame - granting permission for a node A to send data to any other node B. Node B may send an ACK to node A. If transmission fails, node A may not resend until another CF poll is granted. If no data to send, send null frame.
  • data + CF poll frame
  • ACK frame
  • CF end frame - indicating end of PCF mode. Can also be sent when AP has no data to send and no node to pull.
• A node may join a WLAN by passive scanning beacon frames from AP or actively probing APs. This process is not part of MAC protocol.
• Important assumption: All nodes have identical radio range.
• EVERY packet transmitted in a WLAN is separated by at least SIFS period.
• MAC protocol comparisons:

  Name	Carrier sense?	ACK?	Collision Mechanism	Jamming signal?	Send Condition	throughput
  Pure Aloha	No	Yes	Oblivious to collision	No	Anytime	G*e-2G (low)
  Slotted Aloha	No	Yes	Oblivious to collision	No	Anytime	G*e-G (low)
  CSMA/CD	Yes	No	Detection, abort on collision	Yes	Medium is idle	higher
  CSMA/CA	Yes, carrier sensing and virtual carrier sensing (NAV)	Yes	Avoidance	No	carrier free and NAV=0	medium

Data Link Control (DLC) Protocols

• Link layer includes flow control feature.
• Each host and router is called a node and each channel that connects adjacent nodes are called links.
• Data link layer is responsible for transferring upper layer datagram from one node to adjacent node. Link layer packets are also called a frame.
• Link layer provides the following services:
  • Framing
  • Best effort reliable delivery between two adjacent nodes
  • Flow control - receiver is able to pace the sending rate
  • Error detection
  • Error correction - by either receiver corrects the error or ask for retransmission (via ARQ)
• Link layer is implemented in hardware, software, and firmware.
• Framing is done by either byte-oriented protocols (BISYNC,PPP) or bit-oriented protocols (Highlevel Data Link Control) or clock-based approach (SONET).
• Bit Error Rate (BER) for WLAN is around 10^-4, LAN is around 10^-12.
• Error Detection and Correction bits (EDC) are used for error detection. Larger EDC field yields better detection and correction. EDC is a capability in all network levels.
• Some error detection techniques are:
  • Parity bits
  • Cyclic redundancy check (CRC), in MAC and Link
  • Internet checksum, not as strong as CRC, in IP, TCP, ICMP, and UDP. Sum up blocks of 16bits and take the 1's complement.
• Error correction at the receiver is computationally expensive but maybe useful for real-time communication or for long/fat/noisy channels.
• Automatic Repeat Request (ARQ) should deliver data to the receiver without error, in the right order, and without any duplicate. It takes the following variation:
  • stop-and-wait
  • sliding-window protocol
  • go-back-N
  • selective-retransmit
• Flow control is integrated with ARQ.
• Stop-and-wait:
  • Tx sends PDU (protocol data unit) and waits for ACK within a timeout period.
  • Rx checks CRC and sends ACK.
  • If Tx receives no ACK within timeout, it retransmits.
  • 1 bit of sequence number (SN) is used in stop-and-wait to detect duplicate packet.
• Total time for stop-and-wait transaction is t₀ + d + 2P + p + a. d = time to transmit data PDU; P = propagation time; p = time it takes Rx to process PDU and decide to reply; a = time for Rx to transmit ACK. Utilization = d / (d + a + p + 2P) and efficiency = d-H / (d + a + p + 2P), where H is the time to transmit header data.
• The average time A between 2 successive packet is A = (d + 2P + p_r + a) / (1 - p); where p_r is the processing time and p is the probability of a frame or its ACK being corrupted.
• Stop-and-wait's sender cannot send further packets until it receives an ACK from receiver. This mechanism is an explicit flow control system, but it only permits 1 packet to be in the wire, which is inefficient.
• Sliding-window (aka pipelined protocols) allows multiple "in-flight", yet to be acknowledged packets. The sequence number bits must be larger than 1 bit and buffer must exist at sender and/or receiver.
• Two generic forms of sliding window protocols are go-back-N and selective repeat.
• Sliding-window protocol may continue sending data before ACK is received. The number of packets that it may send is called pipelining capacity.
• Pipelining capacity is proportional to bandwidth delay product.
• Sender keeps 3 state variables:
  • SWS - send window size. Fixed or negotiated with receiver, constraint by sequence space size and buffer available.
  • LAR - last acknowledgement received
  • LFS - last frame sent
  Note that LFS - LAR ≤ SWS
• Receiver keeps 3 state variables:
  • RWS - receive window size
  • LFA - largest acceptable SN
  • NFE - next frame expected
  Note that LFA - NFE ≤ RWS - 1
• For go-back-N (a consequence of RWS = 1), sender maintains 1 timer for the oldest sent but unACKed frame. If an ACK arrives, slide the window and restart timer if there are still unACKed frames. Receiver will only accept in sequent frames and drop everything else.

Internet Protocols

• IP provides hop by hop communication, built on top of DLC and MAC, which provides 1 hop communication.
• Key questions in the IP layer are the discovery of hosts and routers, as well as how packets are routed to the destination.
• Routers exchange routing protocols which help them build routing tables (RT).
• IP address - 129.97.92.43/24, address/prefix length. Network prefix is the same for all hosts connected to the same link. This is called address aggregation, allows smaller RT size, the 2nd mechanism for Internet scalability.
• Routing table involves the following columns: target/prefix-length, next hop, interface
• An IP is considered matched if there exists an entry in the RT whose leftmost prefix-legnth bits equal to the given IP.
• There are 3 categories of RT entires:
  • Host-specific - 32bit prefix-length (IPv4), provides exact match
  • Network-specific - 1-31bit prefix-length, provides a subnet matching
  • Default-route - used when no host or subnet matching can be found
  Note that if no RT entry matches the packet IP, then it is sent to ICMP for error handling.
• RT can be constructed statically and dynamically (by running RIP, BGP or ICMP).
• If 2 routers are on the same link, ICMP redirect message can be used by routers to tell nodes if they are not using the optimum route.
• Three types of Autonomous Systems (AS) are:
  • Stub AS - doesn't do much
  • Transit AS - may forward packets coming from other ASes
  • Multi-homed AS - has more than 1 interface routers
  Each AS has an AS ID, which is assigned by agencies.
• RIP protocol is for intra-AS RT construction, each router broadcasts its RT to neighbors every 30 seconds or so. Receiver of this RIP package will evaluate it and calculate the smallest cost path to a destination, then update its own RT table accordingly.

Transport-level Protocols

• TCP achieves end-to-end semantics and maintains data flow between applications.
• TCP operates in connection-oriented mode, in which it establishes connection between two applications.
• 3-way handshake consists of the following steps:
  • Connection request - client gives server sequence number and SYN (SYN = 1 to denote connection request)
  • 1st ACK - server sends ACK to client, giving its sequence number and SYN+ACK and receiver window size
  • 2nd ACK - client sends ACK to server, giving its receiver window size
• TCP regulates amount of data source can send before receiving an ACK. Done using sliding window protocol. This effectively gives TCP flow control.
• Flow control is managed by receiver, while congestion control is managed by sender.
• Actual send window size = min(receiver window size, congestion window size)
• Receiver may send ACK with revised window size to sender to adjust flow control at any time.
• Silly window syndrome: # of data bytes/total segment length is small. May be caused by slow sender and/or receiver.
• TCP checksum covers the entire packet, whereas IP checksum only covers the header.
• TCP ACK type:
  • Positive ACK (=1), ACK sequence is the expected sequence number.
  • Selective ACK, uses option field in the header or use 3-ACK.
  ACK generation rule:
  • In-order data: delay ACK until another segment is received or 500ms elapses.
  • Higher than expected data: send ACK with expected seq#, send 3-ACKs for fast retransmission.
  • Missing segment arrives: send ACK of next seq# expected.
  • Duplicated segment arrives: send ACK immediately.
  In summary, ACK generation rule needs to avoid the generation of many small segments and support selective repeat. And the goal is to improve TCP performance.
• In TCP, retransmission happens when retransmission timer expires, or 3-ACK is received.
• Cause of congestion is if packets arriving on different input go to the same output, or slow routers.
• Congestion control principles generally fall into static decisions (when to accept, when to discard) or dynamic decisions(monitor, inform, adjust).
• Congestion control policies include: don't discard out of sequence packets, use piggy back, spread traffic over many path.
• Dynamic decision of congestion control:
  • monitor: variety of metrics can be used: average queue length, # of retransmitted, avg pkk delay, discarded packets.
  • dissemination of congestion information: probe packets can be used or packet header can be used.
  • flow adjustment: deny/degrade service to some users.
• Main idea behind congestion control is to start slow, but speed up exponentially, then increase linearly after we hit threshold, then go back to slow start if congestion is detected (by means of timeouts and 3AKCs)