COMP211-W6

Lec 7 Physical Layer

Goal

  • learn some basic communications theory
  • get to know different types of transmission media

Lec 8 Network security

Goal

  • 私密性: 发送密文
  • 可认证性
  • 完整性

8.1 Introduction

什么是网络安全

  • 私密性: 发送密文
  • 可认证性: 双方确认身份
  • 完整性: A -> B 确保报文没有任何篡改
  • 访问控制和服务的可用性: 如果b的服务受到攻击就无法访问
  • 违反以上既不可达成网络安全

如何让 A & B 成功安全通信

  • A & B

  • 路由器: OSPF 协议

坏蛋

  • 窃听
  • 插入
  • 劫持: 在通过认证身份之后伪造通信
  • 伪装
  • 拒绝服务

加密语言

  • 加密
  • 明文
  • 密文
  • 解密
  • 密钥
  • 对称加密体系 & 公开密钥加密体系

    8.2 对称加密体系: 加密和解密密钥一致

将一个替换为另一个

  • 可能数据: 26!
  • 字频 & 词频 来提高效率
  • 发送方加密: KA.B(m)
  • 接收方揭秘: KA.B(KA.B(m))
  • 问题: key的分发

Symmetric key crypto: DES

  • 提高安全性
    • 3DS
    • 成串加密: 当前要加密的明文R与(R-1)进行XOR计算后加密

AES

