方法

以测试代替重复学习

看完没记住就是白学，不管花了多少时间

大量阅读

Wikipedia 专业书籍 论文

阅读本领域的权威书籍和经典论文是最好的选择，有些内容是只会写在书里的，网络上不会有的，当然大牛的blog值得一看，也应该关注一下DeepMind这种的研究工作。

只管回忆

• 看书后尽力回忆学到的知识
• 回忆插画内容：色彩，构图，用光，渲染
  回忆越困难，建立的神经元连接就会越牢固（符合代价哲学）

• 回忆量要大，在脑内的搜索速度要快

  体系建立

• 浏览英文维基相关领域的每一个概念词条，以概念建立起知识体系
  创建自己的维基地图，比如我正在复习线性代数系统，记录下我浏览过的词条，哪些是重要的。
  eg: 英文维基Calculus，要做到对其中列出的概念每个都非常熟悉

  概念添加

• 一个东西是什么？包含哪些作用？
  是概念，定义，定理，还是一个库，一个平台？
  eg:

  • OpenGL——是一个API，
  • kernel 是什么？
    a program that is the core of Operating System.
  • kernel 负责什么？(functions)
    1. CPU 2. Memory 3. devices

Chapter4: Ray Tracing

object rendering: each object is considered in turn
image-order rendering: each pixel is considered in turn

Ray Tracing is an image-order algorithm for making renderings of 3D scenes

4.1 The Basic Ray-Tracing Algorithm

a basic ray tracer have 3 parts:

• ray generation
  which computes the origin and direction of each pixel’s viwing ray based on the camera geometry
• ray intersection
  find the cloeset object intersecting the viewing ray
• shading
  computes the pixel color based on the results of ray intersection

  1 2 3 4

  for each pixel do computing viewing ray ray, surface norm n -> first object hit light, hit point, n -> pxiel color

4.2 Perspective

linear perspective

• parallel projection
  orthographic oblique
• perspective projection

4.3 Computing Viewing Rays

A ray is really just an origin point and a propogation direction,a 3D parametric line is ideal for this
$p(\mathbf{t}) = \mathbf{s} + t\mathbf{(e-s)}$

4.3.1 Orthographic Views

the pixel at position (i,j) in the raster images has the position
$u=l+(r-l)(i+0.5)/n_x$
$v=b+(t-b)(j+0.5)/n_y$
where $(u,v)$ are the coordinates of the pixel’s position on the image plane

4.3.2 Perspective Views

all the rays have same origin

compute $\mathbf{w}$ and $\mathbf{w}$
ray.direction $\leftarrow -d\mathbf{w} + u\mathbf{u} + v\mathbf{v}$
ray.origin $\leftarrow e$

4.4 Ray-Object Intersection

4.4.1 Ray-Sphere Intersection

$\mathbf{p} = \mathbf{e} + t\mathbf{d}$
$\mathbf{c} = (x_c, y_c, z_c)$
$\mathbf{(p-c)\cdot(p-c)} - R^2 = 0$
this is a classic quadratic equation in t
$discriminant < 0$ line and sphere do not intersect
$discriminant > 0$ line enter and leave the sphere
$discriminant = 0$ ray graze the sphere

Ray-Triangle Intersection

the vertices of the triangle is in 3D space
$\mathbf{e} + t\mathbf{d} = \mathbf{a} + \beta \mathbf{(b-a)} + \gamma \mathbf{(c-a)}$
$\beta > 0 \quad \gamma > 0 \quad \beta + \gamma < 1$ intersection is inside the triangle, otherwise the ray hit the plane outside of the triangle.
if no solution, either the traingle is degenerate or the ray is paralled to the plane containing the traingle

4.4.3 Ray-Polygon Intersection

4.4.4 Intersecting a Group of Objects

4.5 Shading

4.5.1 Lambertian Shading

a surface facing directly toward the light receives maximum illumination
a surface tangent to tht light direction recevies no illumination
$L = k_dImax(0, \mathbf{n\cdot l} )$
$L:$ pixel color
$k_d$ diffuse coefficient
$I:$ intensity of the light source
$\mathbf{l}:$ light direction
$\mathbf{v}:$ view direction
this equation applies separately to the three color channels

4.5.2 Blinn-Phong Shading

Lambertian Shading is view independent
the color of a surface does not depend on the direction from which you
shininess, producing highlights, specular reflections appear to move around the view point changes
$\mathbf{h} = \dfrac{\mathbf{v+l}}{\parallel \mathbf{v+l} \parallel} $
$L = k_dI\max(0, \mathbf{n \cdot l}) + k_sI\max(0,\mathbf{n\cdot h})^p$
$k_s:$ specular coefficient
$p$: Phong exponent

4.5.3 Ambient Shading

