[Review] Computer network

Overview

network edge

end system=host

link&channel

media

guided

• TP
• coax
• fiber

unguided

• wireless radio

bandwidth

aceess network

MODEM & DSL

HFC/cable modem

institutional access

wireless LAN

network core

Circuit Switching

FDM

TDM

Packet Switching

store and forward

statistical multiplexing

delay

• processing delay
• queuing delay
• transmission delay
• propagation delay

packet loss

• forwarder buffer overflow

traffic intendency

Internet concept

infrastructure

ISP

network of network

layer mode

Internet Protocol Stack

• application
  • msg
• transport
  • segment
• network
  • datagram
• link
  • frame
• phy
  • bit

OSI reference mode

session

presentation

Encapsulation

Application layer

Principles of network applications

Application architectures

C/S

In a client-server architecture, there is an always-on host, called the server, which services requests from many other hosts, called clients.

P2P

In a P2P architecture, there is minimal (or no) reliance on dedicated servers in data centers.

One of the most compelling features of P2P architectures is their self-scalability.

HYBRID

Process Communication

Define the client and server processes as follows:

In the context of a communication session between a pair of processes, the process that initiates the communication (that is, initially contacts the other process at the beginning of the session) is labeled as the client. The process that waits to be contacted to begin the session is the server.

socket

The Interface Between the Process and the Computer Network

It is also referred to as the Application Programming Inter- face (API) between the application and the network

address

To identify the receiving process, two pieces of information need to be specified:

1. the address of the host
2. an identifier that specifies the receiving process in the destination host.

In the Internet, the host is identified by its IP address.

the process is identified by its port number.

transport sercice

• Relaible Data Transfer
  • If a protocol provides such a guaranteed data delivery service, it is said to provide reliable data transfer.
  • When a transport-layer protocol doesn’t provide reliable data transfer, some of the data sent by the sending process may never arrive at the receiving process. This may be acceptable by loss-tolerant applications applications.
• Throughput
  • Applications that have throughput requirements are said to be bandwidth-sensitive applications.
  • While bandwidth-sensitive applications have specific throughput require- ments, elastic applications can make use of as much, or as little, throughput as happens to be available.
• Timing
• Security

TCP

• connection-oriented

• reliable data transfer

• flow control

• congestion control

UDP

• connectionless

• best-effort

HTTP

server port

80

TCP

persistent HTTP & non-persistent HTTP

persistent http with pipeline

non-persistent http with parallel TCP

RTT

Round-Trip Time(RTT)

cookie

cokie file

set cookie

cookie

DB

http request & response

web cache

usage

conditional get

FTP

port 20, port 21

out-of-band

email

components

user agents

mail servers

smtp

smtp

pop/imap

web-based email

DNS

Distributed, Hierarchical Database

root dns server

TLD dns server

local dns server

Authoritative NDS servers

query

iterated query

recursive query

RR

type = A

type = NS

type = CNAME

type = MX

P2P

cs v.s. p2p

BT

DHT

Transport layer

Transport-layer services

Atransport-layer protocol provides for logical communication between application processes running on different hosts.

Multiplexing and demultiplexing

The job of delivering the data in a transport-layer segment to the correct socket is called demultiplexing.

The job of gathering data chunks at the source host from different sockets, encapsulating each data chunk with header information (that will later be used in demultiplexing) to create segments, and passing the segments to the network layer is called multiplexing.

UDP

as many applications are better suited for UDPfor the following reasons:

• Finer application-level control over what data is sent, and when.
• No connection establishment.
• No connection state.
• Small packet header overhead.

checksum

UDP at the sender side performs the 1s complement of the sum of all the 16-bit words in the segment, with any overflow encountered during the sum being wrapped around. This result is put in the checksum field of the UDP segment.

connectionless

rtd

methods

seq

ack

error detection

timeout

pipline

GBN

single timer

cumulative ACK

drop out of order PKTs

selective repeate

timers for each pkt

individual ack

buffer out-of-order PKT

TCP

fast retransimission

seq# and ack#

flow control

connection management

congestion control

