# Introduction to Computer Networks

## 1. Introduction

### Protocal

protocols define format, order of msgs sent and
received among network entities, and actions taken on msg transmission, receipt.

### Network edge

Hosts / end systems: clients and servers (run application programs).

### Network core

Mesh of interconnected packet switches (e.g., routers and link-layer switches) and links.

++Two fundamental approaches to moving data through a network: packet switching (on-demand), circuit switching (reservation-based).++

#### packet switching

Hosts break application-layer messages into packets. Resource sharing.

* queueing delay: wait to be transmitted on link
* dropped: if memory (buffer) fills up

#### circuit switching

Call setup. No resource sharing. Ex: FDM.

(訂位 vs. 無訂位餐廳)

#### Routing

Determines source-destination route taken by packets.

#### Forwarding

Move packets from router’s input to appropriate router output.

#### Delay

Delay at a single router: $d_{nodal} = d_{proc} + d_{queue} + d_{trans} + d_{prop})$

#### Throughput

end-end throughput = transmission rate of the bottleneck link

### Layering

Pros: explicit structure, modularization (eases maintenance).

Cons: one layer may duplicate lower-layer functionality, functionality at one layer may need info from other layers.

### ==OSI==

#### Application (messages)
supporting network applications (FTP, SMPT, HTTP, P2P)
#### Presentation
allow applications to interpret meaning of data (encryption, compression)
#### Session
synchronization, checkpointing, recovery of data exchange
#### Transport (segments)
Process to process data transfer (TCP, UDP).

##### Functions

* Segmentation and Reassembly
* Service Point Addressing: by specifying this address, the transport layer makes sure that the message is delivered to the correct process
* Connection-oriented service or connectionless service

#### Network (datagram)
Routing of network-layer datagrams from one host to the other located in different networks (IP, routing protocal).

##### Functions
* Routing: which route is suitable from source to destination
* Logical Addressing: IP
#### Link (frames)
Transfer between neighboring node (802.11, Ethernet).

When a packet arrives in a network, it is the responsibility of DLL to transmit it to the Host using its ++MAC address++.

The Receiver’s MAC address is obtained by placing an ARP(Address Resolution Protocol) request onto the wire asking “Who has that IP address?” and the destination host will reply with its MAC address.

##### Functions
* Framing: provides a way for a sender to transmit a set of bits that are meaningful to the receiver
* Physical addressing: MAC address
* Error control
* Flow Control
* Access control

#### Physical (bits)
It is responsible for the actual physical connection between the devices.

##### Functions
* Bit synchronization
* Bit rate control
* Physical topologies (bus, star, or mesh)
* Transmission mode (Simplex, half-duplex and full-duplex)

Internet stack “missing” layer 2 & 3.


#### Message segmentation

Pros:
* reducing delay (pipelining)
* error correction
* regulate package size

Cons:
* packets have to be put in sequence
* header bytes overheads

### Network security

* Distributed Denial of Service (DDoS): overwhelming resource with bogus traffic
* packet sniffing
* IP spoofing

## 2. Application Layer

++Communication++ for a network app takes place ++between end systems++ at the application layer.

Processes in different hosts communicate by ++exchanging messages++.

### Sockets

Defined as the software interface between process and computer network. Process sends/receives messages to/from its socket, like a door.

==A socket is the interface between application layer and transport layer within a host.==


### Addressing processes

Identifier includes both ++IP and port number++ associated with process on host.

### Transport service

What to choose? Data integrity, timing, throughput, security...

#### TCP

* reliable transport
* flow control
* congestion control
* connection-oriented

Does not provide: timing, minimum throughput guarantee, security.

#### UDP

* unreliable data transfer

Does not provide: reliability, flow control, congestion control, timing, throughput guarantee, security, or connection setup.

#### SSL (secure sockets layer)

++SSL is at app layer!!++ Apps use SSL libraries, which “talk” to TCP.
SSL encrypts data and passes the encrypted data to TCP socket.

* encrypted TCP connection (TCP- enhanced-with-SSL)
* data integrity
* end-point authentication

### Web and HTTP

Client (browser) and server “talk” by exchanging HTTP messages.
Web page (document) consists of objects. ++Each object is addressable by a URL.++

Uses TCP.

#### non-persistent HTTP

At most one object sent over TCP connections. Connection then closed.

Requires 2 RTTs per object.

#### persistent HTTP

Multiple objects can be sent over a single TCP connections.

One RTT for all the referenced objects (除了第一個 object 需 2 RTTs, 之後每個要抓的 object 皆只需 1 RTT).

### Web cache (proxy server)
Satisfy client request without involving origin server.

### DNS (domain name system)

“name” (www.yahoo.com) used by humans to IP address

When host makes DNS query, query is sent to its ++local DNS server++.

## 3. Transport Layer

Provide ++logical communication++ between ++app processes++ running on different hosts.

Host uses ++IP addresses & port numbers++ to direct segment to appropriate socket.

Transport protocols run in end systems:
* send side: breaks app messages into segments, passes to network layer
* rcv side: reassembles segments into messages, passes to app layer

### Transport vs. network layer
* network layer: logical communication between ==hosts==
* transport layer: logical communication between ==processes==