$L = k_aI_a + k_dI\max(0, \mathbf{n \cdot l}) + k_sI\max(0,\mathbf{n\cdot h})^p$
$k_a:$ surface’s ambient coefficient/ ambient color
$I_a:$ ambient light intensity

4.5.4 Multiple Point Lights

simple shading model can easily be extended to handle N light sources
$L = k_aIa + \sum{i=1}^{N}[k_dI\max(0, \mathbf{n \cdot l}) + k_sI\max(0,\mathbf{n\cdot h})^p]$

4.6 A Ray-Tracing

4.7 Shadows

4.8 Ideal Specular Reflection

mirror reflection
some energy is lost when the light reflects from the surface, and this loss can be different for different colors
$color c = c + k_mraycolor(\mathbf{p}+sr, \epsilon, \infty)$
$k_m:$ specular RGB color

Chapter3 Raster Image

Pixel is short for picture element
A raster images is simply a 2D array that stores the pixel value for each pixel
image pixels != display pixel

3.1 Raster Devices

• Output
  • Display
    • Transmissive: liquid crystal display LCD
    • Emissive: light-emitting diode LED display
  • Hardcopy
    • Binary: link-jet printer
    • Continuous tone: dye sublimation printer
      thermal dye transfer donor ribbon continous tone
      ppi: pixel per inch
      dpi: dots per inch
      stair stepping
• input
  • 2D array sensor: digital camera
    CCD: charge-coupled devices
    CMONS: complimentary metal-oxide-semiconductor
  • 1D array sensor: flatbed scanner

3.2 Images, Pixels, Geometry

$I(x,y): R \to V$
$R \subset \mathbb{R^2}$ is a rectangular area and $V$ is the set of possible pixel values

3.2.2 Monitor intensities and Gamma

• monitors are nonlinear with respect to input
  displayed intensity = (maximum intensity)$a^\gamma$
  a in the input pixel value between 1 and 0
  describing a display’s nonlinearity using $\gamma$ is only an approximation

  3.3 RGB Color

  1 2 3 4 5 6 7 8

  black = (0, 0, 0) red = (1, 0, 0) green = (0, 1, 0) blue = (0, 0, 1) yellow = (1, 1, 0) magenta = (1, 0, 1) cyan = (0, 1, 1) white = (1, 1, 1)

3.4 Alpha Compositing

pixel coverage $\alpha$ fraction of pixel covered by the foreground layer
$c = \alpha c_f + (1-\alpha)c_b$
alpha mask alpha channel

• Image Storage
  jpeg: lossy
  tiff: lossless
  ppm: lossless
  png: lossless

Chapter2 Miscellaneous Math

2.5 Curves and Surfaces

2.5.1 2D Implicit Curves

implicit equation $f(x,y)=0$

2.5.2 The 2D Gradient

$\nabla f(x,y)=(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y})$
normal vector: vector perpendicular to the tangent vector of the curve at that point
gradient points indicate the direction of the f(x,y) > 0 region

• implicit 2D lines
• implicit Quadric Curves
  $Ax^2+Bxy+Cy^2+Dx+Ey+F$

  2.5.3 3D Implicit Surfaces

  $f(x,y,z)=0$

  2.5.4 Surface Normal to an Implicit Surface

  A surface normal is a vector perpendicular to the surface.
  Each point on the surface may havee a different normal vector
  $\vec n = \nabla f(\vec p) = (\frac{\partial f(\vec p)}{\partial x},
  \frac{\partial f(\vec p)}{\partial x},
  \frac{\partial f(\vec p)}{\partial x})$

2.5.5 Implicit Planes

$(\vec p- \vec a) \cdot \vec n = 0 $
$\vec n = (\vec b - \vec a)\times(\vec c - \vec a)$

• 3D Quadric Surfaces
• 3D Curves from Implicit Surfaces
  A 3D curve can be constructed from the intersection of two simultaneous implicit equation

  2.5.6 Parametric Curves

  $\begin{bmatrix} x\y \end{bmatrix} = \begin{bmatrix} g(t)\h(t) \end{bmatrix}$ or $\vec p = f(t)$
• 2D Parametric Lines
  $\begin{bmatrix} x\y \end{bmatrix} = \begin{bmatrix} x_0+t(x_1-x_0)\y_0+t(y_1 - y_0) \end{bmatrix}$
• 2D Parametric Circles
  $\begin{bmatrix} x\y \end{bmatrix} = \begin{bmatrix} x_c+r\cos\phi\y_c+r\sin\phi \end{bmatrix}$

2.5.7 3D Parametric Curves

a spiral aroung the z-axis:
$ x=cost $
$ y=sint $
$ z=t $

• 3D Parametric Lines
  $ \vec p = \vec o + t\vec d$

  2.5.8 3D Parametric Surfaces

  $ x = f(u,v) $
  $ y = g(u,v) $
  $ z = h(u,v) $
