Computer Network

Computer Network

Physical Layer

"bits on the wire"

Link Layer

Reliable delivery between adjacent nodes

Link Layer Services

Framing, link access
- encapsulate datagram into frame, adding header, trailer
- channel access if shared medium
- "MAC" addresses used in frame headers to identify source and destination
Reliable delivery between adjacent nodes
Flow control
- pacing between adjacent sending and receiving nodes.
Error Detection
- errors caused by signal attenuation, noise.
- receiver detects presence of errors
Error Correction
- receiver identifies and corrects bit error(s) without resorting to retransmission
Half-duplex and full duplex

Error Detection and Correction

Parity Checking
Internet Checksum
CRC (Cyclic Redundancy Check)

Multiple Access Protocols

Channel Partitioning Protocols
- TDMA (Time Division Multiple Access)
- FDMA (Frequency Division Multiple Access)
Random Access Protocols
- Slotted ALOHA
- ALOHA
- CSMA, CSMA/CD, CSMA/CA
  - CSMA (Carrier Sense Multiple Access)
    - non-persistent CSMA
    - 1-persistent CSMA
    - p-persistent CSMA
  - CSMA/CD (Carrier Sense Multiple Access with Collision Detection)
  - CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)
- "Taking Turns"

Link-layer Addressing

MAC Address
48 bits
ARP (Address Resolution Protocol)

Ethernet

Ethernet frame

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Preamble|Dest Address|Source Address|Type|   Data  |CRC|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Preamble: 7 bytes with pattern 10101010 followed by one byte with pattern 10101011.
Destination and Source Address: MAC Address of destination and source
Type: indicates the higher layer protocol (mostly IP)
CRC: checked at receiver, if error is detected, the frame is simply dropped

Link-layer Switches

Hubs
Switches

PPP (Point-to-Point Protocol)

Link Virtualization: ATM, MPLS

Network Layer

Network Layer Functions

forwarding: move packets from router's input to appropriate router output

routing: determine route taken by packets from source to dest

"best effort" service: IP provides no guarantees for bandwidth, loss, order, timing and so on.

Virtual Circuit vs. Datagram

Virtual Circuit	Datagram
connection-oriented communication	connectionless communication
required circuit setup	no setup
packet contains a short VC number	packet contains the full source and destination address
routers need to hold state information about each VC	routers do not hold state information about connections

IP (Internet Protocol)

IPv4: RFC791

IPv4 Addressing

Classful Addressing

Class	Leading bits	Network size	Host size	Subnet mask
Class A	0	8 bits	24 bits	255.0.0.0
Class B	10	16 bits	16 bits	255.255.0.0
Class C	110	24 bits	8 bits	255.255.255.0
Class D (multicast)	1110	N/A	N/A	N/A
Class E (reserved)	1111	N/A	N/A	N/A

CIDR (Classless InterDomain Routing)

RFC4632

VLSM: Variable-Length Subnet Mask

address format: a.b.c.d/x, where x is # bits in subnet portion of address

Reserved Address

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|  This host
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |0 0 ... 0 0|                         Host                      |  A host on this network
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1|  Broad on the local network
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Network  |0 0 0                 ...                     0 0 0|  Broad on a distant network
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  127  |                      (Anything)                       |  Loopback
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Reserved private IPv4 address ranges:

10.0.0.0 - 10.255.255.255
172.16.0.0 - 172.31.255.255
192.168.0.0 - 192.168.255.255

DHCP (Dynamic Host Configuration Protocal)

v4: RFC2131, v6: RFC8415

Port: DHCP server uses UDP port 67, host uses UDP port 68.

Host sends "DHCPDISCOVER" message (broadcast)
DHCP server responds with "DHCPOFFER" message (broadcast)
Host requests IP address with "DHCPREQUEST" message (broadcast)
DHCP server sends "DHCPACK" message

Route Aggregation

NAT (Network Address Translation)

Internet Header Format

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |Version|  IHL  |Type of Service|          Total Length         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Identification        |Flags|      Fragment Offset    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Time to Live |    Protocol   |         Header Checksum       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Source Address                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Destination Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Options                    |    Padding    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Version: 4 bits.
IHL(Internet Header Length): 4 bits
The length of the internet header in 32 bit words. Note that the minimum value for a correct header is 5.
Type of Service(TOS): 8 bits.
Total Length: 16 bits
The length of the datagram, measured in octets, including internet header and data.
Identification: 16 bits.
Flags: 3 bits
- Bit 0: reserved, must be zero
- Bit 1: (DF) 0 = May Fragment, 1 = Don't Fragment.
- Bit 2: (MF) 0 = Last Fragment, 1 = More Fragments.
Fragment Offset: 13 bits
This field indicates where in the datagram this fragment belongs. The fragment offset is measured in units of 8 octets (64 bits). The first fragment has offset zero.
Time to Live(TTL): 8 bits
This field indicates the maximum time the datagram is allowed to remain in the internet system.
Protocol: 8 bits
This field indicates the next level protocol used in the data portion of the internet datagram.
- 1：ICMP
- 6：TCP
- 17：UDP
Header Checksum: 16 bits
A checksum on the header only.
Source Address: 32 bits
The source address.
Destination Address: 32 bits
The destination address.
Options: variable
Padding: variable
The internet header padding is used to ensure that the internet header ends on a 32 bit boundary. The padding is zero.