Network Layer

Network Service Models

• Guaranteed delivery(确保交付)
• Guaranteed delivery with bounded delay(具有时延上界的确保交付)
• In-order packet delivery(有序分组交付)
• Guaranteed minimal bandwidth(确保最小带宽)
• Guaranteed maximum jitter(确保最大时延抖动)
• Security services(安全性服务)

以上 Internet 都不提供

forwarding & Routing

• forwarding: When a packet arrives at a router's input link, the router must move the packet to the appropriate output link.
• Routing: The network layer must determine the router or path taken by packets as they flow from a sender to a receiver.

建立连接(Connection setup)

网络层中另一个重要的功能（不准确描述

Virtual circuit

still store-forward

VC#

A VC consists :

1. a path(that is, a series of links and routers) between the source and destination hosts
2. VC numbers, one number for each link along the path.
3. entries in the forwarding table in each router along the path.

setup

path failure

datagram network

Longest prefix matching

router

input port

HOL

switching fabrics

memory

bus

crossbar

output port

queueing

routing processor

IP

IPV4

IP Fragmentation and Reassembly

addressing

subnet

subnet mask

DHCP

NAT

IPV6

addressing

48bits

tunneling

ICMP

routing algorithms

LS

Oscillations

OSPF

DV

infinite problem & poisoned reversed

RIP

Hierarchical routing

route aggregation

AS

BGP

Link Layer & LAN

Introduction

We'll find it convenient in this chapter to refer to any device that runs an link-layer protocol as a node.

Nodes include hosts, routers, switches, and WiFi access points.

We will also refer to the communication channels that connect adjacent nodes along the communication path as links.(我们也把沿着通信路径连接相邻结点的通信信道称为链路)

Over a given link, a transmitting node encapsulates the datagram in a link-layer frame and transmits the frame into the link.(在通过特定的链路时， 传输结点将数据报封装在链路层帧中， 并将该帧传送到链路中)

The Services Provided by the Link Layer: 成帧(framing), 媒体访问控制(Medium Access Control, MAC), 可靠交付(Reliable delivery), 差错检测和纠正(Error detection and correction).

Where Is the Link Layer Implemented: For the most part, the link layer is implemented in a network adapter(网络适配器), also sometimes known as a network interface card(NIC)(网络接口卡).

error detection & correction

Parity Checks(奇偶校验)

Perhaps the simplest form of error detection is the use of a single parity bit.

With the two-dimensional parity scheme, the parity of both the column and the row containing the flipped bit will be in error. The receiver can thus not only detect the fact that a single bit error has occurred, but can use the column and row indices of the column and row with parity errors to actually identify the bit that was corrupted and correct that error!

The ability of the receiver to both detect and correct errors is known as forward error correction(FEC).

Checksumming Methods(检验和方法)

In checksumming techniques, the d bits of data are treated as a sequence of k-bit integers. One simple checksumming method is to simply sum these k-bit integers and use the resulting sum as the error-detection bits.

internet checksum is based on this approach--bytes of data are tread as 16-bit integers and summed.

Cyclic Redundancy Check(CRC) (循环冗余检测)

An error-detection technique used widely in today's computer networks is based on cyclic redundancy check (CRC) codes.

CRC codes are also known as polynomial codes(多项式编码), since it is possible to view the bit string to be sent as a polynomial whose coefficients are the 0 and 1 values in the bit string, with operations on the bit string interpreted as polynomial arithmetic.

(略)************

MAC

Channel Partitioning

TDMA

时分多路访问

FDMA

频分多路访问

CDMA

码分多址(Code Division Multiple Access)

CDMA assigns a different code to each node. Each node then uses its unique code to encode the data bits it sends. If the codes are chosen carefully, CDMA networks have the wonderful property that different nodes can transmit simultaneously and yet have their respective receivers correctly receive a sender's encoded data bits (assuming the receiver knows the sender's code).

random access

ALOHA

有话就说，碰撞随机重传

Slotted ALOHA