• spherical coordinate system
  $ x = r\cos\phi sin\theta $
  $ y = r\sin\phi sin\theta $
  $ z = r\cos\theta $

  2.5.9 Summary of Curves and Surfaces

• implicit curves in 2D / surfaces in 3D
  scalar valued functions: $f: \mathbb{R}^2 \to \mathbb{R}$ or $f: \mathbb{R}^3 \to \mathbb{R}$
  $S = {\mathbf{p} | f(\mathbf{p}) = 0 }$
• Parametric curves in 2D / 3D
  vector valued functions of one variable $\mathbf{p}: D \subset \mathbb{R} \to \mathbb{R^2}$ or $\mathbf{p}: D \subset \mathbb{R} \to \mathbb{R^3}$
  $S = { \mathbf{p}(t) | t \in D }$
• Parametric surfaces in 3D
  vecotr valued functions of two variables
  $\mathbf{p}: \subset \mathbb{R^2} \to \mathbb{R^3}$
  $S = { \mathbf{p}(t) | (u,v) \in D }$

2.6 Linear Interpolation

points are connected by straight line segments
$f(x) = y_{i+1} + \frac{x-xi}{x{i+1}-xi}(y{i+1}-y_i)$
$(1-t)A+B$

2.7 Triangles

2.7.1 2D Traingles

area=$\frac{1}{2} \begin{vmatrix} x_b-x_a & x_c - x_a \ y_b-y_a&y_c-y_a \end{vmatrix}$

This area will have a positive sign if points a,b,c are in counterclockwise order and a negative sign,otherwise

• barycentric coordinate
  $\mathbf{p} = \mathbf{a} + \beta(\mathbf{b}-\mathbf{a}) + \gamma(\mathbf{c} - \mathbf{a}) $
  $\mathbf{p} = (1-\beta-\gamma)\mathbf{a} + \beta \mathbf{b} + \gamma \mathbf{c} $
  $\mathbf{p} = \alpha \mathbf{a} + \beta \mathbf{b} + \gamma \mathbf{c}$ $\alpha+\beta+\gamma=1$

  A particular nice feature of barycentric coordinates is that a point p is insde the triangle formed by a,b,c if and only if
  $0 < \alpha < 1$
  $0 < \beta < 1$
  $0 < \gamma < 1$
  if one of the coordinates is zero and the other two are between zero and one, then you are on an edge, If two of the coordinate are zeor, then the other is one, and you are at a vertex

• how to compute?
  $\begin{bmatrix} x_b-x_a&x_c-x_a \ y_b-y_a&y_c-y_a\end{bmatrix} \begin{bmatrix}\beta\\gamma\end{bmatrix}=\begin{bmatrix}x_p-x_a \ y_p-ya\end{bmatrix}$
  $\beta = \frac{f{ac}(x,y)}{f_ac{x_b,y_b}}$
  $\beta = \frac{(y_a-y_b)x + (x_b-x_a)y + x_ay_b - x_by_a}{(y_a-y_b)x_c + (x_b-x_a)y_c + x_ay_b - x_by_a}$
  $A=A_a+A_b+A_c$ is the area of the traingle
  $\alpha=A_a/A$
  $\beta=A_b/A$
  $\gamma=A_c/A$

  This rule still holds for points outside the triangle if the areas are allowed to be signed. note that these are signed areas and will be computed correctly as long as the same signed area computation is used for both A and subtriangles

2.7.2 3D Triangles

$\mathbf{p} = (1-\beta-\gamma)\mathbf{a} + \beta\mathbf{b} + \gamma\mathbf{c}$
$\mathbf{n=(b-a)\times(c-a)}$
$area=\mathbf{\frac{1}{2}|(b-a)\times(c-a)|}$
$\alpha=\mathbf{ \frac{n \cdot n_a}{|n|^2}}$
$\beta=\mathbf{ \frac{n \cdot n_b}{|n|^2}}$
$\gamma=\mathbf{ \frac{n \cdot n_c}{|n|^2}}$

LearnOpenGL

OpenGL是什么?

API

• glAttachShader()
  把编译的着色器附加到程序对象上
• glGenBuffers()
  生成VBO对象
• glGenVertexArrays()
  生成VAO对象
• glBindBuffer()
  把创建的缓冲绑定到目标
  GL_ARRAY_BUFFER
  GL_ELEMENT_ARRAY_BUFFER
• glBindVertexArray()
  绑定VAO
• glBufferData()
  把用户定义数据复制到当前绑定缓冲的内存中
  GL_STATIC_DRAW
  GL_DYNAMIC_DRAW
  GL_STREAM_DRAW
• glClearColor
• glClear
• glCreateShader()
  创建着色器
  GL_VERTEX_SHADER
  GL_FRAGMENT_SHADER
• glCompileShader()
• glCreateProgram()
  创建程序