IP Fragmentation

MTU (Maximum Transmission Unit)

Ethernet: 1500
802.3: 1492
802.5: 4464
FDDI: 4352
ATM AAL5: 9180
PPP: negotiated

Fragmentation

IP router splits the datagram into several datagram
Fragments are reassembled at receiver

involved IP header fields:

When a datagram is fragmented, the identification is the same in all fragments.
The fragment offset is the offset of the payload of the current fragment in the original datagram.
The total length is the length of the current fragment.

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |Version| Traffic Class |           Flow Label                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Payload Length        |  Next Header  |   Hop Limit   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   +                                                               +
   |                                                               |
   +                         Source Address                        +
   |                                                               |
   +                                                               +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   +                                                               +
   |                                                               |
   +                      Destination Address                      +
   |                                                               |
   +                                                               +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Routing Algorithms

Link State

Dijkstra's algorithm

OSPF (Open Shortest Path First)

RFC2328, RFC5340

Distance Vector

Bellman-Ford algorithm

RIP (Routing Information Protocol)

RFC2453, RFC2080

Hierarchical Routing

aggregate routers into regions, "autonomous systems" (AS).

routers in same AS run same routing protocol

Internet inter-AS routing: BGP (Border Gateway Protocol)

RFC4271

Broadcast and Multicast Routing

Transport Layer

TCP

Transmission Control Protocol

RFC793

TCP Header Format

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |          Source Port          |       Destination Port        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Sequence Number                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Acknowledgment Number                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Data |           |U|A|P|R|S|F|                               |
   | Offset| Reserved  |R|C|S|S|Y|I|            Window             |
   |       |           |G|K|H|T|N|N|                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           Checksum            |         Urgent Pointer        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Options                    |    Padding    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             data                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Connections

Connection establishment: "three-way handshake"
Connection termination: "four-way handshake"

Flow Control

sliding window

Congestion Control

RFC5681

slow start
congestion avoidance
fast retransmit
fast recovery

UDP

User Datagram Protocol

RFC768

UDP Header Format

    0      7 8     15 16    23 24    31
   +--------+--------+--------+--------+
   |     Source      |   Destination   |
   |      Port       |      Port       |
   +--------+--------+--------+--------+
   |                 |                 |
   |     Length      |    Checksum     |
   +--------+--------+--------+--------+
   |
   |          data octets ...
   +---------------- ...

Application Layer

HTTP

HyperText Transfer Protocol

HTTP/1.1: RFC2616

Message Formaat

Message        = Request-Line | Status-Line
                 *(message-header CRLF)
                 CRLF
                 [ message-body ]
Request-Line   = Method SP Request-URI SP HTTP-Version CRLF
Status-Line    = HTTP-Version SP Status-Code SP Reason-Phrase CRLF
message-header = field-name ":" [ field-value ]

Method Types

HTTP/1.0: GET, POST, HEAD
HTTP/1.1: GET, POST, HEAD, PUT, DELETE

Status Codes

Successful 2xx
- 200 OK
Redirection 3xx
- 301 Moved Permanently
- 304 Not Modified
- 307 Temporary Redirect
Client Error 4xx
- 400 Bad Request
- 403 Forbidden
- 404 Not Found
Server Error 5xx
- 502 Bad Gateway
- 505 HTTP Version Not Supported

Nonpersistent HTTP vs. Persistent HTTP

Cookies

Web Caches

Example

Client request

GET / HTTP/1.1
Host: www.google.com

Server response

HTTP/1.1 200 OK
Content-Length: 3059
Server: GWS/2.0
Date: Sat, 11 Jan 2003 02:44:04 GMT
Content-Type: text/html
Cache-control: private
Set-Cookie: PREF=ID=73d4aef52e57bae9:TM=1042253044:LM=1042253044:S=SMCc_HRPCQiqy
X9j; expires=Sun, 17-Jan-2038 19:14:07 GMT; path=/; domain=.google.com
Connection: keep-alive

<HTML file>

DNS

Domain Name System

RFC1034, RFC1035

FTP

File Transfer Protocol

RFC959

control connection: port 21
data connection: poet 20

Electronic Mail

SMTP

Simple Mail Transfer Protocol

RFC5321

Sample SMTP interaction

S: 220 www.example.com ESMTP Postfix
C: HELO mydomain.com
S: 250 Hello mydomain.com
C: MAIL FROM: <sender@mydomain.com>
S: 250 Ok
C: RCPT TO: <friend@example.com>
S: 250 Ok
C: DATA
S: 354 End data with <CR><LF>.<CR><LF>
C: Subject: test message
C: From:""< sender@mydomain.com>
C: To:""< friend@example.com>
C:
C: Hello,
C: This is a test.
C: Goodbye.
C: .
S: 250 Ok: queued as 12345
C: quit
S: 221 Bye

POP

Post Office Protocol

RFC1939

IMAP

Internet Message Access Protocol

RFC3501