• 所有的帧由 L 比特组成
• 时间被划分成长度为 L/R 秒的时隙
• 结点旨在时隙起点开始传输帧
• 如果在一个时隙中由两个或者更多帧碰撞，则所有结点在该时隙结束之前检测到该碰撞事件
• 如果有碰撞，该结点以概率P在后续的每个时隙重传他的帧，知道该帧被无碰撞地传输出去

CSMA

载波侦听多路访问(CSMA carrier sense multiple access)

• Listen before speaking 如果其他人正在说话，等到他说完为止(载波侦听(carrier sensing))
• If some one begins talking at the same time, stop talking (碰撞检测(collision detection))

CSMA/CD

1. The adapter obtains a datagram from the network layer, prepares a link-layer frame, and puts the frame adapter buffer.
2. If the adapter senses that the channel is idle(that is, there is no signal energy entering the adapter from the channel), it starts to transmit the frame. If, on the other hand, the adapter senses that the channel is busy, it waits until it senses no signal energy and then starts to transmit the frame.
3. While transmitting, the adapter monitors for the presence of signal energy coming from other adapters using the broadcast channel.
4. If the adapter transmits the entire frame without detecting signal energy from other adapters, the adapter is finished with the frame, If, on the other hand, the adapter detects signal energy from other adapters while transmitting, it aborts the transmission(that is, it stops transmitting its frame).
5. After aborting, the adapter waits a random amount of time and then returns to step 2.

binary exponential backoff

当传输一个给定帧时，在该帧经历了一连串的 n 次碰撞后， 结点随机地从
$$
{0, 1, 2, ... , 2^n - 1}
$$
中选择一个 K 值

CSMA/CA

Taking Thurns

Polling 轮询

需要一个主结点

• 主结点首先向结点 1 发送一个报文， 告诉它能够传输的帧的最多数量。
• 在结点 1 传输了某些帧后， 主结点告诉系欸但 2 它能够传输的帧的最多数量。
• (主结点能够通过观察在信道上是否缺乏信号， 来决定每个结点何时完成了帧的发送)

消除了碰撞和空时隙， 引入了轮询时延

Token passing

令牌传递协议(token-passing protocol) 没有主结点

有一个称为 令牌(token) 的小的特殊的帧在结点之间以某种固定次序进行交换。

Link layer Addressing

MAC Addresses

LAN address, physical address, MAC address 都是链路层地址的术语

MAC地址为最常用的术语

没有两块适配器有相同的MAC地址

广播地址： FF-FF-FF-FF-FF-FF

ARP

地址解析协议(Address Resolution Protocol, ARP)

• 适配器的ARP模块维系一个ARP表
• 查看表内有无对应的IP-MAC映射
• 若无广播寻址
• 更新ARP表

Routing to Another LAN

• 判断是否同一子网
• 不在同一子网 ARP 查询路由器接口MAC地址
• 投递给路由器
• 路由器再查询目的MAC
• 路由器投递

Ethernet

Ethernet Frame Structure

Preamble	Dest. address	Source address	Type	Data	CRC
8bytes	6bytes	6bytes	2bytes	46~1500bytes	4bytes

• 数据字段： 承载IP数据报。 以太网的最大传输单元(MTU)是1500字节。 数据字段最小长度是46字节，如果不够填充
• 目的地址： 包含目的适配器的MAC地址
• 源地址： 包含发送适配器的MAC地址
• 类型字段： 类型字段允许以太网服用过多种网络层协议。
• CRC：
• 前同步码：以太网帧以一个八字节的前同步码字段开始。前七个字节的值都是10101010 最后一个是10101011

Switch

Layer 2

Self-learning

1. 交换机表初始为空
2. 对于每个接口接受到的每个入帧， 该交换机再其表中存储：
   1. 再该帧源地址段中的MAC的地址
   2. 该帧到达的接口
   3. 当前时间
3. 如果再一段时间(称为老化其(aging time)) 后， 交换机没有接收到以该地址作为源地址的帧， 就在表中删除这个地址

交换机是即插即用设备(plug-and-play device)

comparing with other devices

router

hub

repeater

bridge

cut-through