![](https://pic.imgdb.cn/item/61da0b6c2ab3f51d9172196f.png)
  • 将data化为128bit 的密钥
  • 128, 192, 或者256 bit 密钥
  • 加密强度非常强

块加密


  • 64bit 分成8个8bit小块
  • T1到T8的组合

密码块链


  • 输入块冲刺将得到相同的密文

8.2 公开密钥加密体系

公开密钥加密体系

  • 在网上下载公钥证书
  • 私钥自我保留, 公钥公开
  • 公钥推出私钥时间太久了

    公钥加密算法

    RSA: 选择密钥

  • example
  • another important property

模运算

  • 10进制:计算余数
  • 2进制:异或

解密的几种模型

  • 加密算法已知求密钥
  • 加密算法和密钥未知
  • 唯密文攻击
  • 已知明文攻击
    • 一致部分蜜文和明文关系
  • 选择明文攻击
    • 攻击者选择一段明文并得到密文

8.3 Authentication

Goal: Bob wants Alice to “prove” her identity to him

  • Protocol ap1.0
    • 完全没有加密
  • Protocol ap2.0
    • 加上IP address
  • Protocol ap3.0
    • 加上IP address & password
    • 重放攻击 play back
  • Protocol ap4.0
    • avoid playback attack
    • number(R) used only-in-a-lifetime
    • to prove Alice “live”, Bob sends Alice nonce, R
      • Alice must return R, encrypted with shared secret key
  • Protocol ap5.0
    中间攻击

8.4 Integrity

接收方要确保报文没有被修改

  • 可验证性 - 可验证性
  • 不可伪造性 - 接收方
  • 不可抵赖性 - 第三方

    Digital signatures 数字签名


报文摘要 Message digests

![](https://pic.imgdb.cn/item/61da3e842ab3f51d91889ef6.png)
将长报文进行精简

报文摘要不容易得到原报文 

m & K<sub>B-</sub>(H(m))

互联网 checksum: poor crypto hash function

不同的报文可能有一样的校验值

散列函数算法

可信赖中介 - Public key Certification Authorities(CA)

8.5 Security in internet protocol stack

Secure e-mail: confidentiality

  • confidentiality

  • integrity, authentication

Pretty good privacy(PGP)

TLS



8.6 WIFI secutity

802.11: authentication, encryption




展开全文 >>

COMP207-P3

T5

Checkpoints

Overview

advatages of chekpoints:

  1. faseter recovery
  2. less space for log-file

Simple Checkpointing(for undo logging)

  1. 在日志中记录checkpoint_start (T1,T2…Tn) (Tx代表做checkpoint时，正在进行还未COMMIT的事务）
  2. 等待所有正在进行的事物 commit
  3. 在日志中记录checkpoint——end

  • 借助checkpoint进行回滚·

    从后往前扫描undo log

    1. 如果先遇到checkpoint_start, 则将checkpoint_start之后的所有未提交的事务进行回滚；
    2. 如果先遇到checkpoint_end, 则将前一个checkpoint_start之后所有未提交的事务进行回滚；（在checkpoint的过程中，可能有很多新的事务START或者COMMIT)。

Recovery via Simple Checkpoints


ARIES Checkpoints

Recovery via ARIES Checkpoints

Being able to recover

Conflict-Serialissability vs Recovery

No good solutions to the problem

Dirty Reads

Cascading Rollback

Isolation vs Durability

Recoverable Schedules

Can still do cascadinng rollbacks, but only active transactions can be forced to abort

Example

Recoverable Schedules - implicit assumption(隐含假设)

No cascading-rollbacks!

Overview

Cascadeless schedules

Recover schedules still cascades

Cascadeless Schedules


Example

Cascadeless Schedules: Properties

Can cascading Aborts & Serialisability both?

Strict Schedules

A schedule is strict if each transaction in it reads and writes only values that were written by transaction that have already committed
如果调度中的每个事务只读取和写入已经提交的事务写入的值，则调度是严格的


Strict Two-phase Locking(Strict 2PL)

Example



Strict Two-Phase Locking Enforces Conflict-Serialisable & strict Schedules

Example for serializable schedules

Still … Risk of Deadlocks

Strict 2PL and Deadlocks

Detecting deadlocks

Strict 2PL and Deadlocks

Deadlock Detection: Approaches

Timestamps for Deadlock Detection

How Are Timestamps Used

Wait-Die Scheme

Wound-Wait Scheme



Timestamp based schedules

Deadlock prevention

Two approaches for deadlock prevention:

  • Detect deadlock & fix them
  • Enforce deadlock-free schedules

Basic Idea

计划事务，以便其效果与在每个事务启动时立即执行相同。

Timestamp-Based Schedulers

Timestamps

展开全文 >>

COMP211-W5

Lec6-Link Layer 链路层和局域网

Goals

  • Understand principles behind link layer services:
    • error detection, correction
    • sharing a broadcast channel: multiple access(多点接入)
    • link layer addressing
    • local area networks(局域网): Ethernet, WLAN
    • 可靠数据传输,流量控制
  • instatiation, implementation of various link layer technologies

    Review:

    • 网络层以一个子网为单位作为路由
    • 最长路由匹配
    • 子网内部:主机和主机如何沟通? —— 链路层来解决

      特例

    • 点到点链路(广域) & 多点链路(局域) 多个设备连接一个ip — 引出多点接入的问题
    • 无线链路出错率要比有线链路出错率要高
    • 局域网的访问控制
    • 多点链路会在广域上造成碰撞最后损失

Introduction

terminology:

  • hosts and routers: nodes
  • communication channels that connect adjacent nodes along communication path: links
    • wired
    • wireless
    • LANs
  • layer-2 packet: frame, encapsulates datagram

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

  • datagram transferred by different link protocols over different links:
    • e.g., WiFi on first link, Ethernet on next link
  • each link protocol provides different services
    • e.g., may or may not provide reliable data tranasfer over link

transportation analogy:

  • trip from Princeton to Lausanne
    • limo: Princeton to JFK
    • plane: JFK to Geneva
    • train: Geneva to Lausanne
  • tourist = datagram
  • transport segment = communication link
  • transport mode = link-layer protocol
  • travel agent = routing algorithm
  • framing, link access:
    • encapsulate datagram into frame, adding header, trailer
    • channel access if shared medium
    • “MAC” addresses in frame headers identify source, destination (different from IP address!)
  • reliable delivery between adjacent nodes
    • we already know how to do this!
    • seldom used on low bit-error links
    • wireless link: high error rates
      • Q: why both link-level and end-end reliability?

  • flow control:
    • pacing between adjacent sending and receiving nodes
  • error detection:
    • errors caused by single attenuation, noise.
    • receiver detects errors, signals retransmission, or drops frame
  • error correction:
    • receiver identifies and corrects bit error(s) without retransmission
  • in each-and-every host
  • link layer implemented in network interface card(NIC) or on a chip
    • Ethernet, WiFi card or chip —— (CPU)
    • implements link, physical layer
  • attaches into host’s system buses
  • combination of hardware, software, firmwawre

Interfaces communicating

Error Detection, correction

Error detection

EDC: error detection and correction bits (e.g., redundancy)
D: data protected by error checking, may include header fields

数据检查并非百分百可靠

Parity checking

Internet checksum (review)

Cyclic Redundancy Check(CRC)

CRC example


3. 两边同除G得到余数 «R=

Mulitple access protocols

A day in the life of a web request

Synthesis: a day in the life of a web request

A day in the life: scenario

A day in the life: connecting to the Internet


A day in the life … ARP(befor DNS, before HTTP)

uisng DNS

TCP connection carrying HTTP

HTTP request/reply

展开全文 >>

COMP207-P2

T3 transaction management

Introduction to transactions

Overview

Transaction

  • A sequence of queries

The complication arises from that many might happen at the same time and that computers can fail…

Executing SQL Queries in “Real Life”

In parctice, problems may arise due to

  • Concurrency(并发性): SQL statements that overlap in time
  • Partial execution of SQL statements(e.g., due to failures)

Problem 1: Concurrency

如果第一位乘客订过这个座位后面的人就没法再定这个座位了

Transactions to Rescue

SQL allows us to state that a group of SQL Statements must be executed so that no conflicts arise

Problem 2: Partial Execution

Acounts(accountNo, accountHolder, balance)
Goal: transfer 100 gbp from account ‘123’ to account ‘456’

Transactions to the Rescue

SQL allows to state that a transaction must be executed atomically(as a whole or not at all)

Transactions in SQL - Summary

Transaction in SQL: a sequence of SQL statements

Schedules, a low-level view and notation

Overview

Introduce a simplified and lower level view of transaction as well as schedules and notatios for all of these

Translating SQL into Low-level Operations

Employees(e_id, first_name, last_name, birth_day, salary)

Simplifying Low-level Operation

Basic Operations of Transactions

read(X): Reads a database item X into a program variable (also named X, for simplicity)

  • Find the address of the disk block(page) that contains item X
  • Copy that disk block into a buffer in main memory
    • if that disk block is not already in some main memory buffer
  • Copy item X from the buffer to the program variable X

write(X): Writes the value of program variable X into the database item named X

  • Find the address of the disk block(page) that contains item X.
  • Copy that disk blok into a buffer in main memory
    • if that disk block is not already in some main memory buffer
    • Copy item X from the program variable X into its correct location in the buffer
    • Store the updated block from the buffer back to disk either immediately or at some later point in time.

Transactions(in general)

A logical unit of processing using access operations

  • Begin
  • End (Begin/end are are omitted when the beginning/end of a transaction are understood)
  • read
  • write
  • +other non-databse operation

Schedules

Schedules hold many transactions for execution
The operations making up the transactions are then executed by the schedule in some order

  • It mus preserve that the operation in each transaction happens in the right order!

Two types:

  • Serial Schedules
    • Exectutes the transactions one after another
    • Concurrent Schedules
      • Can Interleave operation from the transactions (while still preserving that the operations in each transaction happens in the right order) - formally speaking, a serial schedule is therefore also concurrent…

A Serial Schedule

Executes all operations in transaction T1,
then all operations in transaction T2.

For simplicity we will typically ignore
the non-database operations…

Shorthand Notation for Schedules

Another Example

Sb: r1(x); w1(x); c1; r2(x); w2(x); c2

Order matter

Concurrent Schedule

Summary

ACID in details

Overview

  • Atomicity
  • Consistency
  • Isolation
  • Durability

A - Atomicity

A transaction is an atomic unit of processing

  • An indivisible unit of execution
  • Executed in its entirety or not at all

Deals with failure(“aborts”)

  • User aborts transaction
  • System aborts transaction
  • Transaction aborts itself
  • System crashes, network failure

Abort - an error prevented full execution

  • we UNDO the work done up to the error point
    • System re-creates the database state as it was before the start of the aborted transaction

Commit - no error, entire transaction executes

  • The system is updated correctly

Atomicity is broken

C - Consistency

A correct execution of the transaction must take the database from one consistent state to another

  • Weak version: Transactions may not violate constraints(tyoical definition)
  • Strong version: It should correctly transfor the database to reflect the effect of a real world event(ISO/IEC 10026-1:1998)

Consistency is tricky

From definition:

A correct execution of the transaction must take the database from one consistent state to another

Transactions Preserce Consistency

I - Isolation

A schedule satisfies isolation iff it is serializable (I.e. like last slide: the effect of a serializable schedule is the same as some serial schedule)

  • Note: consistency is not really defined by serializable
  • A schedule is serializable iff it satisfies isolation

Weakening isolation



D - Durability

Once a transaction commits and changes the database, these changes cannot be lost because of subsequent failure

  • Once a transaction commits and changes the database, these changes cannot be lost because of
    subsequent failure
  • But could be ovwewritten by a later update
  • We REDO the transaction if there are any problems after the update
  • Durability deals with things like media failure

Some relational DBMS Components

Transaction - ACID Properties

Schedules that behaves nearly serial

Overview

how much concurrency can be allowed while still being close enough to serial schedule

Schedules - Two Extremes

Serial Schedules

  • execute correctly
  • maintain consistency of the database
  • infficient in multi-user enviroment(because transactions have to wait until others are finished)

Concurrent Schedules(non-serial)

  • may not execute correctly
  • may not guarantee consistency of the database or isolation
  • efficient in multi-user environments(if you get asked to do something, just do it)

A Serial Schedule

A Concurrent Schedule

Efficiency: Say that this table denotes arrival time of
the commands (and that each commands takes 1 time
unit)

Concurrent Schedule not always equilent to a serial Schedual

Basic Operation of Transactions

read(X): Reads a database item X into program variable(also named X, for simplicity)

  • Find the address of the disk block(page) that contains item X
  • Copy that disk block into buffer in main memory
    • if that disk block is not already in some main memory b
  • Copy item X from the buffer to the program variable X

write(X): Writes the value of program variable X into the database item named X

  • Find the address of the disk block (page) that contains item X.
  • Copy that disk block into a buffer in main memory
    • if that disk block is not already in some main memory buffer.
    • Copy item X from the program variable X into its correct location in the buffer
    • Store the updated block from the buffer back to disk either immediately or at some later poin

Concurrent Schedules Do Not Guarantee Consistency or Isolation

Serializable Schedules

A schedule S is serializable if there is a serial schedule S’that has the same
effect as S on every initial database state.

Serializable schedules are essentially those schedules
that we are looking for!

Guarantee:

  • Correctness and consistency(because serial schedules do)
  • Does not satisfy isolation, but we could fix that

Problem: serializability is difficult to test

  • Does not only depend on reads, writes, and commits, but also on the non-database operations
  • Non-database operations can be complex

Conflict-serializable schedules

Overview

Serializable schedules are too complex, so what is DBMS doing instead?

Conflict-Serializability

Stronger form of serializability that is used/enforced by most commercial DBMS

Based on the notion of a conflict.

Conflict - Characterisation

A conflict in a schedule is a pair of operations

  1. from different transactions
  2. that access the same item
  3. and at least one of them is a write operation

Conflict-Serializability

Two schedules S and S’ are conflict-equivalent if S’ can be obtained from S by swapping any number of (1) consecutive (2) non-conflicting operations from (3) different transactions

A schedule is conflict-serialisable if it is conflict-equivalentto a serial schedule.

Schedules

Example

Summary

Recognizing a conflict-serializable schedule

Overview

recognize conflict-serializable

Precedence Graph

The precedence graph for a schedule S is defined as follows:

  • It is a directed graph
  • Its nodes are the transactions that occur in S.
  • It has an edge from transaction Ti to transaction Tj if there is a conflicting pair of operations op1 and op2 in S such that
    • op1 appears before op2 in S
    • op1 belongs to transaction Ti
    • op2 belongs to transaction Tj

Testing Conflict-Serializability

Implication of a cycle

Summary

T4

Locking conflict-serializable

Overview

how conflict-serializable schedules

Transaction Scheduling in a DBMS

Simple Locking Mechanism

A transaction has to lock an item before it accesses it.

Locks are requested from & granted by the scheduler:

  • Each item is locked by at most one transaction at a time
  • Transactions wait until a lock can be granted

Each lock has to be released(ublocked) eventually

Schedules With Simple Locks

Extend syntax for schedules by two operations:

  • Ii(X): transaction i requests a lock for item X
  • ui(x): transaction i unlocks item X

Example:

May Not Be Serializable


Two-Phase Locking(2PL)

Simple modification of the simple locking mechanism that guarantees conflict-serializability

Two-phase locking(2PL) condition
In each transaction, all lock operations precede all unlocks (所有锁定操作优先于解锁操作)

Test a transaction for 2PL

Find first unlock

  • Phase 1 is up to, but not including, that unlock
  • Phase 2 is from unlock until the end

Transaction is 2PL iff phase 2 contains no lock


Summary

2PL ensures conflict-serializability

Overview

2PL schedules are conflict-serializability

Two-Phase Locking(2PL)

Simple modification of the simple locking mechanism that guarantees conflicy-serializability

Two-phase locking(2PL) condition:

In each transaction, all lock operations precede all unlocks

2PL Ensures Conflict-Serializability

If S is a schedule containing only 2PL transactions, then S is conflict-serializable
Proof idea




More flexible locks

Overview

Still Some Issues

2PL ensures conflict-serializability, but might lead to

  • Deadlocks: transactions might be forced to wait forever
  • other issues

Risk of Deadlocks

Different lock modes make 2PL more flexible

Shared & Exclusive locks

Schedules With Shared/Exclusive Locks

Problems With “Upgrading” Locks

Update Locks to the Rescue

Update lock:

  • Requested by transactions to read an item - Operation: u-lock(X) or uli(X)
  • May be upgraded later to an exlusive lock(shared locks can no longer be upgraded)
  • Granted to at most one transaction at a time

New upgrading policy:

Example 1: Avoiding the Deadlock


Example 2

Two-Phase Locking(2PL) with Shared/Exclusive/Update Locks

Straightforward generalisation:

In each transaction, all lock operations (i.e., shared, exclusive, or update lock requests) precede all unlocks

Locks With Miltiple Granularity

DBMS may use locks at different levels of granularity

  • May lock relations
  • May lock disk blocks
  • May lock tuples

Examples:

1
2
SELECT name FROM Student WHERE studentID = 123456;
SELECT avg(salary) FROM Employee;

Trade-Offs

Locking at too coarse granularity:

  • Low overhead (don’t need to store too much information)
  • Less degree of concurrency: may cause unnecessary delays

Locking at too fine granularity:

  • High overhead: need to keep track of all locked items
  • High degree of concurrency: no unnecessary delays

Need to prevent issues such as the following
to guarantee (conflict-) serialisability:

  • A transactions holds shared lock for a tuple.
  • Another transaction holds exclusive lock for the relation.

Intention Locks


Policy for Granting Locks

Summary

Why Might a Transaction Abort

Some relation DBMS Components

Why Might a Transactino Abort

Errors while executing transactions

  • Violation of integrity constraints, other run-time errors

Problem 1: Concurrency

Why Might a Transaction Abort

Deadlocks

Why Might a Transaction Abort

Beyond the DBMS’s Control


Summary

Undo Logging for database

  • undo log是把所有没有COMMIT的事务回滚到事务开始前的状态，系统崩溃时，可能有些事务还没有COMMIT，在系统恢复时，这些没有COMMIT的事务就需要借助undo log来进行回滚
  • 使用undo log时，要求：
    1. 记录修改日志时，(T，x，v）中v为x修改前的值，这样才能借助这条日志来回滚；
    2. 事务提交后，必须在事务的所有修改（包括记录的修改日志）都持久化后才能写COMMIT T日志；这样才能保证，宕机恢复时，已经COMMIT的事务的所有修改都已经持久化，不需要回滚。
  • 使用undo log时事务执行顺序
    1. 记录START T
    2. 记录需要修改的记录的旧值（要求持久化）
    3. 根据事务的需要更新数据库（要求持久化）
    4. 记录COMMIT T
  • 使用undo log进行宕机回滚
    1. 扫描日志, 找出所有已经start, 还没有commit的事物
    2. 针对所有commit的日志, 根据undo log来进行回滚

      Overview

      handle failure using undo log

Logging in DBMS

Idea: write important activities to a log so that a desired database state can be recovered later

Examples of important activities:

  • Starts of transactions, commits, aborts
  • Modification of database items

Should work even in case of system failures!

Techniques:

  • Undo logging (for maintaining Atomicity)
  • Redo logging (for maintaining Durability)
  • Combinations thereof (specifically Undo/Redo for doing both Atomicity and Durability)

Extension of Transaction Syntax




Undo Logging

Undo Logging: Procedure

  1. If transaction T updates item X and the old value was v, then<T, X, v> must be written to the log on the disk before X is written to disk.
  2. If transaction T commits, then must be written to disk as soon as all database
    elements changed by T have been written to disk

Example

Scenario 1

Scenario 2

Scenario 3

Recovery With Undo Logs

Example of Unndo Logging

If a Transaction Aborts

Summary

Other kinds of logging

Overview

other kinds of logging how to get atomicity and durability from logging

Redo Logging

redo log是指在回放日志的时候把已经COMMIT的事务重做一遍，对于没有commit的事务按照abort处理，不进行任何操作。

  • 使用redo log时, 要求

    1. 记录redo log时，(T,x，v）中的v必须是x修改后的值，否则不能通过redo log来恢复已经COMMIT的事务。
    2. 写COMMIT T日志之前，事务的修改不能进行持久化，否则恢复时，对于未COMMIT的操作，可能有数据已经修改，但重放redo log不会对该事务做任何处理，从而不能保证事务的原子性。

  • 使用redo log时事物执行顺序:

    1. 记录START T
    2. 记录事物需要修改记录的新值(要求持久化)
    3. 记录COMMIT T(需要持久化)
    4. 将事物相关的修改写入数据库

  • 使用redo log重做事务

    1. 扫描日志, 找到所有commit事务
    2. 对已经commit的事物, 根据redo log重做事务

Redo Logging: Procedure


Example

Recovery With Redo Logs

Example


Undo/Redo Logging

Example with Undo/Redo Logging

Undo without Redo

Redo without Undo

Ensuring atomicity and durability

展开全文 >>

COMP219-P2

Lec10-overfitting and K-Nearset Neighbour

Topic

  • Overfitting
  • K-NN classification

Regression using polynomial

General phenomenon

Ovwefitting in decision trees

Prevent overfitting

  • cause: training error and expected error are different
    • there may be noise in the training data
    • training data is of limited size, the easier to find a hypothesis that fits the difference between the training data and the true distribution
  • prevent overfitting:
    • cleaner training data help!
    • more training data help!
    • throwing away unnecessary hypotheses helps!

Overfitting in Decision Tree

Overfitting

  • consider error of model M over

    • training data: Error(Dtraining, M)
    • entire distribution of Data: Error(Dtrue, M)

  • model M $\in$ H overfits the training data if there is an alternative model M’ $\in$ such that

  • Example: overfitting with noisy data

    • Suppose
      • the target concept is Y = X1 $\bigwedge$ X2
      • there is noise in some feature values
      • we’re given the following training set









    • Avoiding overfitting in DT learning
      • two general strattegies to avoid overfitting
        1. early stopping: stop if further splitting not justified by a statistical test
          • Quinlan’s original approach in ID3
        2. post-pruning: grow a large tree, then prune back some nodes
          • more robust to myopia of greedy tree learning

Nearest-neighbor classification

Nearest-neighbor classification

  • learning stage
    • given a training set(X(1), y(1))…(x(m), y(m)), do nothing
      • (it’s sometimes called a lazy learner)
  • classification stage
    • given: an instance (q) to classify
    • find the training-set instance x(i) that is most similar to x(q)
    • return the class value y(i)

Nearest Neighbor

  • When to consider
    • Less than 20 attributes perinstance
    • Lots of training data
  • Advantages
    • Training is very fast
    • Learn complex target function
  • Disadvantages
    • Slow at query time
    • Easily fooled by irrelevant attributes
  • To classify a new input vector x, examine the k-closest training data points to x and assing the object to the most frequently occurring class

The decision regions for nearest-neighbor classification

  • Voronoi diagram: each polyhedron indicates the region of feature space that is in the nearest neighborhood of each training instance

Lec11-KNN(cont.)

Topic

  • Definition

    • How can we determine similarity/distance
    • Standardizing numeric features(leave this to you)

  • Speeding up k-NN

    • edited nearest neighbour
    • k-d trees for nearest neighbour identification

  • Variants of k-NN

    • k-NN regression
    • Distance-weighted nearest neighbor
    • Locally weighted regression to handle irrelevant features

  • Discussions

    • Strengths and limition of instance-based learning
    • Inductive bias

Definition

K-nearest-neighbor classification

  • Classification task
    • given: an instance x(q) to classify
    • find the k training-set instances(x(1),y(1))…(x(k),y(k)) that are the most similar to x(q)
    • return the class value
    • (i.e. rerturn the class that have the most number of instance in the k training instances)

How can we determine similarity/distance

  • suppose all features are categorical
    • Hamming distance(or L0 normal): count the number of features for which two instances differ
  • Example: X = (Weekday, Happy?, Weather) Y = AttendLecture

How can we detemine similarity/distance

![](https://pic.imgdb.cn/item/6197ed042ab3f51d91266b92.png)

How can we determine similarity/distance

  • suppose all feature are continuous
    • Euclidean distance
    • Manhattan distance

Standardizing numeric features

Speeding up k-NN

Issues

  • Choosing k
    • Increasing k reduces variance, increase bias
  • For high-dimensional space, problem that the nearest neighbor may not be very at all!
  • Memory-based technique. Must make a pass through the data for each classification. This can be prohibitive for large data sets

Nearest neighbour problem

  • Given sample S = ((X1,Y1),…..,(Xm,Ym)) and a test point x,
  • it is to find the nearest k neighbours of x
  • Note: for thhe algorithms, dimensionality N, i.e., number of features, is crucial

Efficient Indexing: N = 2

  • Algorithm
    • comopute Voronoi diagram in O(m log m)
      • See algorithm ~~~~~~~~~~~~
    • use point loaction data structure to determine nearest neighbours

Efficient Indexing: N > 2

  • Two general strategies for alleviating this weakness
    • don’t retain every training instance(edited nearest neighbor)
    • pre-processing. Use a smart data structure to look up nearest neighbors(e.g. a k-d tree)

Edited instance-based learning

k-d trees

Construction of k-d tree

Finding nearest neighbors with a k-d tree

  • use branh-and-bound search
  • priority queue stores
    • nodes considered
    • lower bound on their distance to query instance
  • lower bound given by distance using a single feature
  • average case: O(log2m)
  • worst case: O(m) where m is size of training set

k-d tree example (Manhattan distance)










Extended Materials: Voronoi Diagram Generation

•https://en.wikipedia.org/wiki/Voronoi_diagram
•https://courses.cs.washington.edu/courses/cse326/00wi/projects/voronoi.html

Variants of k-NN

k-NN regression

  • learing stage
    • given a training set(x(1),y(1))…(x(m),y(m)), do nothing
      • (it’s sometimes called a lazy learner)
  • classification stage
    • given: an instance x(q) to classify
    • find the k training-set instances(x(1),y(1)…(x(k),y(k))) that are most similar to x(q)
    • return the value

Distance-weighted nearset neighbor

  • We can have instances contribute to a prediction according to their distance from x(q)

Irrelevant features in instance-based learning

Locally weighted regression


展开全文 >>

COMP211-W4

Lec 4 - Network Layer - Data Plane

网络层

Goal

  • Principles behind network layer services, focusing on the data plane:
    • Network layer service routing
    • how a router works
    • addressing
    • generalized forwarding
    • Internet architecture
  • Instantiation, implementation in the Internet
    • IP protocol
    • NAT
    • Routing protocols

控制平面:全局
数据平面:局部

Overview:

  • Data Plane
  • Control Plane

Network-layer services and protocols

  • transport segment from sending to receiving host
    • sender: encapsulates segments into datagrams, passes tp link layer
    • receiver: deliver segments to transport layer protocol
  • network layer protocols in every Internet decvice: hosts, routers
  • routers:
    • examines header fields in all IP datagrams passing through it
    • moves datagrams from input ports to output ports to transfer datagrams along end-end path

Two key network-layer functions

network-layer functions:

  • forwarding: move packets from a router’s input link to appropriate router output link
  • router: determine route taken by oackets from source to destination
    • routing algorithms

analogy: taking a trip

  • forwarding: process of getting through single interchange
  • routing: process of planning trip from source to destination

Network layer: data plane, control plane

Data plane:

  • local, per-router function
  • determines how datagram arriving on router input port is forwarded to router output port

Control plane

  • network-wide logic
  • determines how datagram is routed among routers along end-end path from source host to destination host
  • two control-plane approaches:
    • traditional routing algorithms: implemented in routers
    • software-defined networking(SDN): implemented in (remote) servers

Per-router control plane

Individual routing algorithm components in each and every router interact in the control plane

SoftWare-Defined Networking(SDN)control plane

Remote controller computes, installs forwarding tables in routers

Inside a router

Router acrchiteture overview

High-level view of generic router architecture:

Input port functions

分散的切换

  • destination-based forwarding: forward based only on destination IP address(traditional)
  • generalized forwarding: forward based on any set of header field values

Destination-based forwarding

Longest prefix matching

Longest prefix match

when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.

Example 1: interface:0
Example 2: interface:1

Switching fabrics

  • Transfer packet from input link to appropriate output link

  • switching rate: rate at which packets can be transfer from inputs to outputs

    • often measured as multiple of input/output line rate

    • N inputs: switching rate N times line rate desirable

    • three major types of switching fabrics:

Switching via memory

First generation routers:

  • traditional computers with switching under direct control of CPU
  • packet copied to system’s memory
  • speed limited by memory bandwidth(2 bus crossing per data gatagram)

Switching via a bus

  • datagram from input port memory to output port memory via a shared bus
  • bus connection: switching speed limited by bus bandwidth
  • 32 Gbps bps, Cisco 5600: sufficient speed for access routers

Switching via interconnection network

  • Crossbar, Clos networks, other interconnection nets initially deceloped to connecr processors in multiprocessor
  • multistage switch: nxn switch from miltiple stages of smaller switches
  • exploiting parallelism:
    • fragment datagram into fixed length cells on entry
    • switch cells through the fabric, reassemble datagram at exit

Input port queuing

  • If switch fabric slower than input ports combined -> queueing may occur at input queues
    • queueing delay and loss due to input buffer overflow!
  • Head-of-the-Line(HOL) blocking: queued datagram at front of queue prevents others in queue from moving forward

Output port queuing

  • Buffering required when datagrams arrive from fabric faster than link transmission rate.

Drop policy: which datagrams to drop if no free buffers?

Datagrams can be lost due to congestion, lack of buffers

  • Scheduling discipline chooses among queued datagrams for transmission

Priority scheduling - who gets best performance, network neutrality

IP: the Internet Protocol - Datagram format

Network Layer: Internet

host, router network layer functions:

IP Datagram format

IP fragnebtation/reassembly

  • network links have MTU(max, transfer size) - largest possible link-level frame
    • different link types, different MTUs
  • large IP datagram divided(“fragmented”) within net
    • one datagram becomes several datagrams
    • “reassemebled” only at destination
    • IP header bits used to identify, order related fragments

      IP fragmentation/reassembly

IP: the Internet Protocol - Addressing

IP addressing: introduction

  • IP address: 32-bit identifier associated with each host or router interface
  • interface: connection between host/router and physical link
    • router’s typically have mulriple interfaces
    • host typically has one or two interfaces(e.g., wired Ethernet, wireless 802.11)

Subnets


Recipe for defining subnets:

  • detach each interface from its host or router, creating “islands” of isolated networks
  • each isolated network is called a subnet

IP addressing: CIDR

CIDR: Classless Inter Domain Routing(pronounced “cider”)

  • subnet protion of address of arbitrary length
  • address format: a.b.c.d/x, where x is # bits subnet portion of address

IP: the Internet Protocol - get an IP Address

IP addresses: how to get one?

Q: How does a hostget IP address within its network (host part of address)?

Q: How does a networkget IP address for itself (network part of address)

How does hostget IP address?

  • hard-coded by sysadmin in config file (e.g., /etc/rc.config in UNIX)
  • DHCP:Dynamic Host Configuration Protocol: dynamically get address from as server•“plug-and-play”

DHCP: Dynamic Host Configuration Protocol

goal: host dynamically obtain IP address from network server when it “joins” network

  • can renew its lease on address in use
  • allows reuse of addresses (only hold address while connected/on)
  • support for mobile users who join/leave network

DHCP overview

  • host broadcasts DHCP discovermsg [optional]
  • DHCP server responds with DHCP offermsg [optional]
  • host requests IP address: DHCP request msg
  • DHCP server sends address: DHCP ackmsg

DHCP client-server scenario


DHCP: more than IP addresses

DHCP can return more than just allocated IP address on subnet:

  • address of first-hop router for client
  • name and IP address of DNS server
  • network mask(indicating network versus host portion of address)

IP addresses: how to get one

Hierarchical addressing: route aggregation

hierarchical addressing allows efficient adverrisement of routing information:


IP addressing: last words

IP: the Internet Prorocol - Network address translation & IPv6

NAT: network address translation

NAT: all devices in local network share just one IPv4 address as far as outside world is concerned

IPv6: motivation

  • initial motivation: 32-bit IPv4 address space would be completely allocated
  • additional motivation:
    • speed processing/forwarding: 40-byte fixed length header
    • enable different network-layer treatment of “flows”

IPv6 datagram format

Transition from IPv4 to IPv6

  • not all routers can be upgraded simultaneously
    • no “flag days”
    • how will network operate with mixed IPv4 and IPv6 routers
  • tunneling: IPv6 datagram carried as payload in IPv4 datagram among IPv4 routers(“packet within a packet”)
    • tunneling used extensively in other contexts(4G/5G)

Tunneling and encapsulation

Tunneling

IPv6: adoption

  • Long(long!) time for deployment, use
    • 25 years and counting
    • think of application-level changes in last 25 years: WWW, social media, streaming media, gaming, telepresence,….

Generalized Forwarding, SDN - Match + action & OpenFlow

Generalized forwarding: match plus action

Review: each router contains a forwarding table (aka: flow table)

  • “match plus action” abstraction: match bits in arriving packet, take acton
    • destination-based forwarding” forward based on dest. IP address
    • generalized forwarding:
      • many header fields can determine action
      • many action possible: drop/copy/modify/log packet

Flow table abstraction

  • flow: defined by header field values(in link-, network-, transport-layer fields)
  • generalized forwarding: simple packet-handling rules
    • match: pattern values in packet header fields
    • actions: for matched packet: drop, forward, modify matched packet, or send matched packet to controller
    • priority: disambiguate overlapping patterns
    • counters: #bytes and #packets

OpenFlow: flow table entries

  • example

OpenFlow abstraction

  • match + action: abstraction unifies different kinds of devices

Router

  • match: longest destination IP prefix
  • action: forward out a link

Switch

  • match: destination MAC address
  • action: forward or flood

Firewall

  • match: IP address and TCP/UDP port numbers
  • action: permit or deny

NAT

  • match:IP address and port
  • action: rewrite address and port

Example

Generalized forwarding: summary

Lec5 - Network Layer - Control Plane

Goals:

  • Principles behind network control plane:
    • tradtional routing algorithms
    • SDN controllers
  • Instantiation, implementation in the Internet:
    • OSPF,BGP
    • OpenFlow

Introduction

Network-layer functions

  • forwarding(转发): move packets from router’s input to appropriate router output
  • routing(路由): determine route taken by packet from source to destination

Per-router control plane

Individual routing algorithm components in each and every
router interact in the control plane

Software-Defined Networking(SDN) control plane

Remote controller computes, installs forwarding tables in routers

Routing Algorithms

Routing protocols

Routing algorithm classification

Intra-AS Routing in the Internet: OSPF

Making routing scalable

Inrernet approach to scalable routing

aggregate routers into regions known as “autonomous systems” (AS) (a.k.a. “domains”)

inter-AS(aka “inter-domain”): routing among AS’es

  • gateways perform inter-domain routing(as well as intra-domain routing)

intra-AS(aka “intra-domain”): routing within same AS(“network”)

  • all routers in AS must run same intra-domain protocol
  • routers in different AS can run different intra-domain routing protocols
  • gateway router: at “edge” of its own AS, has link(s) to router(s) in other AS’ es

Interconnected ASes

Inter-AS routing: routing within an AS

most common intra-AS routing protocols:

  • RIP:Routing Information Protocol
    • classic DV: DVs exchanged every 30 secs
    • no longer widely used
  • EIGRP: Enhanced Interior Gateway Routing Protocol
    • DV based
    • formerly Cisco-proprietary for decades (became open in 2013)
  • OSPF: Open Shortest Path First
    • link-state routing
    • IS-IS protocol (ISO standard, not RFC standard) essentially same as OSPF

OSPF(Open Shortest Path First) routing

  • “open”: publiciy available
  • classic link-state
    • each router floods OSPF link-state advertisements (directly over IP rather than using TCP/UDP) to all other routers in entire AS
    • multiple link costs metrics possible: bandwidth, delay
    • each router has full topology, uses Dijkstra’s algorithm to compute forwarding table
  • secruity: all OSPF messages authenticated(to prevent maliciious intrusion(恶意入侵))

Hierarchical OSPF

Routing Among the ISPs: BGP

Internet inter-AS routing: BGP

  • BGP(Border Gateway Protocol): the de facto inter-domain routing protocol
    • “glue that holds the Internet together”
  • allows subnet to advertise its existence, and the destinations it can reach, to rest of Internet: “I am here, here is who I can reach, and how”
  • GBP provides each AS a means to:
    • eBGP: obtain subnet reachability information from neighboring ASes
    • iBGP: propagate reachability information to all AS-internal routers.
    • determine “good” routes to other networks based on reachability information and policy

eBGP, iBGP connections

BGP basics

  • BGP session: two BGP router(“peers”) exchange BGP messages over semi-perimanent TCP connection:
    • advertising path to different destination network prefixes(BGP is a “path vector” protocol)
  • when AS3 gateway 3a advertises path AS3, x to AS2 gateway 2c:
    • AS3 promises to AS2 it will forward datagrams towards X

Path attributes and BGP routes

  • BGP adverised router: prefix + attributes
    • prefix: destination being advertised
    • two important attributes:
      • AS-PATH: list of ASes through which prefix advertisement has passed
      • NEXT-HOP: indicates specific internal-AS router to next-hop AS
  • policy-based routing:
    • gateway receiving route advertisement uses import policy to accept/decline path (e.g., never route through AS Y).
    • AS policy also determines whether to advertise path to other other neighboring ASes

BGP path advertisement




BGP route selection

  • router may learn about more than one route to destination AS, selects route based on:
    1. local preference value attribute: policy decision
    2. shortest AS-PATH
    3. closest NEXT-HOP router: hot potato routing
    4. additional criteria
  • RouteViews Project: http://www.routeviews.org
    • telent route-views.linx.routeviews.org
    • show ip bgp 130.127.0.0/16 longer-prefixes

Why different Intra-, inter-AS routing?

policy:

  • inter-AS: admin wants control over how its traffic routed, who routes through its network
  • intra-AS: single admin, so policy less of an issue

scale:

  • hierachical routing saves table size, reduced update traffic

performance:

  • intra-AS: can focus on performance
  • inter-AS: policy dominates over performance

Software defined networking(SDN)

  • Internet network layer: historically implemented via distributed, per-router control approach:
    • monolithic router contains switching hardware, rums proprietary implementation of Internet standard protocols (IP, RIP, IS-IS, OSPF, BGP) in proprietary router OS(e.g., Cisco IOS)
    • different “middleboxes” for different network layer functions: firewalls, load balancers, NAT boxes, …

Software-Defined Networking(SDN) control plane

Remote controller computes, installs forwarding tables in routers

Software defined networking(SDN)

SDN analogy: mainframe to PC revolution

Traffic engineering: difficult with traditional routing



The SDN Control Plane - Implementation

Software defined networking(SDN)



OpenFlow protocol

  • operates between controller, switch
  • TCP used to exchange messages
    • optional encryption
  • three classes of OpenFlow messages:
    • controller-to-switch
    • asynchronous(switch to controller)
    • symmetric(e.g. check liveness)

SDN: control/data plane interaction example


SDN and the future of traditional network protocols

展开全文 >>

COMP201-W4

Lec 11-Formal Specifications

Objectives:

  • To explain why formal specification techniques help discover problems in system requirements
  • Todescribe the use of:
    • algebraic techniques(for interface specification)
    • model-based techniques(for behavioural specification)
  • To introduce Abstract State Machine model(ASML)

Formal Methods

  • Formal specification is part of a more general collection of techniques that are known as ‘formal methods’
  • Formal methods include
    • Formal specification
    • Specification analysis and proof
    • Transformational development
    • Program verification

Formal Method in reality

  • When software was first developed
    • it was done using assembly language
    • No OO, no high level languages
    • Limited understanding of software testing and testing tools
  • Modern software development
    • Many ways to make high quality software

Acceptance of Formal Methods

  • Formal methods have not become mainstream software development techniques as was once predicted

Use of Formal Methods

Specification in the software process

  • Specification and design are inextricably mixed.
  • Architectual design is essential to structure a specification
  • Formal specifications are expressed in mathematical notation with precisely defined vocabulary, syntax and Semantic

Specification Techniques

Use of Formal Specification

  • 正式的规范要求在软件开发的早期阶段投入更多的精力
    • 这减少了需求错误，因为它迫使对需求进行详细的分析
  • 不完整性和不一致性可以被发现和解决。
    • 因此，由于需求问题导致的返工数量减少，从而节省了成本

Formal Specification

  • 系统需求和设计被详细地表达出来，减少歧义，并在实现开始前仔细地分析和细化
  • 形式化规范的一大好处是它能够发现需求中的潜在问题和歧义。

Interface Specification

  • 大型系统被分解为子系统，这些子系统之间有定义良好的接口
  • 子系统接口的规范允许不同子系统的独立开发
  • 接口可能被定义成 抽象数据类型 或者 事物类

形式规范的代数方法特别适合于接口规范

Sub-system Interface Specification


The Strucutre of an Algebraic Specification

  • Introduction - Declare the sort(the type name) of the entity being specified, i.e., a set of objects with common characteristics. It also imports other specifications to use.
  • Description - An informal description of the operations
    to aid understanding.
  • Signature - Defines the syntax of the interface to the abstract data type(object), including their names, parameters list and return types.
  • Axioms(公理) - Defines the semantics of the operations by defining axioms characterising the behaviour

Systematic Algebraic Specification

  • Algebraic specifications of a system may be deceloped in a systematic way:
    • Specification structuring;
    • Specification naming
    • operation selection
    • Informal operation specification
    • Syntax definition
    • Axiom definition

Specification Operations

  • Constructor operations Operations which create entities of thetype being specified.
  • Inspection operations Operations which evaluate entites of the type being specified
  • To specify behaviour, define the snspector operations for each constructor operation
  • Example: Operation on a List ADT


Interface Specification in Critical Systems

A sector object

  • Critical operations on an object representing a controlled sector are
    • Enter- Add an aircraft to the controlled airspace
    • Leave - Remove an aircraft from the controlled airspace
    • Move - move an aircraft from one height to another
    • Lookup - Given an aircraft identifier, return its current height;

Primitive Operations

  • It is sometimes necessary to introduce additional operations to simplify the specification.
  • The other operations can the be defined using these more primitive operations
  • Primitive operations
    • Create - Bring an instance of a sector into existence
    • put - Add an aircraft without safety checks
    • In-space - Determine if a given aircraft is in the sector
    • Occupied - Given a height, determine if there is an aircraft within 300m of that height.

Speification Commentary for Sector

展开全文 >>

COMP211-W3

Lec3 Transport layer

传输层

OVERVIEW

Understand priciples behind transport layer services:

  • multiplexing, demultiplexing 复用（源段）和解复用(目标段)
  • reliable data transfer 可靠数据传输原理
  • flow control 流量控制
  • congestion control 堵塞控制

Learn about Internet transport layer protocols:

  • UDP: connection-oriented
  • TCP: connection-oriented reliable transport
  • TCP congestion control

Summary

  • principles behind transport layer services
    • multiplexing, demultiplexing
    • reliable data transfer
    • flow control
    • congestion control
  • instantiation, implemetation in the Internet
    • UDP
    • TCP

Transport-layer services

Service and protocols

  • provide logical communication between application processes running on different hosts
  • transport protocols actions in end systems:
    • sender:breaks applications messages into segments which as messages passes to network layer
    • receiver: reassembles segments into messages, passes to application layer
  • two transport protocols available to Internet applications
    • TCP,UDP

Transport vs. network layer services and protocols

  • network layer: logical communication between host
    • Similar to postal service that send a letter to a postal address

主机与进程之间的区别

  • transport layer: extends network service to provide a logical communication between processes
    • relies on, enhances, network layer services 是一种对网络层的细分

Transport Layer Action

传送端:

  • 通过应用层的报文
  • 决定字段头的值
  • 创建字段
  • 将字段传送给IP

接收端：

  • 从IP接受字段
  • 查看段头的值
  • 提供应用层报文
  • 由套接字解复用报文到应用

Two principal Internet transport protocols

  • TCP: 传输控制协议
    • 可靠， in-order delivery字节流
    • 多复用解复用
    • 流量控制
    • congestion setup 阻塞控制
    • connection setup
  • UDP: 用户数据报协议
    • 不可靠， unordered delivery
    • no-frills extension of “best-effort” IP

两种服务无法改变延迟，带宽
（吞吐量）

Multiplexing/demultiplexing 复用和解复用

在传送端复用，在接收端解复用

  • Multiplexing: 从多个套接字那里处理数据， 添加传输头
  • 用头信息来匹配接到的字段到正确的套接字

How demultiplexing works

  • host receives IP datagrams
    • each datagram has source(源段) IP address, destination(目标段) IP address
    • each datagram carrie one transport-layer segment 数据报包含传输层字段
    • each segment has source, destination port number
  • host uses IP addresses & port numbers to direct segment to appropriate socket
    主机通过 源端IP地址和目标端口号 来指导字段匹配套接字

Connectionless demultiplexing 无线连接复解用

  • 创建套接字的时候必须规定host-local 端口#：
    1
    DatagramSocket mySocket1 = new DatagramSocket(12534);
  • 创建数据报来传输到UDP套接字时必须规范
    • 目标端的IP地址
    • 目标端的端口#

当接收主机接收到 UDP字段：

  • 检查字段目标源端口
  • direct UDP segment to socket with that port#

IP/UDP datagrams with same dest.port#, but different source IP address and/or source port numbers will be directed to same socket at receiving host
目标端端口一样， 源端IP和端口被引导到同一个接受主机的套接字

  • example

Connection-oriented demultiplexing 面向连接的解复用

  • TCP socket identified by 4-tuple:
    • source IP address
    • source port number
    • dest IP address
    • dest port address
  • server may support many simultaneous TCP sockets:
    • each socket identified by its own sockets
    • each socket associated with a different connecting client
  • example

Summary

  • multiplexing, demultiplexing: based on segment, datagram header field values
  • UDP: demultiplexing using destination port number(only)
  • TCP: demultiplexing using 4-tuple: source and destination IP addresses, and port number

Connection-oriented transport: UDP

UDP:User Datagram Protocol

  • “no frills,” “bare bones” Internet transport protocol
  • “best effort” service, UDP segments may be:
    • lost
    • delivered out-of-order
  • connectionless:
    • no handshaking between sender, receiver
    • each UDP segment handled independently of others 彼此独立

Wbhy is there a UDP

  • no connection establishment(which can add RTT delay)
  • simple: connection state at sender, receiver
  • small header size
  • no congestion control
    • UDP can blast away as fast as desired
    • can function in the face of congestion

UDP: User Datagram protocol

  • UDP use:
    • streaming multimedia apps(loss tolerant, rate sensitive) 流媒体app
    • DNS
    • SNMP
    • HTTP/3
  • 如果需要在UDP上稳定传输
    • add needed reliability at application layer
    • add congestion control at application layer
  • RFC768

UDP segment header

![](https://pic.imgdb.cn/item/617bad302ab3f51d91fcccd5.png)

UDP checksum**

用来检测在传输字段里的错误

Internet checksum

Goal: detect errors in transmitted segment

Sender:

  • treat contents of UDP segment as sequence of 16-bit integers
  • checksum: addition (one’s complement sum) of segment content
  • checksum value put into UDP checksum field

Receiver

  • compute checksum of received segment
  • check if computed chechsum equals checksum field value:
    • not equal - error detected
    • equal - no error detecrted. But maybe errors notetheless? More later ….
  • Example
  • weak proteciton!

Summary: UDP

  • “no frills” protocol:
    • segments may be lost, delivered out of order
    • best effort service: “send and hope for the best”
  • UDP has its plusses:
    • no setup/handshaking needed(no RTT incurred)
    • can function when network service is compromised
    • helps with reliability(checksum)
  • Build additional functionality on top of UDP in application layer(e.g., HTTP/3)

Principle of reliable data transfer



需要在进入非可靠channel之前加安全协议

可靠传输协议的复杂度由非可靠channel的特征决定

接收端和发送端彼此不知道对方的状态除非经由报文沟通

protocol(rdt): interfaces

Reliable data transfer: getting started

We will:

  • incrementally develop sender, receiver sides of rdt protocol
    逐步开放发送端和接收端的rdt协议
  • consider only unidirectional data transfer
    • 但是控制信息会双向流动
  • use finite state machines(FSM) to specify sender, receiver

    rdt1.0: reliable transfer over a reliable channel

    发送方：对数据进行接收封装打走
    接收方：接受packet解封装然后传给上层用户
  • underlying channel perfectly reliable底层通道非常可靠
    • no bit errors
    • no loss of packets
  • separate FSMs for sender, receiver:
    • sender sends data into underlying channel
    • receiver reads data from underlying channel

rdt2.0:

channel with bit errors
发送方留副本，接收方检验

  • underlying channel may flip bits in packet
    • checksum(e.g., Internet checksum) to detect bit errors
      在1.0基础上加伤checksum
  • the question: how to recover from errors?

channel with bit errors

  • acknowledgements(ACKs): receiver explicitily tells sender that pkt receiverd OK
  • negative acknowledgements(NAKs): receiver explicitly tells sender that pkt had errors
  • sender retransmits pkt on receipt of NAK 收到错误消息后重新发送
  • stop and wait
    发送端发送一个包裹， 然后等待接收端反应

FSM specifications

Note: 接收端和发送端彼此不知道对方的状态除非经由某种方式沟通

  • 所以需要协议来控制
  • 发送方：
    • 等待上层的调用
    • 等待ACK 或者 NAK
  • 接收方：
    • 等待来自下层的调用

operation with no errors

corrupted packet scenario

has a fatal flaw!

when ACK/NAK corrupted happened

  • sender doesn’t know what happened at receiver
  • can’t just retransmit: possible duplicate

handling duplicates:

  • sender retransmits current pkt if ACK/NAK corrupted
  • sender adds sequence number to each pkt
  • receiver discards(doesn’t deliver up) duplicate pkt
    发送端发送一个包裹， 然后等待接收端反应

rdt2.1

sender, handling grabled ACK/NAKs 停止等待协议

发送方：初始化等待上层调用零 ——> 等待 ACK/NAK （没收到/NAK- 重发） ——> 等待上层调用1 ——> 等待 ACK/NAK （没收到/NAK- 重发）

接收方： 等待下层调用0 成功的话提取data 并返回ACK 如果重复数据 重新发送 ——> 等待下层调用1
discussion

sender:

  • seq # added to pkt
  • two seq. #s(0,1) will suffice. 只需要一位就能区分新老
  • check if received ACK/NAK corrupted 如果崩溃了重新发送之前的
  • twice as many states
    • state must “remember” whether “expected” pkt should have seq # of 0 or 1

receiver:

  • if packet is duplicate 重复了丢掉现在的 重新发送 ack/nak
    • state indicates whether 0 or 1 is expected pkt seq#
  • note: receiver can notknow if its last ACK/NAK received OK at sender

rdt2.2

a NAK-free protocol

  • same functionality as rdt2.1, using ACKs only
  • insted of NAK, receiver sends ACK for last pkt received OK
    • receiver must explicitly include seq# pf pkt being ACKed
  • duplicate ACK at sender results in same action as NAK: retransmit current pktTCP use this approach to be NAK-free

sender, receiver fragments

rdt3.0: channels with errors and loss

New channel assumption: underlying channel can also lose packets(data, ACKs)

  • checksum, sequence #s, ACKs, retransmissions will be of help … but not quite enough

channel with errors and loss
Approach: sender waits “reasonable” amount of time for ACK

  • 如果ACK没有被接收重新发送
  • if pkt()or ACK just dlayed:
    • retransmission will be duplicate, but seq #s already handles this!
    • receiver must specify seq# of packet being ACKed
  • use countdown timer to interrupt after “reasonable” amount of time

sender

in action

Principles of reliable data transfer - Pipelined protocols

rdt3.0

Performance of rdt3.0

  • U sender: utilization - fraction of time sender busy sending
  • example: 1Gbps link, 15 ms prop. delay, 8000 bit packet
    • time to transmit packet into channel

stop-and-wait operation

RTT

Pipelined protocols operation

piplining: sender allows multiple, “in-flight”, yet-to-be-acknoledged packets

  • range of sequence numbers must be increased
  • buffering at sender and/or receiver

Pipelining: increased utilization

Go-Back-N: 回退n步协议

Sw = 1 Rw = 1 等停协议 rdt 3.0

流水线协议：

  • Sw > 1 Rw = 1 GBN协议

  • Sw > 1 Rw > 1 选择性重发协议

发送缓冲区： 发送方发送完之后将分组放在缓冲区中以用于鉴错重发超时重发

  • 内存中的一个区域
  • 连续向对方发送多个未经确认分组， 上线就是缓冲区大小

发送窗口： 发送缓冲区的一个范围

  • 已发送但是未确认的分组构成的子集 <= 发送缓冲区的值
  • 上限前沿和后沿距离达到发送缓冲区的值
  • 确认后（ACK），后沿向前滑动 -> 缓冲区向前滑动
    • 后沿极限是和前沿重合

sender

  • sender: “window” of up to N, consecutive transmitted but unACKed pkts
    • k-bit seq # in pkt header
  • cumulative(积累) ACK: ACK(n) all packets up to, including seq # n
    • on receiving ACK(n): move window forward to begin at n+1
  • timer for oldest in-flight packet
  • timeout(n): retransmit packet n and all higher seq # packets in window

接收缓冲区：

接收窗口：

  • Rw = 1 一次次滑动只有接到对应分组才能继续滑动
    • 对接到的顺序的窗口进行确认
    • 只能顺序接收
  • Rw > 1
    1. 给接收到的分组确认
    2. 接受窗口向前滑动一格
    3. 可以接受窗口内任何一个分组
    4. 只有最小的序列分组接收之后才能继续滑动

receiver

  • ACK-only: always send ACK for correctly-received packet so far, with highest in-order seq#
    • may generate duplicate ACKs
    • need only remember rcv_base
  • on receipt of out-of-order packet:
    • can discard(don’t buffer) or buffer: an implementation decision
    • re-ACK pkt with highest in-order seq#

in action

Selective repeat

  • receiver indually acknowledges all correctly received pactet
    • buffers packets, as needed, for eventual in-order delivery to upper layer
  • sneder times-out/retransmits individually for unACKed packets

sender, receiver, windows

sender and receiver

  • sender
    • data from above:
      • if next available seq# in window, send packet
    • timeout(n):
      • resend packet n, restart timer
    • ACK(n) in [sendbase, sendbase+N]:
      • mark packet n as received
      • if n smallest unACKed packet, advance window base to next unACKed seq#
  • receiver
    • packet n in [rcvbase, rcvbase+N-1]
      • send ACK(n)
      • out-of-order: buffer
      • in-order: deliver (also deliver buffered, in-order packets), advance window to next not-yet-received packet
    • packetn in [rcvbase-N, rcvbase-1]
      • ACK(n)
    • otherwise
      • ignore

Selective Repeat in action

Connection-oriented transport: TCP

TCP: overview RFCs: 793, 1122, 2018, 5681, 7323

  • point-to-point:
    • one sender, one receiver
  • reliable, in-order byte steam:
    • no “message boundaries”
  • full duplex data:
    • bi-directional data flow in same connection
    • MSS: maximum segment size
  • cumulative ACKs
  • pipelining
    • TCP congestion and flow control set window size
  • connection-oriented:
    • handshaking (exchange of control messages) initializes sender, receiver state before data exchange
  • flow controlled:
    • sender will not overwhelm receiver

TCP segment structure

TCP sequence numbers, ACKs

  • Sequence numbers:

    • byte stream “number” of first byte in segment’s data

  • Acknowledgements:

    • seq # of next byte expeceted from other side
    • cumulative ACK

      TCP round trip time, timeout

  • set TCP timeout

    • longer than RTT, but RTT varies!
    • too short: premature timeout, unnecessary retransmissions
    • too long: slow reaction to segments loss

  • estimate RTT

    • SampleRTT: mesured time from segment transmission until ACK receipt
      • ignore retransimissions
    • SampleRTT: will vary, want estimated RTT “smoother”
      • average several recent measurements, not ust current SampleRTT
      • 指数加权移动平均
      • 过去样本呈指数衰减

  • timeout interval: EstimatedRTT plus “safety margin”

    • large variation in EstimatedRTT: want a larger safety margin

      TimeoutInterval = EstimatedRTT + 4*DevRTT

    • DevRTT: EWMA of SampleRTT deviation from EstimatedRTT:

      DevRTT = （1-$\beta$) * DevRTT + $\beta$*| SampleRTT - EstimatedRTT|
      (typically, $\beta$ = 0.25)

      reliable data transfer

Overview

  • TCP creates rdt service on top of IP’s unreliable service
    • pipelined segments
    • cumulative acks
    • single retransmission timer
  • retransmissions triggered by:
    • timeout events
    • duplicate acks
  • simplified TCP sender:
    • ignore duplicate acks
    • ignore flow control, congestion control

TCP Sender(simplified)

event: data received from application

  • create segment with seq #
  • seq # is byte-stream number of first data byte in segment
  • start timer if not already running
    • think of timer as for oldest unACKed segment
    • expiration interval: TimeOutInterval

event: timeout

  • retransmit segment that caused timeout
  • restart timer

event: ACK received

  • if ACK acknowledges previously unACKed segments
    • update what is known to be ACKed
    • start timer if there are still unACKed segments

retransmission scenarios

![](https://pic.imgdb.cn/item/617ef3aa2ab3f51d910414ff.png)

累加ACK 覆盖了先前丢失的ACK

TCP Receiver: ACK generation

TCP fast retransmit

if sender receives 3 additional ACKs for same data(“triple duplicate ACKs”), resned unACKed segment with smallest seq#

  • likely that unACKed segment lost, so don’t wait for timeout

    Receipt of three duplicate ACKs indicates 3 segments received after a missing segment –lost segment is likely. So retransmit!

Flow control

当网络层传输信息的速度大于应用层从套接字缓冲区移除信息的速度

flow control

  • receiver controls sender, so sender won’t overflow receiver’s buffer by transmitting too much, too fast


Application removing data from TCP socket buffers

  • TCP receiver “advertises” free buffer space in rwnd field in TCP header
    • RcvBuffer size set via socket options (typical dfault is 4096 bytes)
    • many operating systems autoadjust RcvBuffer
    • sender limits amount of unACKed(“in-flight”) data to received rwnd(free buffer space)
    • guarantees receive buffer will not overflow

TCP connection management

before exchanging data, sender/receiver “handshake”:

  • agree to establish connection(each knowing the other willing to establish connection)

Agreeing to eatablish a connection
2-way handshake in network

  • variable delays
  • retransmitted messages due to message loss
  • message reordering
  • can’t “see” other side

2-way handshake scenarios

TCP 3-way handshake

Closing a TCP connection

  • client, sercver each close their side of connection
    • send TCP segment with FIN bit = 1
  • respond to received FIN with ACK
    • on receiving FIN, ACK can be combined with own FIN
  • simultaneous FIN exchanges can be handled

Principles of congestion control

Pirnciples of congestion control

Approaches towards congestion control

End-end congestion control

  • no explicit(明确的) feedback from network
  • congestion inferred from obesrved loss, delay
  • approach taken by TCP

Network-assisted congestion control:

  • routers provide direct feedback to sending/receiving hosts with flows passing through congested router
  • may indicate congestion level or explicitly set sending rate
  • TCP ECN, ATM, DECbit protocols

TCP congestion control

AIMD(Additice Increase & Multiplicative Decrease)

  • approach: senders can increase sending rate until packet loss(congestion)occurs, then decrease sending rate on loss event
  • Additive Increase: increase sending rate by 1 maximum segment size every RTT until loss detected
  • Multiplicative Decrease: cut sending rate in half at each loss event
    • sending rate is cut in half on loss detected by triple duplicate ACK(TCP Reno)
    • Cut to 1 MSS(maximum segment size ) when loss detected by timeout(TCP Tahoe)
  • AIMD sawtooth behavior: probing for bandwidth
    • a distributed, asynchronous algorithm - has been shown to:
      • optimize congested flow rates network wide!
      • have desirable stability properties
  • details
    • TCP sending behavior:
      • roughly: send cwnd bytes, wait RTT for ACKs, then send more bytes
        • TCP rate $\approx$ cwnd/RTT bytes/sec
    • TCP sender limits transmission
      • LastByteSent - LastByteAcked <= cwnd
    • cwnd is dynamically adjusted in response to observed network congestion(implementing TCP congestion control)

TCP slow start

  • when connection begins, increase rate exponentially until first loss event:
    • initially cwnd = 1MSS
    • double cwnd every RTT
    • done by inctementing cwnd for every ACK received
  • summary: initial rate is slow, but ramps up exponentially fast

TCP: from slow start to congestion avoidance

TCP fairness

Fairness goal: if K TCP sessions share same bottleneck link of banwidth R, each should have average rate of R/K

Is TCP Fair?
Example: 两个竞争的TCP会话

  • additive increase gives slope of 1, as throughout increases
  • multiplicative decrease decreases throughput proportionally

Evolution of transport-layer functionality

Evolving transport-layer functionality

QUIC: Quick UDP Internet Connections

  • application performance of HTTP
  • deployed on many Google servers, apps(Chrome, mobile YouTube app)
  • adopts approaches we’ve studied in this chapter for connection establishment, error control, congestion control
    • error and congestion control: “Readers familiar with TCP’s loss detection and congestion control will find algorithms here that parallel well-known TCP ones.”
    • connection establishment: reliability, congestion control, authentication, encryption, state established in one RTT
  • multiple application-level “streams” multiplexed over single QUIC connection
    • separate reliable data transfer, security
    • common congestion control
  • Connection establishment

展开全文 >>

COMP211LAB

Assessment 1

Part A:

  • This part is based on the content for the first two lab
  • First we need to declare variables such as socket and cache
  • Then I combine from the lab source and my own knowladge figure out the result
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    /*************************************
     * Filename:  SMTPInteraction.java
     *************************************/
    import java.net.*;
    import static java.lang.Integer.parseInt;
    import java.io.*;
    import java.util.*;

    // Name: Junshu Sha
    // ID: 201600804
    // Blog: https://shaysha-pra.github.io/

    // import jdk.internal.org.jline.utils.InputStreamReader;

    /**
     * Open an SMTP connection to mailserver and send one mail.
     *
     */
    public class SMTPInteraction {
        /* Socket to the server */
        private Socket connection;
        /* Streams for reading from and writing to socket */
        private BufferedReader fromServer;
        private DataOutputStream toServer;
        private static final String CRLF = "\r\n";	
        /* Are we connected? Used in close() to determine what to do. */
    	//the number of recipient address
        private boolean isConnected = false;
    	private int number_of_RCPT = 0;
    	private String check_RCPT[];

        /* Create an SMTPInteraction object. Create the socket and the 
           associated streams. Initialise SMTP connection. */
        public SMTPInteraction(EmailMessage mailmessage) throws IOException {
            // Open a TCP client socket with hostname and portnumber specified in
            // mailmessage.DestHost and  mailmessage.DestHostPort, respectively.
    		int PORT = mailmessage. DestHostPort;
    		connection = new Socket(mailmessage.DestHost, PORT);
    	
            // attach the BufferedReader fromServer to read from the socket and
            // the DataOutputStream toServer to write to the socket
            fromServer = new BufferedReader(new InputStreamReader(connection.getInputStream()));
    		toServer =   new DataOutputStream(connection.getOutputStream());
    		// fromServer = new BufferedReader(new InputStreamReader(System.in));
    		// toServer = System.out;


    		/* Read one line from server and check that the reply code is 220.
    	   If not, throw an IOException. */


    		String response = fromServer.readLine();
    		if (!response.startsWith("220")) {
    			throw new IOException("220 reply not received from server.");
    		}
    		/* SMTP handshake. We need the name of the local machine.
    		Send the appropriate SMTP handshake command. */
    		String localhost = InetAddress.getLocalHost().getHostName();
    		sendCommand("HELO " + localhost, 250);


    		isConnected = true;
        }

        /* Send message. Write the correct SMTP-commands in the
           correct order. No checking for errors, just throw them to the
           caller. */
        public void send(EmailMessage mailmessage) throws IOException {

    	// initialize the number of rcpt address.
    		check_RCPT = mailmessage.Recipient.split(",");
    		number_of_RCPT = check_RCPT.length;

    	/* Send all the necessary commands to send a message. Call
    	   sendCommand() to do the dirty work. Do _not_ catch the
    	   exception thrown from sendCommand(). */

    		sendCommand(("MAIL FROM: " + "<" + mailmessage.Sender+ ">"), 250);

    		if (number_of_RCPT > 1){
    				for (int i = 0; i <= number_of_RCPT;i++){
    					sendCommand(("RCPT TO: " + "<" + check_RCPT[i] + ">"), 250);
    					number_of_RCPT--;
    				}
    		}else{
    			sendCommand(("RCPT TO: " + "<" + mailmessage.Recipient + ">"), 250);
    		}
    		sendCommand("DATA", 354);
    		sendCommand(mailmessage.Headers + CRLF + mailmessage.Body + CRLF + ".", 250);
        }

        /* Close SMTP connection. First, terminate on SMTP level, then
           close the socket. */
        public void close() {
    		isConnected = false;
    		try {
    			sendCommand("QUIT", 221);
    			connection.close();
    		} catch (IOException e) {
    			System.out.println("Unable to close connection: " + e);
    			isConnected = true;
    		}
        }

        /* Send an SMTP command to the server. Check that the reply code is
           what is is supposed to be according to RFC 821. */
        private void sendCommand(String command, int rc) throws IOException {

    		/* Write command to server and read reply from server. */
    		toServer.writeBytes(command + CRLF);

    		

    		/* Check that the server's reply code is the same as the parameter
    		rc. If not, throw an IOException. */
    		String response = fromServer.readLine().split(" ")[0];
    		int reply_code = parseInt(response);
    		System.out.println(response);
    		if(reply_code != rc)
    			throw new IOException("reply code is not matched.");
    	}

        protected void finalize() throws Throwable {
            if (isConnected) {
                close();
            }

        }
    }

Part B

  • This part is the application of the HTTP method
  • This part is some functional functions. The function I used to judge BUF_SIZE at the beginning is logically wrong. This is very common and it is difficult to find that after a long time of inspection, I changed to the function that I use now.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    /**********************************
     * Filename:  HTTPInteraction.java
     *************************************/

    import java.io.*;
    import java.net.*;
    import java.util.*;

    // Name: Junshu Sha
    // ID: 201600804
    // Blog: https://shaysha-pra.github.io/

    // import jdk.internal.org.jline.utils.InputStreamReader;

    /**
     * Class for downloading one object from http server.
     *
     */
    public class HTTPInteraction {
    	private String host;
    	private String path;
    	private String requestMessage;
    	
    		
    	private static final int HTTP_PORT = 80;
    	private static final String CRLF = "\r\n";
    	private static final int BUF_SIZE = 4096; 
    	private static final int MAX_OBJECT_SIZE = 102400;

     	/* Create HTTPInteraction object. */
    	public HTTPInteraction(String url) {
    		
    		/* Split "URL" into "host name" and "path name", and
    		 * set host and path class variables. 
    		 * if the URL is only a host name, use "/" as path 
    		 */		
    		
    		/* Fill in */			
    		String name[] = url.split("/", 2); // divided url into two parts when it meets the first "/" 
    		host = name[0];	// initial the host as first part of name[]
    		if (name.length >= 2) {
    			path = "/" + name[1]; // set path name when name's length is bigger or equal than 2

    		}else{
    			path = "/";	
    		}

    	
    		/* Construct requestMessage, add a header line so that
    		 * server closes connection after one response. */		
    		requestMessage = "GET " + path  + " HTTP/1.1" + CRLF + "Host: " + host + CRLF; // normal format for GET method

    	
    		return;
    	}	
    	
    	
    	/* Send Http request, parse response and return requested object 
    	 * as a String (if no errors), 
    	 * otherwise return meaningful error message. 
    	 * Don't catch Exceptions. EmailClient will handle them. */		
    	public String send() throws IOException {
    		
    		/* buffer to read object in 4kB chunks */
    		char[] buf = new char[BUF_SIZE];

    		/* Maximum size of object is 100kB, which should be enough for most objects. 
    		 * Change constant if you need more. */		
    		char[] body = new char[MAX_OBJECT_SIZE];
    		
    		String statusLine="";	// status line
    		int status;		// status code
    		String headers="";	// headers
    		int bodyLength=-1;	// lenghth of body
    				
    		String[] tmp;
    		
    		/* The socket to the server */
    		Socket connection;
    		
    		/* Streams for reading from and writing to socket */
    		BufferedReader fromServer;
    		DataOutputStream toServer;

    		System.out.println("Connecting server: " + host +CRLF); 
    		
    		/* Connect to http server on port 80.
    		 * Assign input and output streams to connection. */		
    		connection = new Socket(host, HTTP_PORT); // get host and it's server
    		fromServer = new BufferedReader(new InputStreamReader(connection.getInputStream())); // get input of connection
    		toServer = new DataOutputStream(connection.getOutputStream());	// get out put of connection
    		
    		System.out.println("Send request:\n" + requestMessage); //print request Message


    		/* Send requestMessage to http server */
    		/* Fill in */
            toServer.writeBytes(requestMessage + CRLF); 
    		
    		/* Read the status line from response message */
    		statusLine= fromServer.readLine();
    		System.out.println("Status Line:\n"+ statusLine +CRLF); //print status message 
    		
    		/* Extract status code from status line. If status code is not 200,
    		 * close connection and return an error message. 
    		 * Do NOT throw an exception */		
    		/* Fill in */
    		status = Integer.parseInt(statusLine.substring(9,12)); // get status codes

    		try{									// this part is almost same as the lab session
    			if (status != 200){
    				connection.close();
    				System.out.println("status code is not 200!");
    			}
    		}catch(UnknownHostException e){
    			throw e;
    		}

    		/* Read header lines from response message, convert to a string, 
     		 * and assign to "headers" variable. 
    		 * Recall that an empty line indicates end of headers.
    		 * Extract length  from "Content-Length:" (or "Content-length:") 
    		 * header line, if present, and assign to "bodyLength" variable. 
    		*/
    		/* Fill in */ 		// requires about 10 lines of code

    		
    		String header_lines;
    		
    		while(!(header_lines = fromServer.readLine()).isEmpty()){
    			headers += header_lines + CRLF;  // generate the hearder's information
    			if(header_lines.startsWith("Content-Length:") || header_lines.startsWith("content-length:")){
    				tmp = header_lines.split(" ");
    				int lth = Integer.parseInt(tmp[1]);
    				bodyLength = lth;
    				
    			}
    			if (header_lines.startsWith("Location:")) {
                    tmp = header_lines.split(" ");
                    return tmp[1];
    			}
    		}
    		System.out.println("Headers:\n" + headers + CRLF);
    	

    		/* If object is larger than MAX_OBJECT_SIZE, close the connection and 
    		 * return meaningful message. */
    		if (bodyLength > MAX_OBJECT_SIZE) {
    			/* Fill in */
    			connection.close();
    			return(headers +bodyLength);
    		}
    					    
    		/* Read the body in chunks of BUF_SIZE using buf[] and copy the chunk
    		 * into body[]. Stop when either we have
    		 * read Content-Length bytes or when the connection is
    		 * closed (when there is no Content-Length in the response). 
    		 * Use one of the read() methods of BufferedReader here, NOT readLine().
    		 * Make sure not to read more than MAX_OBJECT_SIZE characters.
    		 */				
    		int bytesRead = 0;

    		/* Fill in */   // Requires 10-20 lines of code

    		if(bodyLength>0){				//Read the body in chunks of BUF_SIZE using buf[] and copy the chunk in to body[]
    			while(bodyLength-bytesRead>0){   
    				int read = fromServer.read(buf); // read form buf
    				for(int i=0;i< read;i++){
    					body[i+bytesRead] = buf[i];
    				}
    				bytesRead += read;	// add read's content to bytesRead
    			}
    		}else{
    			while(bytesRead<MAX_OBJECT_SIZE){
    				int read = fromServer.read(buf,  0, BUF_SIZE); 
    				if(read == -1) break;
    				for(int i=0;i< read;i++){
    					body[i+bytesRead] = buf[i];
    				}
    				bytesRead += read;
    			}
    		}
    		for(int i=0;i<bytesRead;i++){
    			System.out.print(body[i]);
    		}
    		   
    		/* At this points body[] should hold to body of the downloaded object and 
    		 * bytesRead should hold the number of bytes read from the BufferedReader
    		 */
    		
    		/* Close connection and return object as String. */
    		System.out.println("Done reading file. Closing connection.");
    		connection.close();
    		return(new String(body, 0, bytesRead));
    	}
    }

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>🌳就是最菜的<br>谢谢大家