• glDrawArrays()
  绘制图元
  GL_TRIANGLES
• glDrawElements()
  绘制，指明从索引缓冲渲染
  从当前绑定到GL_ELEMENT_ARRAY_BUFFER目标中的EBO中获取索引
  GL_TRIANGLES
• glDeleteShader()
• glDisableVertexAttribArray()
• glEnableVertexAttribArray
• glGetShaderiv
  检查编译是否成功
  GL_COMPILE_STATUS
• glGetProgramiv
  检查链接着色器程序是否失败
  GL_LINK_STATUS
• glGetShaderInfoLog()
  编译失败，获取错误消息
• glLinkProgram()
  链接程序对象中的着色器
• glShaderSource()
  把着色器源码附加到着色器对象上
• glUseProgram()
• glVertexAttribPointer
  告诉OpenGL该如何解析顶点数据
• glEnableVertexAttribArray
  启用顶点属性
• glGetUniformLocation
  查询uniform的位置
• glUniform
  设置uniform值
  OpenGL核心是Ｃ写的，不支持重载
  glUniform3f
• glfwGetTime
• glfwWindowShouldClose

glm::ortho()
glm::mat4
glm::perspective
glm::radians

渲染三角形

1. 定义顶点数据
2. 顶点着色器
   • 在GPU上创建内存用于储存顶点数据
   • 配置OPENGL如何解释这些内存
   • 指定如何发送给显卡
   • VBO管理顶点着色器创建的内存（显存中存储大量顶点）
3. 创建着色器并编译
   每个输入变量也叫顶点属性(Vertex Attribute)
   现代OPENGL需要至少设置一个顶点和片段着色器
   着色器语言 GLSL(OpenGL Shading Language)
   顶点属性　vertex attribute
   把着色器对象链接成一个着色器程序对象
4. 链接顶点属性
   －　绑定ＶＡＯ
   －　把顶点数组复制到缓冲中供OpenGL使用
   －　设置顶点属性指针

   GLSL

• uniform

词汇

VAO Vertex Array Object 顶点数组对象
VBO Vertex Buffer Object 顶点缓冲对象
EBO/IBO Element Buffer Object/Index Buffer Object 索引缓冲对象
Graphics Pipeline 图形渲染管线
OpenGL Shading Language GLSL OpenGL着色器语言
Normalized Device Coordinates 标准化设备坐标
图形渲染管线可以被划分为两个主要部分：第一部分把你的3D坐标转换为2D坐标，第二部分是把2D坐标转变为实际的有颜色的像素
2D坐标和像素也是不同的，2D坐标精确表示一个点在2D空间中的位置，而2D像素是这个点的近似值，2D像素受到你的屏幕/窗口分辨率的限制。

###变换

• 转移矩阵
  缩放 位移 旋转
  先缩放，然后旋转，最后位移，否则会影响
  先位移再缩放，位移的向量同样会被缩放
• 万向节死锁 Gimbal Lock
• GLM(OpenGL Mathematics)
  专门为OpenGL设计的数学库

1.2 The Network Edge
host = end system
1.2.1 Access Networks
Home Access: DSL (digital subscriber line) cable FTTH Dial-Up Satellite
hybrid fiber coax

Chapter4: The Network Layer:Data Plane

network layer can be decomposed into two interactiing parts,the data plane and the control plane
what will be coverd?

• per_router functions
• traditional IP forwarding
• generalized forwarding
• IPv4 IPv6 addressing

4.1 Overview of Network Layer

4.1.1 Forwarding and Routing: The Data and Control Planes

• two important network-layer functions:
  • Forwarding in data plane of the network layer
  • Routing in control plane of the network layer

4.2 What’s Inside a Router?

4.2.1 Input Port Processiing and Destination-Based Forwarding

• longest prefix matching

  4.2.2 Switching

• Switching via memory
  • only one memeory read/write can be done at a time.
• Switching via a bus
  • only one packet can cross the bus at a time.
• Switching via an interconnection network
  • crossbar switch non-blocking
  • a packet being forwarding will not be blocked as long as no other packet is currently being forwarded to that output port.

    4.2.3 Output Port Processing

    4.2.4 Where Does Queueing Occur?

• queueing-at both input ports and output ports
• factor: line speed, traffic load, relative speed
• Input Queueing
  • head-of-line(HOL) blocking
    a queued packet in an input queue must wait for transfer through the fabric even though its output port is free
• Output Queueing
  • drop-tail drop the arriving packet
  • active queue management(AQM)
    Random Early Detection(RED)

    4.2.5 Packet Scheduling

• FIFO
• Priority Queueing
  • non-preemptive priority queuing
    the transmission of a packet is not interrupted once it has begun
• Round Robin and Weighted Fair Queueing(WFQ)
  alternates service among different classes in priority
  queueing
  • work_conserving queueing
    move on to the next class in the service sequence when it finds an empty calss queue.(轮到服务你但是你为空我就跳过)
