Computer Networks: Fundamentals and Protocols Overview
Institutional:Wifi/Ethernet
Home: Cable Internet/Digital Subscriber Line/Satellite/Ethernet/Router
Wide Area Wireless: Cable/Tower
Delay calculations (propagation delay, transmission delay) with or with store-and-forward. Bandwidth-delay product and its meaning; Bandwidth-RTT product and its meaning.
Bandwidth-delay – Max amount of data that can be held in a link at any time (B*dprop). Bandwidth RTT – Amount of Data that the sender can send before it can receive any response from server (B * RTT, RTT = 2 *dprop, RTT: Time for small packet to traverse to one end and back). Propagation Delay = d (length of link (in bytes))/s (prop speed ~2×10^8). Transmission Delay = L (packet length (bits))/R (link bandwidth (bits per sec))
ISO/OSI reference model for computer networks (the seven layers); TCP/IP architecture for the Internet (five layers)
ISO/OSI Reference: Application/Presentation/Session/Transport/Network/DataLink/Physical
TCP/IP Architecture: Physical: Transfer bits on the links (wired or wireless). Link: Data transfers between network elements next to the link. Network: Host-to-Host Data Transfer. Transport Process-to-Process Data Transfer. Application: Supporting Network Applications
Traceroute/tracert – Provides delay measurement from source to router along end-end internet path to destination
Persistent HTTP vs. Non-persistent HTTP.
Persistent: Multi Obj can be sent over single TCP connection between Client/Serv. Non-persistent: 1 Obj sent over TCP connection and is closed after, downloading multi obj requires multi connections
Email application protocols: SMTP, POP, IMAP; their underlying transport layer protocol.
SMTP: TCP/UDP (25) POP3: TCP(110) IMAP: TCP/UDP (143)
HTTP, SMTP, DNS; their underlying transport layer protocol and the service port numbers.
HTTP/TCP/80 SMTP/TCP/25 DNS/TCP.UDP/53
Typical HTTP request methods.
GET: Get info from given serv with given URL. POST: Send data to serv. DELETE: Remove all current representation of target resource given by URL. CONNECT: Establishes a tunnel to server identified given URL. HEAD: Similar to GET, transfers status line and header sections.
Typical HTTP response status codes.
400 Bad Request: HTTP request to serv has invalid syntax. 403 Forbidden: user makes a valid request but server refuses to serve request due to permissions. 404 Not Found: Does not Exist/Not Found unable to communicate with serv or locate requested file/resource. 502 Bad Gateway: server is a gateway or proxy serv, and is not recognizing a response from backend servs that should fulfill the request.
HTTP cookie
HTTP Cookie is a special type of ID created when a user visits a website for the first time and the cookie is saved as a file on the user’s machine. User info is stored in the database from the web server with the Cookie ID. If the user comes back to the site, the user will send a Cookie ID so the website can recognize and provide information to the user quickly based on saved data.
Web caching
Web caching is the concept of downloading/accessing unchanged data from a web proxy server, this allows the user to download web objects from the proxy server that the user has visited and unchanged than remote web server which is much quicker.
DNS resource records. How to interpret a resource record of a given type (A, NS, CNAME, MX).
A: Name is the hostname and value is the IP address of hostname NS: Name is a domain and value is hostname of DNS server responsible for that domain CNAME: Name is a alias of a serv and value is the canonical name of the same serv MX: Name is a domain and value is the hostname of the email serv that is providing email services for the domain (FORMAT: NAME/VALUE/TYPE, 4-TUPLE)
How to use DNS resource records to answer related questions.
rdt 1.0, 2.0, 2.1, 2.2, 3.0: channel error characteristics & mechanisms to handle channel errors.
1.0: Perfectly Reliable, No Bit Errors, No Packet Loss, Separate FSMs for Sender/Receiver. Send/Reads data into/from underlying channel 2.0: Flip bits in packet, Users Checksum to detect bit errors. ACK/NAKS (Negative ACK): Packet (PKT) OK or PKT had Errors (Feedbacks/Retransmission) 2.1: Sequence # added to PKT for sender (two seq # 0 or 1), check if ACK/NAK is corrupted. Receiver: check for dupes (Cannot know if last PKT was ACK/NAK was OK). 2.2: Same as 2.1 but ACK only, reciever sends ACK for last PKT that received OK ACK (explicitly include seq #). Dupes ACK = Retransmit Current PKT. 3.0: Lost Packets (data, ACK), sender waits a reasonable # of time for ACK, no ACK = retransmits, If PKT or ACK is delayed, retransmission = dupe but receiver must specify seq # of PKT being ACK, cooldown timer.
Sliding window (pipelined) protocols: Go-Back-N; Selective Repeat. Window size calculation. Sequence number calculation. Number of bits to represent the sequence numbers.
Go-back-N: Sender can have N unacked packets in pipeline. receiver (RCVR) only sends cumulative ACK (no buffer, doesnt ACK packet if there is a gap or dupe ACK for highest in-order PKT. sender has timer for oldest unacked PKT (retransmit all unacked PKTS when timer expires). Selective Repeat: Sender can have N unacked PKTs in pipeline. RCVR sends individual ACK for each PKT (buffer maintained on RCVR). Sender maintains timer for each unacked PKT (retransmit only that unacked packet when timer expires)
TCP & UDP segment format.
UDP: SRC Port #/Dest Port #/Length/Checksum/AppData (Payload) (32 bits long). TCP: SRCPort#/DestPort#/Seq#/ACK#/TCPFlags(URG/ACK/PSH/RST,SYN,FIN (connection establishment and teardown)/Checksum/RCVWindow(# of Bytes RCVR willing to accept)/URG data pointer/Options(Variable Length)/AppData(Variable Length)
IP addresses. TCP port numbers. TCP sequence numbers; how are they chosen initially when a connection is established.
IP Address is based on SRC IP (Your IP), Port Number is randomly chosen between 0 – 65535 and TCP seq # is a 32-bit number created at random.
TCP acknowledgement number and sequence number in connection management scenario (Ack # = Seq # + 1) and general scenario (Ack # = Seq # + size of segment payload).
TCP cumulative acknowledgement.
Receiving everything up to and including seq # reference, implies that anything after may be outstanding.
Behavior of TCP Fast Retransmit.
Timeout period often relatively long: long delay before sending lost packet, finds lost segments via dupe ACKs (sender oftens sends many segments backtoback, if segment is lost, there will likely be many dupe ACKs), if senders rcvs 3 dupe ACKS with same data, resend unacked seg with smallest seq #.
UDP socket vs. TCP socket.
TCP is more reliable than UDP Socket, TCP takes care of data being sent to the network and being delivered to the receiver and retransmitting until ACKed by receiver, takes care of flow control.
TCP flow control
RCVR notifies Sender about free buffer space by including rwnd value in TCP header of receiver-to-sender segments (RCVBuffer = default 4096 bytes). Sender limits amt of unacked data to receiver’s rwnd value (guarantees receive buffer to not overflow)
TCP congestion control. Understand how ssthresh & cwnd is adjusted in Slow Start, Congestion Avoidance, and Fast Recovery states.
initial congestion window (cwnd) = 1 MSS, doubles every RTT, incrementing cwnd by 1 MSS for every ACK received. ssthresh = cwnd/2. Congestion Avoidance: approach, sender increases transmission rate (window size), examining for usable bandwidth, until loss occurs. additive increase = cwnd + 1 MSS per RTT until loss, multiplicative decrease = cwnd/2 after loss. Fast Recovery: 3 dupe ACK causes cwnd = cwnd/2 + 3 MSS and ssthresh = cwnd/2. Increase cwnd by 1 MSS for every dupe ACK. When new ACK comes, acking resent segment, sender will go to Congestion Avoidance state, setting cwnd = ssthresh
MSS & MTU; relationship between MSS and MTU.
MSS: max segment size, max size of payload that can be carried in TCP segment (not entire segment). MTU: max transmission unit, max size of payload that can be carried in data link layer frame (due to link layer characteristics)
Chapter 4:
IPv4 address format, datagram format: [ver/header length/type of service/datagram length/16-bit identifier/flags/13 bit fragmentation offset/time-to-live/upper-layer protocol/header checksum/32 bit src ip/32-bit dest ip/options/data] 32 bits long (Addr Format: 8 bits.8bits.8bits.8bits, example 172.16.254.1)
IPv6 address format, datagram format: Datagram: Fixed-Length 40 byte header, no fragmentation allowed. [ver/priority/flower label/payload length/next header/hop limit/src addr/dest addr/data] 32 bits long. (Addr Format: 8 groups of 4 hexadecimal digits, each group representing 16 bits (2 octets). Example: 2001:0db8:85a3:0000:0000:8a2e:0370:7334 or 2001:db8:85a3:0:0:8a2e:370:7334, leading zeros in group may be omitted.)
IPv6: Initial Motivation: 32-bit address space soon to be completely allocated or used. Header format speeds up processing and forwarding and facilitate QoS. Fixed Length 40 byte header/No Fragmentation allowed.
Longest Prefix Matching:
Looking for forwarding table entry for given destination address, use the longest address prefix that matches destination address (convert IP to binary and check the longest address it matches to)/TCAMS, Content Addressable: present address to TCAM: retrieve address in one clock cycle, regardless of table size.
Subnetting
IP Address: Subnet part – high order bits/Host part – low order bits. Subnet is a device interface with a same subnet part of IP address, can physically reach each other without intervening router. To determine the subnet, detach each interface from its host or router, creating islands or isolated networks, each isolated network is called a subset.
IP Addressing CIDR: Classless InterDomain Routing
Subnet portion of address of arbitrary length. ADDRESS FORMAT: A.B.C.D/X where X is the # of bits in subnet portion of the address (00000000 =>2726252423222120 or 128/64/32/16/8/4/2/1)
11001000 00010111 00010000 00000000 (Red: Subnet Part/Black: Host Part) => 200.23.16.0/23
NAT: All datagrams leaving local network have same single source NAT IP Address: 138.76.29.7,
different source port numbers. Datagrams with source or destination in this network have 10.0.0/24 address
for source/destination. Motivation: local network uses just one IP address as far as outside world is concerned. Range of address not needed from ISP: just one ip address for all devices. can change address of devices in local network without notifying outside world. can change ISP without changing address of devices in local network
Devices inside local net not explicitly addressable visible by outside world (security plus)
NAT Router: must replace outgoing datagrams (source IP, port #) of every outgoing datagram to (NAT IP, new port #)
remote clients/servers will respond using (NAT IP/New Port #) as destination addr. Remember (in NAT translation table)
every (source IP, port #) to (NAT IP, new port #) translation pair. Replace incoming datagrams (NAT IP, new port#) in destination fields for every incoming datagram with corresponding (source IP, port #) stored in NAT table.
NAT: Network Address Translation, 16 bit port number field. 60k simultaneous connections with single
LAN side address
NAT is controversial, router should process up to layer 3. Address solved by IPv6. Violates end to end argument.
NAT Possibly must be taken into account by app designs and P2P apps.
IP tunneling (how IPv4 router forward IPv6 datagram): Once IPv6 reaches
IPv4, the IPv6 is carried by the IPv4
Chapter 5
Routing algorithms: Link state algorithm (Dijkstra’s algorithm); distance vector algorithm (Bellman Ford algorithm)
Dijkstra’s algorithm: N’ = {u} for all nodes v, if v is adjacent to u then D(v) = c(total cost,node) else D(v) = infinity.
(Filling Graph is based on what is in N(Prime) or the set, which path takes the least amount of cost to get to a node using the nodes in the current set. Choose the smallest cost after finishing each step. IF node is already in set that means it will have no value)
Intra-AS routing protocols (OSPF, RIP); what routing algorithm does each of them use.
OSPF (Open Shortest Path First) uses Link State (Dijkstra’s Algorithm) and RIP (Routing Information Protocol) uses (Distance Vector Algorithm)
Inter-AS routing (BGP). When do routers use eBGP & iBGP sessions/connections.
(AS = Autonomous systems) is a collection of connected internet protocol routing prefixes under the control of one or more network operators on behalf of a single administrative entity or domain.
eBGP sessions/connects are used between 2 routers belonging to 2 ASs.
iBGP sessions/connects are used between 2 routers belonging to same AS
Underlying transport layer protocol for BGP.
Transport Layer for BGP is Application Layer because it uses TCP to transport messages
Chapter 6
Three categories of Medium Access Control (MAC) protocols and typical MAC protocols.
Categories: Channel Partitioning/Random Access/Taking Turns
Channel Partitioning: Divide channel into smaller “pieces” (time slots, frequence, code), Allocate piece to node for
exclusive use
Random Access: Channel not divided, allows collisions, recover from collisions.
Taking Turns: Nodes take turns, but nodes with more to send can take longer turns.
MAC Protocols:
Channel Partition: TDMA (Time Division Multiple Access)/FDMA (Frequency Division Multi Access)
Random: Slotted ALOHA, ALOHA, CSMA, CSMA/CD, CSMA/CA.
Binary exponential back-off in CSMA/CD: After Mth collision, NIC (Network Interface Card) chooses K are random
from {0,1,2, …, 2m-1}.NIC waits K * 512bit time, returns Step 2. Longer backoff interval with more collisions
LAN broadcast vs unicast.: Unicast is a communication where info is sent from one point to another point
(single source to specified destination, still the predominant form of transmission on LANs, uses TCP transport protocol)
LAN Broadcast is a communication where info is sent from one point to all other points. One sender but sent to all
receivers. Can be used to send same message to all computers on the same LAN (example: ARP uses this to send an
address resolution query to all computers on LAN)
ARP protocol (finding the MAC address for a given IP address in the LAN)
ARP: A wants to send datagram to B: B’s MAC Address is not in A’s ARP table. A broadcasts ARP query packet
containing B’s IP (All nodes on LAN receive ARP query, destination MAC: FF-FF-FF-FF-FF-FF) B receives ARP
packet, replies to A with B’s MAC Address (frame sent to A”s MAC address (unicast)) A saves IP-to-MAC address
pair in its ARP table until info becomes old (times out or soft state: info that goes away unless refreshed). ARP is
plug and play (node creates their ARP tables without intervention from net admin). ARP packets are carried directly
in Ethernet frames. No IP datagram is involved.
Ethernet switch self-learning mechanism: switch learns hosts can be reached through which interfaces, when frame
is received, switch learns the location of sender: incoming LAN segment. recordes sender/location pair in switch table.
(MAC Address/Interface/TTL)
MAC address and IP address settings during the process of sending a datagram from one subnet to another subnet.
Chapter 7
Hidden terminal problem in a wireless setting.
Hidden Terminal problem denotes the situation where 2 nodes cannot see each other (hidden) but they still may not
transmit frames at the same time because of potential frame collision. (D and Z are hidden from each other, they
cannot transmit frames to G at the same time due to the 2 frames will collide with each other at G)
Comparison between the Ethernet & WiFi in terms of MAC address format, frame format, MAC protocol, etc.
Ethernet Frame Structure [preamble/destination addr/source addr/type/data (payload)/CRC]
Wifi Frame: [frame control/duration/MAC Addr of wireless host or AP to receive this frame/MAC of Wireless host
or AP transmitting this frame/MAC of router interface to which AP is attached/seq control/addr 4 (ad hoc mode)/
data (payload)/CRC]
Ethernet does not use CSMA/CA as its MAC Protocol/WiFi (802.11) uses CSMA/CA as its MAC protocol.
Ethernet and WIfi uses CRC for error detection,
Ethernet does not use link-layer acknowledgement/Wifi uses link-layer acknowledgement.
48-bits are used to represent both Wifi/Ethernet MAC Address.
Basic concepts and methods in mobility management when a node moves from on access network
to another access network.
Routers advertise permanent address of mobiles-nodes-in-residence via routing table exchange. Tables indicate
location of each mobile located. No changes to end-systems (correspondent uses same IP to reach mobile node)
Indirect Routing: communication from correspondent to mobile goes through home agent, then forwarded to remote
Direct Routing: correspondent gets foreign address of mobile, sends directly to mobile.
Foreign agents contacts home agent: “this mobile is resident in my network”, mobile contact foreign agent on
entering visited network. Foreign agents knows about mobile and home agent knows location of mobile.
Mobile uses two addresses: permanent address: used by correspondent and care-of-address: used by home agent to
forward datagrams to mobile.
Suppose mobile users moves to another network (indirect): registers with new foreign agent, new foreign agent
registers with home agent, home agent update care-of-address of mobile, packet continue to be forwarded to mobile
(but with new care-of-address).
(Left: Indirect Routing/Right: Direct Routing)
Subnet Problem (2^N where N = amount that would yield # of subnets, i.e 4 subnets = 2^2 where N = 2)
Example: 120.126.0.0/15 => 120.126.0.0/17 where you add 2 bits to host part.
Follow basic binary protocol 00/01/10/11 to change the IP to create the 4 subnets. at the host portion.
01111000.01111110.00000000.00000000 (So starts at 16-17)
01111000.01111110.10000000.00000000
01111000.01111111.00000000.00000000
01111000.01111111.10000000.00000000