EECS3214 Computer Network Protocols and Applications

2017-01-10 9:49:23

[专业笔记] , , ,

This course includes TCP/IP architecture. 这是一门有关网络的基础课程,主要涉及Layer3-5。

This course introduce very fundamental network knowledges. It covers some old technology but that is very critical.

We will study the TCP/IP protocol through out the whole course. Advance topics includes P2P system, multimedia communication (VoIP), network security(IPSec SSL), wireless sensor networks. Top-down approach. Start from top(Application) to bot(Network). More algorithmic. More programming.

Simple core, but complex edges.

 

Jan 10 雪

What is the Internet?

(为什么要这样设计,需要考虑什么)

  • Network of networks
  • Heterogeneous(异质,这里讲的是兼容性,例如速度的兼容性)
  • Distributed
  • Owned by many different entities
  • Allows easy additions and removal from the network (without effecting other people)

 

 

 

Terminology

接下来介绍一些有关的术语 (Terminology)

host (= end system) : computer devices that connected

  • running network apps
  • PC, server, laptop, smartphone

 

communication links:

  • fibre, copper, radio, satellite
  • transmission rate = bandwidth (data rate in this course
  • 相比起来另外一个概念是物理上的带宽,例如声音,人类的声音只利用了其中很小部分的带宽

 

packet switches: forward packets (小包)

  • routers
  • switches

 

protocols(协议): control sending receiving of messages

  • protocols define format, order of messages sent and received among network entities, and actions taken on message transmission, receipt

 

Internet : 网络的网络 ("network of networks"),松散结构,共有网络和私有网络

 

Internet Standard

  • RFC: Request for comments, 由IETF 发布 [[Wikipedia]]
  • IETF: Internet Engineering Task Force [[Wikipedia]]

 

 

Service Aspect

  • communication infrastructure
    • distributed application 网络服务都是分散的
  • communication service
    • connectionless unreliable 不基于链接,不可靠,诸如UDP协议
    • connection-oriented reliable 基于链接,可靠,诸如TCP协议

 

 

Access Network

How to connect end system to edge router?

  • residential access nets
  • institutional access networks
  • mobile access networks

We should consider?

  • bandwidth
  • shared / dedicated

 

DSL or ADSL network

  • use existing telephone line to central office DSLAM ( DSL access multiplexer [MUX 数据复用器 Wikipedia] )
  • dedicated 
  • ADSL is the updated version of DSL, 它采用频分多路复用技术(Frequency Division Multiplexing)把普通的电话线分成了电话、上行和下行三个相对独立的信道,从而避免了相互之间的干扰。

 

Cable network (mean for TV cable, coaxial cable)

  • Frequency Division Multiplexing: bandwidth(physical bandwidth) divided into channels
    一个cable有他的物理带宽,物理带宽取决于物理介质,切分成不同频道,根据需求,可以将更多的频道用于下传(就是不对等传输)
  • shared
  • CMTS: cable modem termination system
  • HFC: hybrid fiber coax
    • Optical fiber: 光纤
    • Coaxial cable: 同轴电缆

 

 

Network Structure

  • network edge: applications and hosts
  • network core:
    • interconnected routers
    • network of networks
  • access networks, physical media:
    • wired, wireless communication links

 

application message breaks into packets (of length L bits), and transmits packet into access network at transmission rate (R bit/sec, bandwidth)

packet transmission delay
= time needed to transmit L-bit packet into link
= L(bits)  /  R(bits/sec)
= packets / transmission rate

传输延迟 = 包裹/带宽

 

Network Edges

  • end systems
  • client/server model
  • peer-peer model

 

Network Core

  • mesh(网格) of interconnected routers
  • packet-switching:
    • hosts break application-layer messages into packets
    • store and forward
    • end-to-end delay = router 两端的delay加起来
    • need to involved routers
      excessive congesting possible
    • queuing and loss: if arrival rate to link exceeds transmission rate of link for a period of time
      1. packets will queue, wait to be transmitted
      2. packets can be lost if buffer fills up
    • delay:
      • transmission delay
      • queueing delay
      • packets loss delay
    • Two key network-core function
      • routing: determines source destination route taken by packets
        因为世界的互联网很大,所以,要在一个路由器查找routing table,会消耗很大的时间。所以local routing table will be very small
      • forwarding: move packets from router's input to appropriate router output

 

Physical Media

  • propagates: 传播
  • guided media: copper, fiber, coax
  • unguided media: radio
  • Twisted Pair: 双绞线
    分类CAT 1-7 ,通俗说法 X类线
  • Coaxial cable
  • Fibre optical cable
  • Radio
    • terrestrial microwave
    • LAN
    • wide-area: cellular
    • satellite

 

 

Jan 12

 

Connection-Oriented Service

TCP (Transmission Control Protocol)  -  RFC 793

  • NOT the same as the traditional telephony.
  • The ISP would you to use TCP. Because TCP is more polite and follow the rules. Try to hack TCP, you will get benefits.
  • data transfer between end systems
  • hand shaking:
    • setup data transfer ahead of time
  • TCP:
    • reliable, in-order byte-stream data transfer
    • flow control
    • congestion control

 

 

Connectionless Service

UDP (User Datagram Protocol) - RFC 768

  • data transfer between end systems (Same as before!)
  • UDP:
    • connectionless
    • unreliable data transfer
    • no flow control
    • no congestion control

 

注意!HTTP其实也算是一个Connectionless Server。 这个服务是基于Connection-Oriented Service的 TCP的。

 

 

 

 

Packet Switching vs. Circuit Switching

两种模式:

  • FDM (Frequency Division Multiplexing)
    absolute guarantee, fixed - circuit switching 基于频率(Frequency)切分
  • TDM (Time Division Multiplexing)
    statistical guarantee - packet switching 基于时间(Time)切分

 

Circuit Switching

end-to-end resources allocated to, reserved for "call" between source and destination.

Commonly used in: Old style telephone route
会独立分配给你3Hz 物理带宽,当你通话质量不好的话,是因为Switcher 质量不行,而不是因为带宽不足。

 

 

Packet Switching

Packet switching allows more users to use network!
因为大部分人链接之后都处于静止状态不占用带宽!

  • Circuit-switching: 10 users
  • Packet-switching: 35 users 因为 10个人以上同时活跃的概率非常低(类似于机票超售)

 

特征:

  • great for bursty(突发的) data
    • no call setup
    • simpler
    • resource sharing
  • excessive congestion possible:
    • may cause packet delay and loss
  • can provide circuit-like behaviour (referring to Chapter 7)

 

 

 

Internet Structure

End systems connect to Internet via access ISPs.

ISP to each other directly doesn't scale O(N^2) 因此每新建一个ISP都不会直接跟全部的ISP建立链接。

IXP: Internet Exchange Point

Tire-1 commercial ISP (Wikipedia)

Content Provider Network (CDN)

 

Design Philosophy:

  • simple core, complex edge
  • best effort service
  • great support for heterogeneity (异质性,不同的设备都能够使用)
  • Dynamic by design
  • one network for many purposes
  • designed primarily for non-real-time text traffic with no QoS requirements other than reliable delivery

 

 

 

Jan 17

Lecture Slide 1 Page 47

Protocol Layers

Why need to divide into pieces(layers)?

  • network are complex
    • it has so many pieces: hosts, routers, links of various media......
  • advantages and disadvantages of layering
    • explicit structure allows identification relationship of complex system's pieces
    • modularization eases maintenance, updating of system
    • change of implementation of layer's service transparent to rest of system

 

Internet Protocol Stack

注意括号内的内容,不同layers的数据包都有不同的名称

  • Application: FTP, SMTP, HTTP (message)
  • Transport: TCP, UDP (segment)
  • Network: IP (datagram)
  • Link: PPP, Ethernet (frame)
  • Physical: bits "on the wire"

上面2.5层是在Software,下面2.5层是Hardware

 

 

Encapsulation

(封装) Lecture Slide 1 Page 49

可以看到router的任务是比较简单的,但是end system的任务就比较复杂(这符合设计理念,simple core),信息在传递的过程中有解包和打包两种过程。

All the transport must go through the physical. The router will go up through the layers and go down again. And all of these add delay.

 

ATM (Asynchronous Transfer Mode) 现在还有人在bottom layer使用这个协议,这个协议能够

 

[History 不会考]

在90s,人们并不信它Internet里面的内容是有用的,人们并不信任里面的内容。(笑)

 


Finished the Lecture Slide 1
Begin Chapter 2

 

Application Layer

creating a network app

  • 在互联网的原始设计中,core is simple.
  • no software written for devices in network core

SDN (Software Defined Network) 将router变成高计算能力的电脑。

Application architectures (应用层的架构,3种)

  • Client-server architecture
    • server
      • always-on host
      • permanent IP address
      • server farms for scaling
    • client
      • communicate with server
      • may be intermittently connected (可以间歇性在线,有一段时间断线也是可以的)
      • may have dynamic IP address
      • do not communicate directly with other clients
  • Pure P2P architecture
    • no always on server
    • arbitrary end systems directly communicate
    • peers are intermittently connected and change IP addresss
    • highly scale-able: new peers bring new service capacity, and new service demands
    • difficult to manage
  • Hybrid of client-server and P2P
    • 经典案例:
      • Napster
        • File transfer base on  P2P
        • File search is centralized
      • Instant messaging
        • Chatting between two user is P2P
        • Presence detection/location is centralized. (在线检测,定位)

 

 

Processes Communicating

Process: program running within a host.

  • with-in a same host, two processes communicated using inter-process communication

Socket 是在 application layer的数据交换。Process send/receives message to/from its socket. 这也是为什么我们推荐使用socket而不是bind一个地址。

Application with P2P architectures have BOTH client processes and server processes.

  • client process (not always on)
  • server process (always on)

Atomic process will concern in [[EECS3221]]

App-layer protocol defines (Terminology, LS2P12)

  • Types of messages exchanged
  • Syntax of message types
  • Semantics of the fields (Semantics,语义;字段的含义)
  • Rules for when and how processes send and respond to message

 

Considers

  • data integrity 是否需要非常准确的数据
  • timing 时间方面的考虑
  • throughput 数据量方面的考虑
  • security 安全方面的考虑

 

 

Jan 24

Net Neutrality: (wikipedia)

[Start from LS 2 page 16]

Securing

TCP UDP 都是没有安全措施的

SSL 可以提供

  • provides encrypted TCP connection
  • data integrity
  • end-point authentication

 

 

Web and HTTP

  • URL
    • host name
    • path name
  • base HTML-file
  • 协议
    • HTTP 1.0 - RFC 1945
      non persistent,传输完一个Object连接就关闭了
    • HTTP 1.1 - RFC 2068
      keeps the connection in a while

 

  • HTTP use TCP
    • client initiates TCP connection to server
    • server default 80
    • server accepts TCP connection from client
    • HTTP messages exchanged between browser and web server
    • TCP connection closed
  • HTTP is stateless
    • 不能保持登陆状态,登陆状态是通过别的东西来实现的(例如Cookie)
    • 因为保持登陆状态会增加设计的复杂度

 

Non-Persistent HTTP

指的是 HTTP 1.0

RTT(Round Trip Time) : Time to send a small packet to travel from client to server and back. 客户端到服务器一个来回

  1. initiate TCP connection: not too much time cost on the server side.
  2. file transmit 是无序的

Total=2 \times RTT + TransmitTime 需要两个来回加上文件传输的时间(第一次来回是握手,第二次开始才能传输数据)

Requires 2RTTs per object

browsers often open parallel TCP objects

 

Persistent HTTP

指的是 HTTP 1.1

Server leaves connection open after sending response.
Subsequent(连续的) HTTP messages between same client/server are sent over connection

 

Pipe-lining

将多个请求加入到同一个Request中,参见(wikipedia ,这个概念比较相似)

这个功能在HTTP1.1中默认是开启的。一个RTT中包含了所有referenced object,也就是说,一次性可以传输多个数据。

 

没有pipe-lining的情况:

  • client issues new request only when previous response has been received
  • one RTT for each referenced object

 

 

HTTP Message

Two types: Request, Response

Header 和 Body 之间用一个空行隔开

  • HTTP/1.0
    • GET
    • POST
    • HEAD 只返回头部
  • HTTP/1.1
    • GET
    • POST
    • HEAD
    • PUT 上传文件
    • DELETE 删除文件

 

Cookie

having state by using Cookie

privacy issue,设置不能跨域设置Cookie。However,advertising companies can obtain info across sites.

 

 

Web Caches

proxy server

compare "adding bandwidth"(page 40) and "add cache" (Page 41)

关于带宽的问题:带宽无法使用100%,只能无限接近,因此越接近,造成的延迟越大。

通过Header中If-modified-since: <date> 决定

如果没有修改则返回304 Not Modified

  • Reduce response time for client request
  • Reduce traffic on an institution's access link
  • Internet dense with caches enables "poor" content providers to effectively deliver content

 

 

File Transfer Protocol (FTP)

 

common commands

  • USER username
  • PASS password
  • LIST
  • RETR filename
  • STOR filename

 

 

 

Electronic Mail

Simple Mail Transfer Protocol (SMTP)

port 25

major components

  • user agents
  • mail agents (mail server)
    • server
    • client
  • simple mail transfer protocol: SMTP
    • RFC 2821
    • Must be 7-bit ASCII

use TCP to reliable transfer email message from client to server

server to server is using SMTP
user agents to server is using POP3 IMAP or others.

 

Command:

  • HELO
  • MAIL FROM
  • RCPT TO
  • DATA
  • QUIT

 

Message Format: 

end of the letter use CRLF.CRLF (换行句号换行)
multimedia data use BASE 64 encoding (RFC 2045, RFC 2056)

 

Mail Access Protocols

  • POP
    • RFC 1939
    • authorization agent-server and download
    • only download, no changes in  receiver's mail server
  • POP3
    • download-keep, or download-delete
  • IMAP
    • more features
    • keep session
      • can mark something is important
      • keep folder
  • HTTP
  • POP3
    • command
      • user
      • pass
      • list
      • retr
      • dele
      • quit
    • stateless
      • download-and-delete mode / download-and-keep mode

 

 

 

Jan 26

materials: http://www.eecs.yorku.ca/course_archive/2016-17/W/3214/PPT/
[Page 39 do calculation, referring to PPT note page 1]

 

Domain Name System (DNS)

distributed database 为什么中心化DNS呢? 考虑到 single point of failure(单点失误), traffic volume(流量), distant centralized database(距离), maintenance(维护成本)

sent by UDP. application-layer protocol (why? we can do the resolve in the edge)

Function

  • Host name to IP
  • Host aliasing
  • Mail server aliasing
  • Load distribution

 

Distributed, Hierarchical Database

  1. Root DNS server
    • contacts authoritative name server if name mapping not know
    • get Mapping
    • returns mapping to local name server
  2. Top-level domain servers
    • responsible for 顶级域名
  3. Authoritative DNS server
    • 负责组织的域名

 

 

Local Name Server

  • Does not strictly belong to hierarchy
  • Each ISP has one
  • a host makes a DNS query, the query is sent to its local DNS server

 

Query methods

  • recursive query 递归查询
  • iterated query 轮询

Godaddy 有关的解释  |  Microsoft TechNet 的有关解释

 

DNS Records

RR format: (name, value, type, TTL)

  • A
  • NS
  • MX
  • CNAME

Update/Notify mechanisms using RFC 2136

 


3214W17L4.ppt

Attacking DNS

  • DDoS
    • Bombard root servers with traffic
    • Bombard TLD servers
  • Redirect attacks
    • Man in middle
    • DNS poisoning
  • Exploit DNS for DDoS
    • Send queries with spoofed source address: target IP
    • Requires amplification

 

Jan 31

3214W17L4.ppt

P2P File Sharing

All peers are servers = highly scalable

Architecture

  • no always-on server
  • arbitrary end systems directly communicate
  • peers are intermittently connected and change IP address

 

P2P centralized directory

  • has a centralized directory server
  • Single point of failure
  • Performance bottleneck
  • Copyright infringement

 

Query flooding: Gnutella (Wikipedia)
Overlay Network
Fully distributed
Bootstrap: how to get into the network [LS4 page 10]

 

Exploiting heterogeneity: KaZaA/eDonkey
assign client to certain "group-leader", the "group leader" communicates each others (类似迅雷离线下载)

successive (连续)

 

Overlays graph

  • Edges are TCP connection or pointer to an IP address
  • Edges maintained by heat-beat message
  • New edge(边)  established when a neighbour goes down
  • New nodes bootstrap (引导)
  • Structured(传统) vs. Unstructured (非定型类似DNS不涉及于本教学中)

 

 

 

File distribution time: client-server; Ignore selfish behaviour

  • 上传 U 下载 D
  • 服务器提供 U_s
  • 客户端提供 U_{1..i}D_{1..i} 共有 N 个客户
  • 文件大小 F

如果采用传统方式下载,下载时间 D_{traditional} \geq max\{NF/U_s , F/D_{min}\}

如果采用P2P分流,客户端承担一部分流量

D_{P2P} \geq max\{F/U_s , F/D_{min} , NF/(U_s+\sum U_i) \}

 

 

 

P2P file distribution: BitTorrent

  • Tracker: track peers participating in torrent
  • Torrent: group of peers exchanging chunks of a file

 

tit-for-tat (投桃报李,[[wikipedia]]  让新用户有机会加入)

  • requesting chunks:
    • at any given time different peers have different subsets of file chunks
    • periodically, the peer ask other peers for the list of chunks that they have
    • the peer request missing chunks from peers
  • sending chunks:
    • the peer sends chunks to those peers currently sending it chunks at highest rate
    • periodically select another peer, starts sending chunks (allow new peer to join)

 

Feb 2

graph structure of internet, graph 理论应用于这个项目之中
{老师花了很多时间在graph理论中}
built trust is very hard in a distributed system!
end LS 4 page 26

Distribute Hash Table (DHT)

wikipedia DHT  特点:

  • Distribute key-value pairs over millions of peers
  • Any peer can query database with a key
  • Each peer only knows about a small number of other peers
  • Robust to peers coming and going (节点加入和离开都没有什么影响)

Hash Table (如果标题相近,hash也相近(与安全领域的hash不一样)),assign key-value pair to the peer that has the closest ID(也就是说连接到最近的ID)。
Each peer only aware of immediate successor and predecessor.

DHT paradigm(范例)

Circular DHT and overlay networks [page31]

Peer churn

index the file with hash value, and also index the node with the same space. 寻找节点的时候,会查找相近的节点 Page 30. This is the query system only

n is the number of the node.

Page 32, node 60 has the list of file. 这是最基本的方式 take \Theta (n)
Each peer keep track of : predecessor, successor

Page 33, 加上节点的跳跃,这个算法可以优化到 \Theta ( \log (n))
Each peer keep track of : predecessor, successor, short cuts

 

Diameter(两个节点通信需要通过 最多 多少个节点) and Degree(单个节点到别的节点数) 直接可以有Trade off。

  • Extreme
    •  Diameter=n/2
    •  Degree=2
  • Extreme
    •  Diameter=1
    •  Degree=n-1
  • Mid
    •  Diameter = Degree = \Theta (\log (n))

 

Handle Peer churn

peer coming in and going out

  • each peer knows address of its two successors
  • each peer periodically pings its two successors to check aliveness
  • if immediate successor leaves, choose next successor as new immediate successor

 

Major problem DHT: Polluted files, Flash crowds, Freeloading

 

 

[Java code]

Feb 7

[queue.ppt] use the queue ppt 似乎是重点??

thread&operating system is not a part of the class

Packet Switching

delay 的来源

nodal processing: 保护防火墙安全方面的

 

 

Queuing Theory

Queuing Theory (Wikipedia), Queue FIFO (First-In-First-Out)  这门课为数不多的数学内容 {需要复习}

Example: Propagation(传播), Caravan(车队), Spatial(空间), packet transmission is more like transport traffic.

 

d_{nodal} = d_{proc} + d_{queue} + d_{trans} + d_{prop}

 

Single Queue 问题是本课研究的问题 (Black board 照片)

  • Thru put waiting
  • Ave queue length

 

Naming scheme of queues: X/Y/k/b

  • X = arrival process, (概率方式)Arrival Process  (X) (Poisson Distributed)
  • Y = service time process, (概率方式)Service Time Distribution (Y) (Exponential Distributed)
  • k = number of service stations,
  • b = length of buffer.

 

Markovian Distribution: wikipedia

 

uncorrelated probability (不相关性)

 

M/M/1/∞

Queuing Discipline (结构特性:FIFO队列 / Priority队列 / Fair Queue) [本节课重点讲述]

参见Wikipeida M/M/1 queue

M= Markovian

我们将要讲述的队列内容。

  1. The first M: Poisson arrival process.
    • k is number of packets
    • t is time
    • 这个分布是无穷的(unbounded tail)
    • Poisson is memoryless (泊松分布的特性)
    • P(N(t) = k) = \frac{(\lambda t)^k e^{-\lambda t}}{k!}
  2. The second M: Exponential inter arrival times
    • inter-arrival is exponential (两个包裹到达时间的间隔)
    • 由 Exponential built up Poisson distribution
    • P(x = t) = \mu e^{-\mu t}
  3. Under these assumption utilization:
    • Probability = \rho = \frac{\lambda} {\mu}

 

那么平均队列中任务的数量将会是 \bar{N} = \frac{\rho}{1 - \rho}

 

 

Little's Law

(in the mid term test)  MBA wiki 关于 利特尔法则的解释

公式: L = \lambda W

其中:

  • L , lead time, average number of customer in the system (long term)
  • \lambda , average arrival rate
  • W , the average time that a job spends in system
  • This should be a stable system. Long-term average.

 

结合上面的 M/M/1 queue可以对比地看

  • \lambda 出生率,enqueue rate
  • \mu 死亡率,dequeue rate

如果到达概率 \lambda 接近处理概率 \mu ,则效益达到100%,(队列中人数会达到正无穷)。所以这个系统的稳定条件是“死亡率大于出生率”( \mu > \lambda )。 When \lambda approaches \mu the number of jobs in the queue approaches infinity. 其实传输效率当然是 \rho 越大(越接近1)越好

基本上效果如图所示:

我们可以算出average delay seen by the packet (一项任务在这个队列中的平均等候时间)

T = \frac{\rho}{\lambda(1 - \rho)} = \frac{1}{\mu-\lambda}

 

 

Feb 9

what is thruput : through put is not effect by

[review record, Textbook page 259]

M/M/1/∞

  1. Analytical expression for delay etc. (what about thruput?)
  2. Output is "M" (Poisson distribute) as well. (Networks can be analyzed easily)

Traceroute

traceroute command, base on TTL, this time is use as "hop to leave"

 

 

Packet loss

if we have infinite queue, we don't need to consider the packet loss

因为爆发流量的原因,考虑 instantaneous traffic

 

 

Throughput

Rate (bits/time unit) at which bits transferred between sender/receiver

  • instantaneous: rate at given point in time 爆发
  • average: rate over longer period of time 平均

 

 

[Chapter 3 Part 1]

Transport Layer Service

we will discover the TCP congesting control

 

 

Multiplexing / Demultiplexing

  • demultiplexing : receive host, delivering received segments to correct socket
  • multiplexing: send host, gathering data from multiple sockets enveloping data with header (for demultiplexing)

host receives IP datagrams/ with address and port

java class - DatagramSocket

TCP socket need

  • source IP & Port
  • destination IP & Port

 

 

UDP

没有什么好说的(没有hand shaking),并不是一个稳定的连接

有Checksum 机制,可以基本保证包裹内数据没有错误

byte stream: 并不是说这个包是第几页,而是说这个包是开始于第几byte

简单网络管理协议(SNMP)和 域名系统(DNS)

 

Feb 14

VERY IMPORTANT
TCP Closing issue

 

TCP

  • point-to-point
  • reliable, in-order byte steam
  • pipe lined
  • send & receive buffers
  • connection-oriented
  • flow controlled

 

TCP 需要buffer (send buffer + receive buffer)

TCP segment structure (Page 23) each line is 4 bytes long (这张图很重要)

sequence number (the number of the bytes, not pages)

acknowledgement number (the next number of the bytes you expect, (下一页的页码)) ACK=n 表示自己已经收到0-n byte(待查)

ACK如果没有set,可以忽略 acknowledgement number

RST, SYN, FIN : SYN connection set up, RST and FIN disconnection

Receive window : that how TCP do flow control

 

 

TCP Round Trip Time

RTT (Round trip time)  的设置,要是超时了,就重新传输package。设置得太短或者太长都不行。

TCP 希望能够修正这个速度问题

ARMA model / Kalman Filters 但这里使用 Exponential weighted MA 。计算这个窗口需要一个动态的计算,因为网络延时会变化,所以最后几次测量需要赋予更高的权重。这个算法的几点

  • Exponential weighted moving average
  • influence of past sample decreases exponentially fast
  • \alpha = 0.25 应该算是一个Window size

 

数学过程:

EstimatedRTT = (1- \alpha) \times EstimatedRTT + \alpha \times SampleRTT

E_n = (1-\alpha)E_{n-1} + \alpha S_{n-1}

需要拆开这条公式的右边
E_n = (1-\alpha)[ (1-\alpha)E_{n-2} + \alpha S_{n-2} ] + \alpha S_{n-1}

 

EstimatedRTT = (1- \alpha) \times EstimatedRTT + \alpha \times SampleRTT

DevRTT = (1- \beta) \times DevRTT + \beta | SampleRTT - EstimateRTT |

DevRTT 应该算是波动值得计算,最后两式结合,可得:

TimeoutInterval = EstimatedRTT + 4 \times DevRTT

其中这里 \alpha\beta 都是smoothing factor, 起平滑线段作用。

 

TCP use single timer, 因为timer需要运算资源然后,使用offset计算包裹的时间。

 

ACK / Seq

本节课主要讲了 ACK / Seq 这个问题

  • ACK=n 表示从开始到第 n - 1 (everything up through byte n-1 )都收到了,下一个请从 n 开始发送
  • Seq=n 这是从第 n byte 开始

 

3ACKs 优化问题 (Fast Retransmit, Page36): If sender receives 3 ACKs for the same data, it supposes that segment after ACKed data was lost.

 

TCP Flow Control

Spare room  其实就是 Receive Window
Sender won't overflow receiver's buffer by transmitting too much, too fast.

 

Three ways handshake (page 42) Step 1,2 都不能有data, Step3可以附带上data

 

TCP Closing

FIN-->
<--ACK
<--FIN (Closing)
(Timeed Wait)ACK-->(Closed)
(Closed)

 

Feb 16

Midterm Everything up to today
[Chapter 3 Part 2]

 

SYN flooding attack

  • L: Client;
  • R: Server;

 

SYN-->

<--SYNACK ( Server allocated resources session)

ACK--> (because this is attacker. Attacker will not sent this package)

 

 

Performance of TCP congestion control

 

Performance Objectives:

  • link utilization
  • fairness
  • keep congestion down

 

怎样才公平,TCP才有什么政策达到公平?(电话,物理的邮件,采用均价的策略, Page2)

但是TCP,不知道这些东西(Page3)

 

TCP 的解决方案

  • Packet loss indicates congestion ( true for wire network , not for wireless )
  • Sensing congestion(检查堵塞) : timeouts, duplicate ACKs
  • Reacting to congestion: drastic decrease of sending rates (自己减速)
  • Recover from congestion:
    • continuous probing
    • conservative increase

 

记下来解决 what is drastic / conservative ? 这些程度怎么决定?

Additive (conservative) increase, Multiplicative drastic decrease of sending rates (AIMD)

TCP starts from LOW.  (保守地)

TCP Tahoe includes two modes

  • Slow Start Mode : low start fast increase; Multiplicative (aggressive) increase
  • Congestion avoidance mode: Additive (conservative) increase, multiplicative (drastic) decrease of sending rate

 

Page 8

这里开始采用,两种速度递增模式 (前面的是理想的形式)

ss_thresh :(Threshold,阀值) current estimate of the bandwidth of current network

Threshold = \frac{Congestion Rate}{2}

 

TCP Series 2 Reno

修正 Page 9 (loss -> timeout)

之前的协议只考虑Package loss,但是这个开始考虑 timeout 和 duplicate ACK

 

Page 10

修正 Page 10  (number of packages -> number of bytes)

Transmission rate = \frac{W \times Packet Size} {RTT}

self-clocking

 

Page 13 [重点]

Fairness & Utilization Trade Off (怎么样才公平?)

TCP Performance

similar to ECON 1000

 

Even though the connection started at low, if the session is long enough, the bandwidth will be allocated fairness.

A-Additive  M-Multiplicative

  • AIMD (is the only one that leads to fairness)
  • MIMD
  • MIAD
  • AIAD

 

This solution will give up  1/4 bandwidth 因为在浮动中(fluctuation), bandwidth only use 3/4 , 求导可得 (refer to page 15)

 

Page 14

Once the trajectory hits x=y line, it stays there.

 

  • Online Algorithm (因为不能够一次性获取全部数据,所以在算法上有限制,don't know the future but not the past)
  • Stream Algorithm (在Online Algorithm 至上,don't know the future and don't know the past)

TCP 需要使用 online algorithm 这个model

 

 

TCP/IP Design issues

  • Co-operative algorithm (因为没有检查机制,所以考大家的合作)
  • Policing is hard to do(没法做监控)
  • Tracing of malicious hosts/users difficult

 

 

Feb 28

This chapter will introduce the principle and then see how it works
simple core and complex edge (philosophy)
network layer 上层是  transport layer

这节课主要讲了Router的构造

Network Layer

All the thing can be done in network, but follow the philosophy.

All the thing in the network layer is unreliable. 在自己的网络中可以做任何事情,可以提高network layer的可用性,做QoS。但是根据 simple core and complex edge 这个设计理念,所有在Network layer的东西都是不可靠的。

 

the difference between forwarding and routing : {待查}

Virtual circuits

shorter packet headers: 这个理论上IPv4比IPv6好,因为小。

 

Addressing

Page11 ,注意第二第三,第二是更加小的范围,但是在第三的范围内

因此一个在地点 A的人想拿B地的IP是不需要改很多routing table,所以基本上不可能

 

 

ATM(Asynchronous Transfer Mode): is complex in core.

Switching fabric(布)

 

Input Port Function

3个解包过程

  • Physical layer:
  • Data link layer:
  • part of the network layer: is this centralized or decentralized. 每个networking 都要一点的运算资源。贵的话每一个线程都有独立的运算的队列。

Page 16

memory:

  • 这个是 centralized 的解决方案

bus:

  • 这个是  decentralized 的解决方案,因为每个节点都要确保线路没有被占用
  • 只能一个人在说话,因为shared media。
  • 同一个bus里面的人都能听到( 这个可能是优点,能知道别的设备 are busy

cross-bus

  • works for every permutation simultaneously (排列,同时)
  • \Oh (n \log( n ) )

 

 

bus contention: switching speed limited by bus switchers

 

Banyan network: any input will have a binary tree connected   \Theta (n \log( n ) )

wikipedia (Banyan switches)

(查录音) How to optimize:

  • jumping queue
  • hot spot, randomize

 

 

Output Port

output queuing,same as the input, because we have queue, queue might be filled up.

If filled up, then  it is possible to drop packet. If you don't want to drop packet, some signal must be implemented.

 

Optimization for high end router

  • Head of the line blocking: 当然你可以看Queue 里面更多的packet,通过看看其他的包裹进行优化
  • Fabric slower than input ports combined. queueing may occur at input queue

because of queuing, the order of the packet might be changed.

 

March 7
We started from IPv4

source routing

how much overhead with TCP? 40byte (你即使发送1byte内容,那么也要发41byte)

 

Page 27

可以拆分packet

header length includes 40 bytes header.
fragflag = 0 则数据接收完毕
offset 类似 Seq

 

Page 29

subnet

___.___.___.___/8   Class One
___.___.___.___/16  Class Two
___.___.___.___/24  Class Three

 

CIDR: Classless InterDomain Routing

___.___.___.___/x
the x can be any number now. not necessary to have 8n = x
x is # bits in subnet portion of address

 

DHCP: Dynamic Host Configuration Protocol

 

How to get one IP address

例如:ISP KDDI有 106.185.0.0/17, 分配给Linode 106.185.43.0 / 24

 

ICANN: Internet Corporation for Assigned Names and Numbers

 

 

NAT

  • Security
  • Efficient (re-use) of IP addresses

Simply rewrite the port number

 

 

ICMP

This message used by hosts & routers to communicate network level

ping uses ICMP

QoS problem

 

 

IPv6

Structure

Page 49----

 

 

March 9

The messages are peer to peer, so that the message will not be sent to the server. But it will go to the other peer direct.
"The peers need not to be concurrent." means one peer can only communicate with one peer at a time? YES.
No Group Chat
Directory server do not have responsibly for the actual availability of the client.

 

IPv6 Tunnelling

Take the IPv6 packet but put it into IPv4 packet.

Router need to know the tunnelling route

 

"link state" algorithms. [[最小路径法]]

 

"distance vector" [[distribution implementation of Bellman-Ford Algorithm]]
never end. keep tracking the changes of the network.
Poisoned Reverse. It avoid if some route is highly delayed.
Good news(low delay) travels fast but bad news(high delay) travels slow.....

 

Autonomous System

Wikipedia: Autonomous system

 

 

Intra-AS Routing on the Internet

 

RIP: Link Failure and Recovery

it is too simple. it sends only one path

ping-pong loops: poisoned reverse

 

OSPF "advanced" features not in RIP.

This method is inside the AS

 

 

Inter-AS  Routing on the Internet

BGP only one

  • OPEN
  • UPDATE
  • KEEPALIVE
  • NOTIFICATION

 

 

 

Multimedia Networking

Issue

  • No QoS support
  • available capacity
  • delay (loss)
  • jitter (variation of the delay)
  • mobility
  • heterogeneity

 

  • Quantization   (Trade off the audio signal amplitude,模拟信号数字化)
  • Sampling   (Trade off on "time" axis)

This is not compression at all.

 

Compression

  • compression - lossy
    • 丢失一定数据
  • compression - lossless
    • 不丢失数据

 

PCM

Video

coding: use redundancy within and between images to decrease # bits used to encode image

  • spatial
  • temporal

 

MPEG https://zh.wikipedia.org/wiki/MPEG

RTP: multimedia payload.

 

March 16

 

  1. Encode at different qualities (frame sizes, rates)
  2. Encode the video to different streams
    For example 1,2,3,4. Those who want to lowest quality, use stream 1. Those who want more, use stream 1 and steam 2.

Streaming multimedia:UDP

Streaming multimedia:HTTP

larger payout delay

Streaming multimedia:DASH

  • server:
    • divides video file in to multiple chunks
    • each chunk stored,
  • client: (different standard : HLS / HDS)
    • periodically measure server-to-client bandwidth
    • consulting manifest requests one chunk at a time

 

Content distribution networks (CDN)

  1. 如果是单点的: single large "mega-server" (w/o CDN)
    • single point of failure
    • point of network congestion
    • long path to distant clients
    • multiple copies of video sent over outgoing link
  2. 如果是用CDN: w CDN
    • store/serve multiple copies of videos at multiple geographically distributed site
    • enter deep: push CDN servers deep into many access networks (close to the users)
    • bing home:
      • limelight

 

study case: netflix

 

 

Voice-over-IP VOIP

IMPORTANT

VoIP end-to-end delay requirement: needed to maintain conversational

characters

packet loss slide

VoIP may use fixed layout delay.

 

Adaptive play-out delay

d_i = (1 - \alpha) d_{i-1} + \alpha (r_i - t_i)

usually choose \alpha = 0.1

 

Bloom filters: if origin has k chunks, generate k+m chunks such that ANY k chunks is sufficient.

add lower version of packet 1 to packet 2

 

Skype

a little after than the

 

March 21

 

Protocols for real-time conversational applications: RTP, SIP

Jitter

RTP SIP

Research project. Unsolved open problem.

RTP: Real-Time Protocol

RFC 3550
在Transport Layer,但是基于 TCP。

Not provide QoS.

routers provide best-effort service.

RTCP for control

 

 

SIP: Session Initiation Protocol

VoIP

RFC 3261

long-term vision

how to address a callee. no matter what IP device callee is currently using.

service: Page 5-54

GSM/PCM 格式。。。

example of SIP message

SIP registrar message (need SIP server) like DNS server

 

 

H.323

works with RTP, more like telephone.

 

 

 

next chapter7.5

March 23

QoS

Think: How to do QoS for different class of traffic?

 

Dimensioning best effort networks

call admission

Scheduling and policing mechanisms

Page7-72

sometimes have different queue

  1. Round Robin Scheduling
  2. Weight Fair Queuing (Important)

 

Policing (监控参数)

  • (long term) average rate
  • peak rate
  • (max.)burst size

 

如果获取参数?

 

可以使用Token,获取Token之后才能发送数据

QoS

Edge router, Core router have different solutions

Page 7-80

rt+b

 

TOS (Type of service)

PHB (Per hub behaviour)

Forwarding PHB

RSVP (protocol, call setup, call admission, signalling)

 

Finishing this chapter. Multimedia Networking: Summary.

Different service

DONE.

 

Next topic: security.

 

 

 

March 28

HW 3 (Paper design only)
Internet Access Monitor
not more than three pages

  • how to monitor Internet access?
  • some security aspect

 

 

 

Network Security

  • confidentiality
  • authentication
  • message integrity
  • access and availability

 

Man In The Middle Attack

\text{plaintext} \rightarrow \text{cipher text} \rightarrow \text{plaintext}

Breaking an encrypting scheme

 

Symmetric key cryptography
two people share same key

 

DES: Data Encryption Standard
US encryption standard NIST 1993
DES Challenge: 56-bit-key-encrypted phrase decrypted (brute force) in less than a day
3DES: Encrypt 3 times with 3 different keys

cipher block chaining: 将第一部分加密的结果链接到第二部分一同进行加密

 

Public Key Cryptography
Key exchange : Wikipedia
crypto systems

  • public encryption key known to all
  • private decryption key known only to receiver

 

 

RSA algorithm
Wikipedia
Public key encryption algorithms
modular arithmetic
(a \mod n)^{d} \mod n = a^d \mod n

  1. choose two large prime numbers p and q
  2. compute n = pq and z = (p-1)(q-1)
  3. choose e (with e<n ) that has no common factors with z
  4. IMPORTANT choose d such that ed-l is exactly divisible by z . (in other word: ed mod z = 1 )
  5. public key is (n,e). private (n,d)

I tell you n , but you cannot figure out p and q

 

 

March 30

 

RSA: Creating public/private key pair

  1. given (n,e) and (nod) as computed above
  2. to encrypt message m (<n), compute
  3. to de

[Page 8-23]

[Page 8-24] 错了

 

c^d 的运算时间复杂度为 \Big-oh (\log(d) ) 在优化的情况下。

DES is at least 100 times faster than RSA

 

Authentication

playback attack

  • Goal - avoid playback attack
  • ap4.0 ap5.0 Bob does not have a security way to obtain public key

 

 

Digital signature

cryptographic technique analogous to hand written signatures

不能全部使用RSA架构,因为加密会变得很大,因此使用 Message digests

Even a slight difference on file, the Hash of those files should change drastically.

 

[Page 8-49]

H(m) is a shorter version

Graph is important

 

SSL Certificate

MAC key

 

Toy: key derivation

 

 

April 4

SSL package format (记忆)

MAC 的含义不一样!!!

https://en.wikipedia.org/wiki/Message_authentication_code

length data MAC

Page[Network Security 8-68]

SSL cipher (cipher 读:赛fer)

 

SSL handshake

server authentication
nonce (means: onetime use)

 

 

IPsec & VPN

IPsec 有很多方案

 

Service modes

  • AH
  • ESP (commonly use)with AH, additional provides (查)

 

Host mode / Tunnel mode + AH / ESP [Page 8-89]
其中 Tunnel+ESP 最常用

 

need to maintain state information

SA - SAD
用于登陆用户的验证
IPsec datagram 设计 中加入了更多的信息

SPD

IKE Internet Key Exchange

  • PSK
  • PKI

IKE also contains key exchange.

 

wireless

 

Firewall

  • prevent DDoS
    • SYN flooding, first packages int TCP handshake
  • prevent illegal modification/ access of internal data
  • allow only authorized access to inside network
  • three types of firewalls

 

第一种 Stateless packet filter

Some rules as example
ICMP floor (以往常见的攻击)
Just look at the header to filter

 

第二种 Stateful packet filter

can look into the state of the connection
can do timeout control

 

第三种 Application gateways

For Assignment3, we need to consider we should not use such a powerful server.

 

 

Intrusion detection system

deep packet inspection

examine correlation

  • port scanning
  • network mapping
  • DoS attack

Machine learning for normal model for the network.

 

 

 

这篇博文发表在 专业笔记 目录下,标签为 , , ,
版权所有,请勿转载。如需引用,请使用链接:https://note.masterchan.me/?p=1458

您的邮箱地址不会被公开,评论使用Gravatar头像。
Your email address will not be published. This blog is using Gravatar.

正在提交评论...
正在为您准备评论控件