• WFQ each class may receive a different amout of service in any interval of time.

4.3 The Internet Protocol(IP): IPv4,IPv6,Addressing

4.3.1 IPv4 Datagram Format

20 bytes of header(no optons)

• Version number 4bits
• Header length
• Type of service
• Datagram length 16bits long
• Identifier, flags, fragmentation offset
• Time-to-live
• Protocol
  指定IP datagram的data portion应该传给transport-layer的哪种协议
• Checksum
  • 路由器检查到错误就丢弃datagram，因为每经过一个路由器TTL和option（可能）都会改变，所以要重新计算checksum
  • 为什么TCP/IP 在transport layer和networklayer 都要error checking？
  • IP能携带不会传给TCP/UDP的数据
• Source and destination IP address
• Option IPv6没有
• Data(Playload)
  包含transport-layer segment(TCP/UDP)还可以包含其他数据(ICMP)

4.3.2 IPv4 Datagram Fragmentaion

• maximum transmission unit(MTU)
• 为什么要fragmentation?
  因为不同的link-layer protocol有不同的MTU
• fragments need to be reassembled befroe reach transport layer

  4.3.3 IPv4 Addressing

• interface
  • 什么是interface?
  • an IP address is technically associated with an interface, rather than with the host or router containing that interface*
• subnet
  • 如何划分子网
  • 255.255.255.255 广播地址
• subnet mask
  • 注意，路由器之间也算可以构成子网
• DHCP
  dynamic host configuration protocol 自动分配IP地址
  • first-hop router = default gateway
  • DHCP protocol的four-step process
    • DHCP server discovery DHCP discover message
    • DHCP server offer DHCP offer message 同个子网可能有多个DHCP server
    • DHCP request DHCP request message
    • DHCP message DHCP ACK

      4.3.4 Network Address Translation(NAT)

• private network
  • 10.0.0.0/8 是三种保留的IP地址之一
  • NAT translation table 让router知道该把外网的datagram传给哪个host

Chapter5 Network Layer-Control Plane

link state中的oscillation是什么？
distance vecotr中最坏的情况是？

##goals

• understanding principles behind network control plane
• SDN controllers
• Internet Control Message Protocol
• network management
• OSPF BGP OpenFlow ODL ONOS
• ICMP SNMP

5.1 introductino

• two network-layer function
  • forwarding-data plane
  • routing-control plane
• two approches of control plane
  • per-router control
  • logically centralized control
    software defined networking

5.2 routing protocols

• link state
  dijkstra oscillations???
• distance vector
  bellman-ford $D_x(y)=min{c(x,v)+d_v(y)}$
  when link cost change what will happen?
  convergence timn varies, count-to-infinity

5.3 intra-AS routing in the internet:OSPF

• autonomous system(AS)
• intra-AS routing
  routing in same AS
  all routers in AS must run same intra-domain protocol
  • intra-AS routing algorithm
• inter-AS routing
  routing among AS
  • inter-AS routing algorithm
    router in AS1 destined outside of AS1
    propagate rechability info to all routers in AS1
• interior gateway protocols(IGP)
  ##intra-AS routing protocols:
• RIP routing information protocol
• OSPF open shortest path
  use link-state algorithm
  carried in OSPF messages directly over IP
  like IS-IS routing protocol
  • hierarchical OSPF
    two-level hierarchy: local area, backbone
    link-state advertisement only in area
    • area border routers
    • backbone routers
    • boundary routers
• IGRP interior gateway routing protocol

5.4 inter-AS routing

BGP(border gateway protocol)
eBGP
iBGP

• BGP session: over TCP connection
  advertise: prefix(destination)+attributesd = route
  two attributes
  AS-PATH
  NEXT-HOP
  policy-based routing
  how BGP path advertisement works?
  BGP route slection
  • local preference-policy
  • shortest AS-PATH
  • closest NEXT-HOP-hot potato routing
  • additional criteria

    different between inter/intra routing

• policy
  inter-AS: admin wants to control how traffic is routed
  intra-AS: no need
• scale
  hierarchical routing saves table size, reduced update traffic
• performance
  intra-AS: can focus on performance
  inter-AS: policy may dominate over performance

5.5 software defined networking(SDN)

• network control applications
• SDN controller
• network switches
• openflow protocol
  controller to switch message
  switch to controller message

5.6 ICMP(internet control message protocol)

• ICMP
  used by hosts & routers to communicate
  ICMP msgs carried in IP datagrams
  format type+code+first 8 bytes of IP datagram
  source send UDP to routers and routers back ICMP(name of routers and ip address)

5.7 network management

managed devices contain managed objects whose data is gathered into a management information base(MIB)

• SNMP protocol
  • request/response mode
  • trap mode

Chapter6

##goals