#### household analogy

12 kids in Ann’s house sending letters to 12 kids in Bill’s house:

* hosts = houses
* processes = kids
* app messages = letters in envelopes
* ==transport protocol = Ann and Bill who demux to inhouse siblings (mail collection and distribution)==
* ==network-layer protocol = postal service==

### TCP
==reliable==(no corrupted or lost data bits, in-order), ++connection-oriented++ ==in-order== delivery
* ==congestion control== (為別人著想)
regulated traffic sending rate
* ==flow control==（為自己著想）
sender will not overwhelm receiver
* ==connection setup==

No delay (timing) guarantees and bandwidth guarantees.

##### TCP socket
4-tuple(只要有一個 value 不同, socket ID 就不同):
* source IP address
* source port number
* dest IP address
* dest port number

#### Segment structure: seq. numbers, ACKs
* sequence numbers: byte-stream “number” of first byte in TCP segment
* ACKs: seq # of ++next byte expected++ from other side


#### Reliable data transfer
TCP creates rdt service on top of IP’s unreliable service.

Retransmissions triggered by:
* timeout events
* duplicate acks (dupacks)

##### TCP fast retransmit
if sender receives 3 ACKs for same data: resend unacked segment with smallest seq #

#### Flow control
==Receiver controls sender==, so sender will not overflow receiver’s buffer by transmitting too much, too fast.

Receiver “advertises” ++free buffer space++ by including rwnd (receive window) value in TCP header.

#### Connection management
3-way handshake

#### Congestion control

##### Principle
++Too many sources sending too much data too fast for network to handle.++
* lost packets (buffer overflow at routers)
* long delays (queuing in router buffers)

##### Congestion costs
* more work (retrans) for given “goodput”
* unneeded retransmissions => link carries multiple copies of pkt (decreasing goodput)

##### TCP congestion control

* end-end approach
* each sender limits its sending rate as a function of perceived network congestion

TCP keeps a variable, congestion window (denoted cwnd), which imposes a constraint on sending rate. By tuning cwnd value, sender can adjust its sending rate.

### UDP
++unreliable++, ++connectionless++ ++unordered++ delivery, light error checking

#### UDP socket
2-tuple:
* destination IP address
* destination port #

#### Why UDP?
* no connection establishment: no delay(3-way handshake)
* simple: no connection state
* small header size
* no congestion control: as fast as desired

## 4. Network Layer

* Data exchange ++among computers++.
* Network-layer protocols is in every host, router.
* Internet’s best-effort service model provides neither bandwidth nor timing guarantees, intended to make ++net-layer as simple as possible++.
* additional functionalities implemented at higher layers
* Three major components: IP, routing, and ICMP protocols.
### forwarding and routing
* ==Forwarding==: forwarding table determines ++local forwarding at this router++
* using destination host addresses (range of addresses)
* forwarding tables in datagram networks can be modified at any time
* ==Routing==: routing algorithm determines ++end-end path through network++

#### analogy
* Forwarding: process of getting through single interchange (e.g., router) from input to appropriate output (選擇適當的交流道出口)
* Routing: process of planning trip from source to dest (i.e., the path along which pkts flow from src to dest)

### IP (Internet Protocol)

#### IP addressing: CIDR

* Internet address assignment strategy
* generalizes notion of subnet addressing

### ICMP (Internet Control Message Protocol)

* error detection and reporting
* utilized by ++ping++ and ++traceroute++

### Routing
Find least-cost path from source to destination.

## 5. Link Layer, LANs

Links: communication channels that ++connect adjacent nodes++(hosts, switches/routers) along communication path

Data-link layer has responsibility of transferring datagram from one node to physically adjacent node over a link.

++MAC (medium access control) addresses used in frame headers to identify source, dest++.

Features:
* error detection, correction
* sharing a broadcast channel: multiple access
* link-layer addressing
* local area networks: Ethernet, switches

Q. Why we need both link-level and end-end (trans-level) reliability?
Link-level rdt 無法保證 trans-level in-order delivery. Net-level IP 也可能在送上 link 前就 lost pkts.

#### Analony

* tourist = datagram
* transport segment = communication link
* transportation mode(plane, train, car...) = link- layer protocol
* travel agent = routing algorithm/protocol

### Multiple access links, protocols
* point-to-point link
* single sender at one end of link, single rcvr at the other end of link
* Ethernet
* broadcast link (shared wire or medium)
* multiple sending and receiving nodes connected to same, single, shared broadcast channel
* 802.11

#### Problems

* How to coordinate access of multiple sending and receiving nodes to a shared broadcast channel?
* multiple access protocols

#### multiple access protocol

* fully decentralized: no coordinator, no single point of failure

Three broad classes:

1. channel partitioning: TDMA, CDMA
2. random access ( how to detect collisions? how to recover from collisions?)
3. taking turns (polling): Bluetooth

### Switches vs. routers

#### routers
* network-layer devices (examine network- layer headers)
* compute forwarding tables using routing algorithms, IP addresses
#### switches
* link-layer devices (examine link-layer headers)
* compute (switch) forwarding tables using flooding, self-learning, MAC addresses