• understand principles behind link layer services
  • error detection, correction
  • sharing a broadcast channel: multiple access
  • link layer addressing
  • local area networks: Ethernet, VLAN
• instantiation, implementation of various link layer technologies

##6.1 introduction, services
link layer transfer datagram from one node to physically adjacent noe over link
datagram transferred by different link protocols over different links

link protocols

ethernet, ppp, 802.ii

link layer services

• framing, link access
  encapsulate datagram into frame
  mac addresses used in frame header to identify source, destination
• reliable delivery between adjacent nodes
  seldom used on low bit-error link(fiber, twisted pair)
  why both link-level and end-end reliability
• flow control
• error detection
  error caused by signal attenuation, noise
• error correction
  receiver identifies and corrects bit errors(s)
• full-duplex / half-duplex

  link layer implemented

• in each and every host
• implemented in adaptor(network interface card NIC)

  adaptor communicating

sending side

• encapsulates datagram in frame
• adds error checking bits, rdt, flow control
  recieving side
• looks for errors, rdt, control
• extracts datagram, passes to upper layer

6.2 error detection/correction

error detection

EDC

parity checking

single bit parity
two-dimensional bit parity

internet checksum

used at transport layer only

cyclic redundancy check

D:data G: r+1 bit pattern
D: data to be sent R:CRC bits
D*2^r XOR R
example

6.3 multiple access protocols

two types of links

• point-to-point

  ppp for dial-up access
  

• broadcast(shared wire or medium)

  upstream HFC
  802.II wireless LAN
  

  collision if node reveives two or more signals at the same time
  multiple access protocol
  desired properties

  MAC protocols: taxonomy

  channel partitioning
  divide channel into pieces
  random access
  channel not divided, allow collisions
  taking turns
  nodes with more to sent can take longer turns

  channel partitioning MAC protocols

  TDMA time division multiple access
  access to channel in rounds, each station get fixed slot
  FDMA frequency division multiple access

  random access MAC protocol

  slotted ALOHA
  efficiency
  max efficiency = 1/e = 3.7
  ALOHA
  max efficiency = 1/2e = 2.8
  CSMA
  CSMA/CD
  binary(exponential)backoff
  CSMA + CD(collision detection)
  easy in wire LANs: measure signal strength, compare transmitted, received signals
  difficult in wireless LANs: received signal strenth overwhelmed by local transmission strength
  , CSMA/CA**
  carrier sense multiple access
  CSMA listen before transmit
  if channel sesed idle,transmit entire frame
  if channel sensed busy, defer transmission
  transmit at full channel data rate R
  two or more transmitting nodes->collision

• how to detect collisions
• how to recover from collisions

  taking turns protocols

  FDDI, bluetooth, token ring
  polling
  token passing

6.4 LANs

MAC addresses and ARP

ip address MAC(LAN or physical or Ethernet) address
MAC flat address -> protability
can move LAN card from one LAN to another
IP hierarchical address - > unprotable
address depends on IP subnet to which node is attached
ARP:address resolution protocol
ARP table

Ethernet

wired LAN technology

physical topology

• bus coaxial cable
• star switch

  frame structure

  sending adapter encapsulates IP datagram in Ethernet frame
• preamble
• addresses
• type

  Ethernet is unreliable, connectionless

• connectionless: no handshaking between sending and receiving NICs
• unreliable: receiving NIC doesn’t send acks or nacks
• ethernet’s mac protocol
• unslotted CSMA/CD with binary backoff

  802.3 Ethernet standards: link & physical layers

  common MAC protocol and frame format
  different speeds: 2 Mbps, 10Mbps, 100Mbps
  different physical layer media: fiber, cable

  Ethernet switch

  switch

• link-layer device: takes an active role
• transparent

  hosts are unaware of presence of switches
  

• plug-and-play self-learning

  switches do not need to be configured
  

• switching can transmit simultaneously

  switch forwarding table

  each switch has a switch table
  switch learns which hosts can be reached through which interfaces

  properties of link-layer switching

• elimination of collisions
• heterogeneous links
• management

  different between switches and routers

• routers
  network-layer devices
  compute tables using routing algorithms, IP addresses
• switches(no network layer)
  link-layer devices
  learn forwarding table using flooding, learning, MAC addresses

  VLANs

  virtual local area network
  define multiple virtual LANs over single physical LAN infrastructure

  port-based VLAN

• traffic isolation
• dynamic membership

  ports can be dynamically assigned among VLANs
  

• forwarding between VLANS

  done via routing(just as with separate switches)
  

  VLANs spanning multiple switches

  trunk port
  carries frames between VLANS defined over multiple physical switches
  802.I q protocol adds/removed additional header fields for frames forwarded between trunk ports

  wireless LANs

  802.II LAN architecture

  AP(base station=access point)
  BSS(basic service set)

  802.II channels, association

6.7 a day in the life of a web request

• DHCP
  dhcp request encapsulated
  -UDP
  -IP
  -802.3 Ethernet
  -broadcast(dest:全F)
  -ethernet demuxed to ip demuxed to udp demuxed to dhcp
  client now has ip address, name & address of DNS server, ip address of its first-hop router
• DNS
  DNS encapsulated
  -UDP
  -IP
  -ARP
  client now knows MAC address of first hop router
• TCP
• HTTP

MOEA/D

Main idea

approximation of the PF can be decomposed into a number of scalar objective optimization subproblems.

• Why This decompostion works? What’s the mechanism?
  • most important, because all of the algorithm is based on this theorm

Question

For each Pareto optimal point $x^$, there exists a weight vector $\lambda$ such that $x^$ is the optimal solution of $g^{te}(x|\lambda,z^)$ and each optimal solution of $g^{te}(x|\lambda,z^)$ is a Pareto optimal solution.

• is there a unique solution $x^$ of $g^{te}(x|\lambda,z^)$ for a given $\lambda$ and $z$? making $x^$ = $Arg{g^{te}(x|\lambda,z^)}$
• proof
  $x^$ is a pareto optimal point, $\forall x \in \Omega ,\exists$ at least one $i$, $s.t$ $f_i(x^) > fi(x)$ we choose such $\lambda$ that $\max \limits{1\leq j\leq m} {\lambda_j| f_j(x) - z_j^|} = \lambda_i|f_i(x)-z_i^|$ since $|f_i(x^)-z_i^| < |f_i(x)-z_i^|$ $min{g^{te}(x^|\lambda,z^)} = \lambda_i|f_i(x^)-z_i^|$. thus $x^$ is the optimal solution of $g^{te}(x|\lambda,z^*)$.
  • but this leading to another question
    for different pair of $(x^, x)$ the $i$ may be different, which means different $\lambda$. It seems that no unique $\lambda$ can hold for all condition for a given pareto optimal point $x^$

Major motivation

any information about these $g^{te}(x|\lambda,z^)$ with weight vectors close to $\lambda^i$ should be helpful for optimizing $g^{te}(x|\lambda,z^)$.

which parts in MOEA/D need problem-specific method?

1. when generate initial population
2. when initialize referrence points
3. after generating y’ using problem-specific repair/improvement heuristic

   plan description of MOEA/D

• every time we optimize N scalar subproblem
• the ith subproblems was assgined with a $x^i$ and $\lambda^i$
• update among one neighbour
• for every subporblem, consider it’s neighbour, generate a new child y from it and update all the solutions to subproblems belongs to this neighbour.
• update EP

1. INTRODUCTION

• dominate
• decision(variable) Pspace
• attainable objective set
• Pareto optimal(objective) vector
• Pareto optimal points
• Pareto set(PS)
• Pareto front

2.DECOMPOSITION OF MULTIOBJECTIVE OPTIMIZATION

• A. Weighted Sum Approach [1]
• B. Tchebycheff Approach [1]
• C. Boundary Intersection(BI) Approach

3.THE FRAMEWORK OF MOEA/D

• A. General Framework

  • neighborhood of the i th subproblem

• B. Discussions

  • Why a Finite Number of Subproblems are considered?
  • How diversity is Maintained?
  • Matiing restriction and role of T

• C. Variants of MOEA/D

  • step 2.2 is not a must in MOEA/D
  • EP is an option

    4. COMPARISION WITH MOGLS

• C. MOKP

  • NP-hard

• D. Implementations

  5. COMPARISON WITH NSGA-II

• objective normalization

Futher reading

• approximate the PF by using a mathematical model [5]-[8]
• cMOGA [40] Hisao

「任何事都需要代价，一切所能看到或者看不到的」

• 我发现它可能是神设计世界时的 基本哲学
• 目前所感悟到的道理中最基本的一条

• 暂且将其称为等价交换原则：

  对任何任务T，存在代价P：
  使得T为真的条件是当且仅当支付代价P以实现任务T
  $\forall task(T)\quad\exists price(P) \quad s.t. \quad T \iff Exchange(T,P)$

随着年龄的增长，需要支付的代价会越来越高，直到某一天不能忍受，然后就自杀

就像熬夜短期内却看不到危害一样

第一次对代价有体会是在初中时代，用空间换时间，以时间换空间——消耗存储空间来加快程序运行速度，或者牺牲程序运行速度来节省储存空间——写程序经常会面临的选择。当时我未曾引起足够的重视。毕竟一个初中生有什么其他特别值得担心的事呢。

进入大学后，也经常遇到实际设计中牺牲一个性能换取另一个性能提升的情况。此时我仍然乐观地认为这只是工程师们所面临的一些现实世界的困难，毕竟不完美是世界这个复杂系统所具有的基本属性，与我没有太大的关系，仍然无需多虑。

直到我慢慢发现自己开始不得不考虑现实生活中的复杂问题,并为之开始支付代价。

因为一次意外造成的后遗症，没办法完全集中精力学习，在大学这3年确实给我带来了很多困难

现在认为这不过是一种必须偿还代价，作为一种对过错的惩罚

借太宰治的一句话

我急切地盼望着可以经历一场放纵的快乐，纵使巨大的悲哀将接踵而至，我也在所不惜。

「获得力量需要支付代价，有时力量的使用也需要代价」

务要惜精神

小说，游戏，和动画作品中经常出现类似桥段。《结城友奈是勇者》中，满开系统可以短时间提高力量，代价是之后身体的某一项机能完全丧失。
没有什么力量可以凭空得到

• 支付代价只是必要条件
• 不存在两全其美的方法
• 一次支付的代价可能是复数的

Chapter 1: Introduction

1.1 Graphics Areas

1.2 Major Applications

1.3 Graphics APIs

1.4 Graphics Pipeline

• special software/hardware subsystem that efficiently draws 3D primitives in perspective
• basic operations map the 3D vertex locations to 2D screen postions and shade the triangles
• 4D coordinates system

1.5 Numerical Issues

• IEEE floating-point standard
  • Three special values for real numbers
    1. Infinity($\infty$)
       a valid number that is larger than all other valid numbers.
    2. Minus infinity($-\infty$)
       a valid number that is smaller than all other valid numbers.
    3. Not a number(NAN)
       an invalid number
    • $\infty + \infty = +\infty$
    • $\infty - \infty = NaN $
    • $\infty \div \infty = NaN$
    • $ 0/0 = NaN $
    • Any aritmetic expression that includes NaN results in NaN.
    • Any Boolean expression involving NaN is false.

1.6 Efficiency

efficiency is achieved through careful tradeoffs

1.7 Designing and Coding Graphics Programs

1. Class Design
   some basic classes to be written include:
   • vector2
     A 2D vetor with indexing, vector addition, vector subtraction, dot product, cross product, scalar multiplication, scalar division.
   • vector3
     A 3D vector class analogous to vector2
   • hvector
     A homogeneous vector with four components
   • rgb
     An RGB color with RGB addtion, RGB substraction,RGB multiplication, scalar multiplication, scalar division
   • transform
     A 4*4 matrix for transformations. should include a matrix multiply
   • image
     A 2D array of RGB pixels with an output operation.
2. Float vs. Double
   • Modern architecture suggests that keeping memory use down and maintaining coherent memory access are the keys to efficiency.this suggests using single precision data
   • however, avoiding numerical problems suggests using double-precision arithmetic. The tradeoffs depend on the program.

Chapter3. Solvinig Problems by Search

3.5 INFORMED(HEURISTIC)SEARCH STRATEGIES

3.5.1 Greedy best-first search

3.5.2 A* search

1. Minimizing the totoal estimated solution cost

• $f(n) = g(n) + h(n)$
  • h(n) is the estimated cost of the cheapest path from n to the goal
  • g(n) the cost to reach the node

1. Conditions for optimality: Admissibility and consistency

• $h(n)$ be an admissible heuristic
  • an admissible heuristic is one that never overestimates the cost to reach the goal.
  • an example of admissible heuristics is the straight-line distance $h_{SLD}$
• $h(n)$ be an consistency(monotonicity)
  • required only for applications of A* to graph search
  • A heuristic $h(n)$ is consistent if, for every node $n$ and every successor $n’$ of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to $n’$
    $h(n) <= c(n,a,n’) + h(n’)$
  • every consistent heuristic is also admissible

1. Optimality of A*

   • tree-search version of $A$ is optimal if $h(n)$ is admissible
   • graph-search versioin is optimal if $h(n)$ is consistent
     • fisrt establish: if $h(n)$ is consistent, then the values of f(n) along any path are nondecreasing
     • second prove: whenever $A$ selects a node n for expansion, the optimal path to that node has been found.*
     • A* search is complete, optimal, optimally efficient
     • prunning, optimally efficient, absolute error, relative error
     • There can be exponetially many states with $f(n) < C*$ even if the absolute error is bounded by a constant.

3.6 HEURISTIC FUNCTIONS

3.6.1 The effect of heuristic accuracy on performance

• effective branching factor
• why $h_2$ is better than $h_1$?

  3.6.2 Generating admissible heuristics from relaxed problems

• relaxed problem
  A problem with fewer restrictions on the action
  the cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem

  3.6.3 Generating admissible heuristic from subproblems:Pattern databases

• patern databases, subproblem, disjoint pattern databases
• Admissible heuristic can also be derived from the solution cost of a subproblem of a given problem.

  3.6.4 Learning heuristic from experience

  feature
• to construct a heuristic function?
  • devise relaxed problems
  • learn from experience