ÚCARENYA wiki

wiki:cs_se

MeaCulpa — Mon, 12 Dec 2011 02:12:00 -0600

Software Engineering Quiz

名词解释

CRC

Cyclic redundancy check
循环冗余检测
Class-Responsibility-Collaborator
类-职责-协作者

QFD

Quality Function Deployment
品质机能展开/质量功能解开

OOHDM

Object Oriented Hypermedia Design Method
面向对象的超媒体设计方法

PERT

Program (or Project) Evaluation and Review Technique
程序评估及评审技术

CBSE

Component-based Software Engineering
基于构件的软件工程

简答题

1 计算机软件的分类及解释(P61)

系统软件：一套服务于其他程序的程序
应用软件：可以满足特定业务需要的独立应用程序
工程/科学软件：科学和工程广阔领域用到的软件
产品线软件：为多个不同用户提供特定功能
嵌入式软件：存在于某个产品或者系统中，可实现和控制面向最终使用者和系统本身的特性和功能
WEB应用软件：给予web交互的软件
人工智能软件：利用非数值算法解决计算和直接分析无法解决的复杂问题

——

系统软件：系统软件是一套服务于其他程序的程序。某些系统软件处理复杂但确定的信息结构，某些系统应用程序主要处理不确定的数据。

应用软件：应用软件是一些可以满足特定业务的需要的独立应用程序，应用软件处理商或技术数据，以协助业务操作和管理或技术决策。

工程/科学软件：带着“数字处理”的算法的标签，工程和科学软件涵盖广泛的应用领域，不仅仅局限于传统的数值算法，计算机辅助设计、系统仿真和其他交互性应用程序已经呈现出实时和系统软件的特性。

嵌入式软件：嵌入式软件存在于某个产品或系统中，可实现和控制面向最终使用者和系统的特性和功能。

产品线软件：产品的设计方向是为多个不同用户的使用提供特定功能，关注有限的特定市场或者大众消费品市场。

WEB应用软件：Web应用的概念涵盖了宽泛的应用程序产品。最简单的可以是一组超文本链接文件，仅仅用文本和有限的图形表达信息。随着电子商务和B2B应用的日益重要，网络应用正在发展为复杂的计算环境，不仅为最终用户提供标准特性、计算功能和内容信息，还与企业数据库和商务应用程序相结合。

人工智能软件：人工智能软件利用非数值算法解决计算和直接分析无法解决的复杂问题。这个领域的应用程序包括机器人、专家系统、模式识别、人工神经网络、定理证明和博弈等。

2 统一过程（UP）的特点，所包括的4个阶段及其主要任务(P52)

统一过程: 用例驱动、以架构为核心，迭代并且增量的软件过程框架

初始：inception. 阶段包括客户沟通和策划活动
细化：elaboration. 阶段包括用户沟通和通用过程模型的建模活动
构建：construction. 采用体系结构模型作为输入，开发或获取软件构件，使得最终用户能够操作用例
转化：transition. 软件被提交给客户进行Beta测试，用户反馈报告缺陷及必要的变更，开发团队创建支持信息
生产: production. 监控软件的持续使用，提供运行环境（基础设施）的支持，提交并评估缺陷报告和变更请求

3 极限编程（XP）的四个阶段及各阶段所使用的主要方法/工具

策划：

> 策划活动开始于建立一系列描述待开发软件必要特征与功能的用户故事。由客户根据对应特征或功能的全局业务价值标明权值。XP团队决定和调整验收测试准则和开发迭代计划。

设计：

> XP设计严格遵守KIS（保持简洁）的原则。使用CRC卡作为有效机制。如果某个故事设计中遇到困难，XP推荐立即建立这部分设计的可执行原型，实现并评估设计原型（Spike解决方案）。

编码：

> 结对编程，即推荐2个人使用同一台计算机共同为一个故事开发代码，这一方案提供了实时解决问题和实时质量保证的机制。结对的人完成其工作后，由集成团队进行集成，或者由结对者自己负责集成。这种连续集成策略有助于避免兼容性和接口问题，建立能及早发现错误的“冒烟测试”环境。

测试：

> 在编码开始之前建立单元测试，所建立的单元测试应当使用一个可以自动实施的框架，以支持代码修改后的回归测试。将个人的单元测试组织到一个通用测试集，每天都可以进行集成测试和确认测试。XP验收测试也称为客户测试，由客户确定，将着眼于客户可见的、可评审的系统级特征和功能。

4 QFD是一种将客户要求转化成软件技术需求的技术，三种需求及其简单说明

正常需求：也称普通需求，包含客户对项目的最基本需求，是客户对整个项目最为关心的部分。
期望需求：客户可能没有表达明确或没有明确提出的需求，但是会让客户提升对项目的满意度。
令人兴奋的需求：也称以外需求，如果实现会给客户带来惊喜，但是如果无法实现也不会受到客户责备。

5 在对用例分析的过程中，寻找分析类的途径? 及其示例(P160)

通过检查问题的陈述，或通过对为系统开发的用例或处理叙述进行“语法分析”，可以开始类的识别。带有下划线的每个名词或名词词组可以确定为类，并将这些名词输入到一个简单的表中，同义词应被标注出。如果要求某个类实现一个解决方案，那么这个类就是解决方案的一部分；否则如果某个类只需要说明一个解决方案，那么这个类就是问题空间的一部分。

外部实体：产生或使用基于计算机的系统的信息，例如设备、人员
事物：问题信息域的一部分，例如报告、显示、字母、信号
发生或者事件：在系统操作环境内发生，例如电话呼叫、警报、所有权转移
角色：由和系统交互的人员扮演，例如经理、工程师、销售人员
组织单元：和某个应用有关，比如部门、组、团
场地：例如制造车间或码头，建立问题的环境和系统的整体功能
结构：例如传感器、计算机，定义了对象的类或与对象有关的类

6 分析类的分类方法及其说明(P165)

实体类：从问题中的说明中直接提取出来的，也被称作模型或者业务类。这些类一般代表保存在数据库中的和贯穿应用程序的事物。
边界类：用于创建用户可见的和交互的接口。边界类被设计成负责管理实体对象对用户的表现方式。
控制类：自始至终管理工作单元。控制类可以管理实体类的创建或更新，当边界类从对象获取信息后的实例化，对象集合间的复杂通信，确认对象间交换的数据或用户和应用程序间交换的数据。

7 图8-21 根据用例说明画顺序图或状态图（必考）

SafeHome 安全功能的部分用例：房主使用键盘输入4位密码，该密码和保存在系统中的验证密码相比较，如果密码不正确，控制面板将鸣叫一声并复位以等待下一次输入，如果密码正确，控制面板等待进一步操作。

8 组织良好的设计类的四个特征，简要说明(P188)

完整性与充分性：设计类应该完整地封装所有的，可以合理预见会存在于类中的属性和方法。
原始性：和某个设计类相关的方法应关注于实现类的某个服务。一旦服务已经被某个方法实现，类就不应该再提供另外一个完成同一事情的方法。
高内聚性：一个内聚的设计类具有小的、集中的职责集合，且专注于使用属性和方法来实现这些职责。
低耦合性：设计类间相互协作是必然的，但协作应该保持在一个可以接受的最小范围内。高耦合会导致系统难以实现、测试和维护。

9 接口设计的三个重要元素(P191)

用户界面（UI）：UI设计是软件工程的主要活动，UI设计包含美学元素、人机工程元素和技术元素。通常，UI是整个应用体系结构内独一无二的子系统。
外部接口：外部接口的设计需要关于发送和接收信息的实体的确定信息。外部接口设计应包括错误检查和适当的安全特征。
内部接口：内部接口的设计和构件级的设计紧密相关。分析类的设计实现体现了包含如下内容的方案：在各种类的运作之间实现通信和协作所必需的所有操作和消息发送模式。每个消息的设计必须提供必不可少的信息传递和已被请求的操作的特定功能需求。

10 体系结构风格的简单分类(P203)

以数据为中心：数据存储驻留在这种体系结构的中心，其他构件会经常访问该数据存储，并对存储中的数据进行更新、增加、修改和删除。
数据流：当输入数据经过一系列的计算和操作构件的变换形成输出数据时，可以应用这种体系结构。
调用和返回：该体系结构风格能够让软件设计师设计出一个相对易于修改和扩展的程序结构。有2种子风格，主程序/子程序体系结构，远程过程调用体系结构。
面向对象：系统构件封装了数据和必须应用到该数据的操作，构件间通过信息传递进行通信和合作。
层次体系结构：层次体系结构的基本结构定义了一系列不同的层次，每个层次各自完成操作，这些操作不断接近机器的指令集，最外层的构件完成用户界面的操作，最内层的构件完成与操作系统的连接，中间层的构件提供各种实用程序服务和应用软件功能。

11 界面设计过程中，从减轻用户记忆负担角度出发，可以遵循的原因5个（必考P255）

减少对短期记忆的要求：当用户陷于复杂的任务时，短期记忆的要求将会很大。界面的设计应该尽量不要求记住过去的操作和结果。可行的解决方法是通过提供可视的提示，使得用户能够识别过去的动作，而不是必须记住它们。
建立有意义的缺省：初始的缺省集合应该对一般的用户有意义，但是用户应该能够说明个人的偏好。
定义直观的快捷方式：当使用助记符来完成系统功能时，（如Alt+P激活打印功能），助记符应该以容易记忆的方式被联系到相关动作（被激活的动作的第一个字母）。
界面的视觉布局应该基于真实世界的象征：例如一个账单支付系统应该使用支票簿和支票登记簿来指导用户的账单支付过程，这使得用户能够依赖于能很好理解的可视提示，而不是记住复杂难懂的交互序列。
以不断进展的方式解释信息：界面应该以层次化的方式进行组织，即关于某任务、对象或行为的信息应该首先在在高抽象层次上呈现，更多细节应该在用户用鼠标点击表示兴趣后再展示。

12 WEBAPP的特性说明 10个性质(P363)

网络密集性：WebApp驻留在网络上，服务于不同客户群体的需求，网络可以指内联网或者外联网。
并发性：在同一时间可能有大量用户同时使用webapp，很多情况下，最终用户的使用模式存在很大差异。
无法预计的负载量：Webapp的用户数量每天都可能会有数量级的变化。
性能：如果一位webapp用户需要等待很长时间（访问、服务器端处理、客户端格式化显示），该用户就会转向其他地方。
可得性：尽管百分之百的可得性是不切实际的，但是大多数webapp用户通常要求24/7/365（全天候）的可访问性。
数据驱动：许多webapp的主要功能是使用超媒体向最终用户提供文本、图片、音频及视频内容。除此之外，webapp用来访问那些存储在数据库中的信息，这些数据库最初并不是基于web的环境的整体组成部分。
内容敏感性：内容的质量和艺术性仍然在很大程度上决定了webapp的质量。
持续演化：传统的应用程序是随一系列规划好的时间间隔发布而演化的，而webapp则持续的演化。
即时性：尽管即时性是很多应用领域的特点，然而将webapp投入市场可能只是几天或者几周的事情。Web工程师必须使用经过修改的计划、分析、设计、实现和测试的方法以满足webapp开发所需要的紧迫的时间进度安排。
保密性：为了保护敏感的内容，并提供保密的数据传输模式，在支持webapp的整个基础设施上和应用本身内部必须实现较强的保密措施。
美学性：Webapp具有吸引力的一个不可否认的部分是其观感。当要向市场推销产品或想法时，与技术设比相比，美学可能同样事关该应用的成功。

13 WEB工程团队的角色职责(P380)

内容开发者或提供者：因为WebApp本质上是内容驱动的，web团队成员的角色必须着重于内容的生成和收集，内容开发者或提供者可能来自不同的专业背景。
Web出版者：必须对内容开发者或提供者生成的多种多样的内容进行组织，使这些内容包含在webapp中。充当技术人员和非技术内容开发者或提供者之间的联络人，他必须了解内容和webapp技术。
Web工程师：Web工程师参与webapp开发过程中的一系列活动，包括需求导出、分析建模、体系结构、导航和界面设计、webapp实现和测试。要对webapp开发的各种相关软硬件技术知识有很好的了解。
业务领域专家：一个业务领域专家应该能够回答与业务目标和webapp需求相关的所有问题。
支持专家：应该将这个角色分给长期负责webapp支持的人员，因为webapp持续地演化，支持专家负责站点纠错、适应性修改和增强。
管理者：通常称之为web站长，他负责webapp的日常运作，包括：为webapp运行而制定开发和实现政策，支持和反馈规程的建立，安全过程和访问权限的实现，web站点流量的度量和分析，变更控制规程的协调，以及同支持专家协调。管理者也可能参与到web工程师和支持专家进行的技术活动中。

14 WEBAPP的测试 5个方法(P437)

内容：在语法和语义层对内容进行评估。在语法层，对基于文本的文档进行拼写、标点和文法方面的评估；在语义层，正确性、一致性以及清晰性都要评估。
功能：对功能进行测试，以发现与客户需求不一致的错误。对每一项webapp功能评定其正确性、不稳定性及与相应的实现标准的总体符合程度。
结构：对结构进行评估，以保证它正确地表示webapp的内容和功能，是可扩展的，及支持新内容、新功能的增加。
可用性：对可用性进行测试，以保证接口支持各种类型的用户，各种用户都能学会及使用所有导航语法和语义。
导航性：以保证检查所有的导航语法和语义，发现任何导航错误。
性能：在各种不同的操作条件、配置及负载下，对性能进行测试，以保证系统响应用户的交互并处理各种
极端的负载情况，而且没有出现不可接受的操作上的性能降低。
兼容性：在客户端及服务器端，在各种不同的主机配置下通过运行webapp对兼容性进行测试，目的是发现针对特定主机配置的错误。
互操作性：对互操作性进行测试，以保证webapp与其他应用系统或数据库有正确接口。
安全性：对安全性进行测试，通过评定可能存在弱点，试图对每一个弱点进行攻击，任何成功的突破尝试都被认为是一个安全漏洞。

15 软件团队的四种“组织范型”(P466)

封闭式范型：按照传统的权利层次来组织团队。当开发与过去已经做过的产品相似的软件是，这种团队十分有效，但在这种封闭式范型下难以进行创新性的工作。
随机式范型：松散的组织团队，团队工作依赖于团队成员个人的主动性。当需要创新或技术上突破时，这种团队很有优势，但当需要有次序的执行才能完成工作时，这种团队就会陷入困境。
开放式范型：试图以一种既具有封闭式范型的控制性，又包含随机式范型的创新性的方式来组织团队。工作是大家相互协作完成的，良好的沟通和根据团队整体的意见做出决策是开放式范型的特征。特别适合于解决复杂的问题，但是可能不像其类型的团队那么有效率。
同步式范型：依赖于问题的自然划分，组织团队成员各自解决问题的一部分，他们之间没什么主动的交流

16 软件范围如何定义描述(P470)

软件项目管理的第一项活动是确定软件范围，软件范围是通过回答下列问题来定义的。
项目环境：要开发的软件如何适应于大型的系统、产品或业务环境，该环境下需要施加什么约束？
信息目标：软件要产生哪些客户可见的数据对象来作为输出？需要什么数据对象作为输入？
功能和性能：软件要执行什么功能才能将输入数据变换为输出数据？软件需要满足什么特殊的性能要求吗？
软件项目范围在管理层和技术层都必须是无歧义和可理解的，对软件范围的描述必须是界定的。即，要明确给出定量的数据；说明约束和限制，并且描述其他的缓解因素。

gct

wiki:gct_cs

MeaCulpa — Sat, 03 Dec 2011 07:08:47 -0600

GCT CS

Final

quiz sample 1

CPU性能公式，简单计算 L01-ch1.pdf: 计算CPI: Page 33

Op	Freqency	Cycle count
ALU op	43%	1
Loads	21%	1
Stores	12%	2
Branches	24%	2

if store can do in 1 cycle but slow down clock 15%

awk "BEGIN {print 0.43 + 0.21 + 0.12*2 + 0.24*2 }" = 1.36
awk "BEGIN {print 0.43 + 0.21 + 0.12 + 0.24*2 }" = 1.24

t/p = P * CPI * T old = 1.36 new = 1.24 * 1.5 = 1.86

Don't make the change!

quiz sample 2

amdhal 加速比 spdup page 55- page56

加速比 = 1 / (未提升部分 + (提升部分/提升比例))

95%的部分得到提升，提升10%的话，加速比是1.094 5%的部分得到提升，提升10倍，加速比只有1.047

quiz sample 3

降低失效率的方法之一，编译器优化：

数组合并，循环交换，循环融合，分块

Cache优化中的数组合并

/* Before: 2 sequential arrays */
int val[SIZE];
int key[SIZE];

/* After: 1 array of stuctures */
struct merge {
	int val;
	int key;
};
struct merge merged_array[SIZE];

Reducing conflicts between val & key; improve spatial locality 减少了key和value的冲突失效，提高了空间局部性

Cache优化中的循环融合

/* Before */
for (i = 0; i < N; i = i+1)
	for (j = 0; j < N; j = j+1)
		a[i][j] = 1/b[i][j] * c[i][j];
for (i = 0; i < N; i = i+1)
	for (j = 0; j < N; j = j+1)
		d[i][j] = a[i][j] + c[i][j];

/* After */
for (i = 0; i < N; i = i+1)
	for (j = 0; j < N; j = j+1)
	{	a[i][j] = 1/b[i][j] * c[i][j];
		d[i][j] = a[i][j] + c[i][j];}

2 misses per access to a & c vs. one miss per access; improve spatial locality 2次miss vs 一次miss, 提高空间局部性

Quiz

什么是计算机体系结构？体系结构的分层模型？简述Amdahl定律？
简述R-R、R-M、M-M型指令及其特点。
对于运算x=a-b+c，分别写出基于堆栈、累加器、Load/Store、R_M（1，3）、M_M（3，3）型ISA的伪代码指令序列。
结合CPU性能公式，分析CISC和 RISC指令集的功能设计。
编译技术对计算机体系结构有哪些方面的影响？
CISC架构的主要缺陷？它为何能在计算机发展历程上长期占有重要地位？
何谓结构相关？一般有哪些解决方法？何谓数据相关？一般有哪些解决方法？
何谓控制相关？一般有哪些解决方法？
什么是指令的动态调度和静态调度？各自有什么优缺点？
实现多指令流出，目前主要采用哪些技术？各自的技术特点是什么？
多指令流出处理器的性能受到哪些方面的限制？
什么是存储层次？哪些应用适合用单级存储结构？哪些应用适合使用多级存储结构？
引入cache的理论依据是什么？使用cache有什么优缺点？
Cache的二种写策略及其特点？
简述cache失效的3C分类。
降低Cache的失效率主要有哪些方法？
降低Cache的失效开销主要有哪些方法？
降低Cache的命中时间主要有哪些方法？
对于一定容量的Cache，当块大小有小变大时，失效率为什么先下降，后又上升？对于16KB的Cache，合适的块大小一般是多少？
简述Victim Cache的原理？
对于磁盘存储介质，衡量记录密度的指标是什么？它又取决于哪二个参数指标？
PCI、USB、FireWire、MMU、MPU、MIPS、CPI、IPL？
什么是RAID？简述RAID3、RAID5的主要技术特征。
简述向量机的部件组成，向量处理器的特点？对以下于运算, 试写出其对应的标量指令序列和向量指令序列。
- ```
For (I=0; I<100; I++) Q[I]=A[I]*B[I]+D[I]*(E[I]-5)
```
什么是SIMD？简述MIMD并行机的二种组成结构。
针对计算机体系结构的软件优化技术一般应考虑哪些方面？

Answers

什么是计算机体系结构？体系结构的分层模型？简述Amdahl定律？

体系结构

In its broadest definition, computer architecture is the design of the
abstraction layers that allow us to implement information processing
applications efficiently using available manufacturing technologies.

计算机体系结构是对我们如何利用现有的制造技术来实现信息处理应用的抽象层的设计

分层模型

Application 应用
Algorithm 算法
Programming Language 编程语言
Operating System/Virtual Machinese 操作系统/虚拟机
Instruction Set Architecture (ISA) 指令集
Microarchitecture 微架构
Gates/Register - Transfer Level (RLT) 寄存器，逻辑门，传输层
Circuits 电路
Devices 设备
Physics 物理层

Amdhal 定律

⇒

加速比 = 1 / (未提升部分 + (提升部分/提升比例))

简述R-R、R-M、M-M型指令及其特点

The basic operation in the processor is a register-to-register

  instruction of the following format: This operation takes two source
  registers and , performs a dyadic operations on them and stores the
  resulting value in . As usual may be replaced by a small immediate
  constant.

R-M
- Any operation can access memory
- First operand is loaded from the memory into a register
- Operation is performed on the register and the second operand (from the memory)
- Both operands and location of result are explicit
- Result is written into a register
- Result has to be explicitly stored back into memory

M-M
Operation is performed on the memory locations
Result is written into the memory

对于运算x=a-b+c，分别写出基于堆栈、累加器、Load/Store、R_M（1，3）、M_M（3，3）型ISA的伪代码指令序列。

Stack Based

push a

push b
sub
push c
add
pop x

Accumulator

load a

sub b
add c
store x

LOAD/STORE

load R1, a

load R2, b
sub R3, R1, R2
load R4, c
sub R5, R3, R4
store R5, x

load R1, a

sub R3, R1, b
add R4, R3, c
store R4, x

sub t, a, b

add x, t, c

结合CPU性能公式，分析CISC和 RISC指令集的功能设计

* CPU 性能公式:

From CISC to RISC

Use fast RAM to build fast instruction cache of

user-visible instructions, not fixed hardware microroutines

Can change contents of fast instruction memory to fit what

application needs right now

Use simple ISA to enable hardwired pipelined

implementation

Most compiled code only used a few of the available CISC

instructions

Simpler encoding allowed pipelined implementations

Further benefit with integration
- In early ‘80s, could finally fit 32-bit datapath + small caches

on a single chip

No chip crossings in common case allows faster operation

* RISC use more instructions, thus use more memory and storage. * CISC make instruction complicatred and take more CPU cycle to execute.

CISC架构的主要缺陷？它为何能在计算机发展历程上长期占有重要地位？

* When memory is expensive and CPU clock is slow, CISC rules. But now things changed.

编译技术对计算机体系结构有哪些方面的影响？

Schedules to maximize parallel execution 预计划增加执行并行度
Guarantees intra-instruction parallelism 保证指令并行
Schedules to avoid data hazards (no interlocks) 避免数据相关
- Typically separates operations with explicit NOPs 把操作和NOP隔离

何谓结构相关？一般有哪些解决方法？

An instruction in the pipeline may need a resource being used by another instruction in the pipeline

流水线内一个指令可能需要其他指令使用中的资源

Resolving Structural Hazards
- Structural hazards occurs when two instruction need same hardware resource at same time
  - Can resolve in hardware by stalling newer instruction till older instruction finished with resource

新指令等待旧指令

A structural hazard can always be avoided by adding more hardware to design
- E.g., if two instructions both need a port to memory at same time, could avoid hazard by adding second port to memory

增加硬件

Our 5-stage pipe has no structural hazards by design
- Thanks to MIPS ISA, which was designed for pipelining

更好的设计

何谓数据相关？一般有哪些解决方法？何谓控制相关？一般有哪些解决方法？

An instruction may depend on something produced by an earlier instruction

指令依赖之前指令的生成物

Dependence may be for a data value ⇒ data hazard

如果依赖的是数据，数据相关

Dependence may be for the next instruction’s address ⇒ control hazard (branches, exceptions)

依赖的是地址，控制相关

Resolving Data Hazards 解决数据相关
- Strategy 1:
  - Wait for the result to be available by freezing earlier pipeline stages ⇒ interlocks

等待结果，冻结先前指令的状态

Strategy 2:
- Route data as soon as possible after it is calculated to the earlier pipeline stage ⇒ bypass

尽早计算获取旁路，绕开

Strategy 3:
- Speculate on the dependence. Two cases:

对依赖进行推测, 正确的话什么都不做，错误的话终止，并重启

Guessed correctly ⇒ do nothing
Guessed incorrectly ⇒ kill and restart

Resolving control Hazards 解决控制相关
Branches/Jumps 分支和跳转
Exceptions/Interrupts 例外和中断

什么是指令的动态调度和静态调度？各自有什么优缺点？

TODO ??????
* 静态： 
  * Stall：直到分支方向确定
  * 预测分支失败：直接执行后继指令，如果分支实际情况为分支成功，则撤销流水线中的指令对流水线状态的更新.
    DLX分支指令平均47%为分支失败, 由于PC+4已经计算出来，因此可以用它来取下一条指令
  * 预测分支成功: 平均53% DLX 分支为分支成功，但分支目标地址在ID段才能计算出目标地址
  * 延迟转移：选择指令来填充延迟槽

动态
- 记分牌scoreboard:
  - 没有定向数据通路
  - 指令窗口较小，仅局限于基本块内的调度
  - 功能部件数较少，容易产生结构相关
  - 结构冲突时不能发射

Tomasulo Algorithm: 性能受限于Common Data Bus

3、预测分支成功：平均53% DLX 分支为分支成功，但分支目标地址在ID段才能计算出目标地址 4、延迟转移：选择指令来填充延迟槽

实现多指令流出，目前主要采用哪些技术？各自的技术特点是什么？

To make CPI < 1:
* Superscalar: 
  每个时钟周期发出的指令数目不定（1-8条）
  由编译器或者硬件完成调度
  IBM Power, SUN Ultra SPARC, DEC Alpha, HP 8000
* Very Long Instruction Words::
  每个时钟周期流出指令数目固定（4-16）
  编译器调度，有多个操作合并成一条指令
  DSP， 多媒体应用
  1999/2000 HP与Intel达成协议共同研究VLIW

多指令流出处理器的性能受到哪些方面的限制？

TODO ???????

什么是存储层次？哪些应用适合用单级存储结构？哪些应用适合使用多级存储结构？

  通过优化存储系统的组织来使得针对典型的应用平均访存时间最短
  基本解决方法：多级层次结构 CPU-M1-M2 ...... Mn
  存储系统速度接近速度最快M1，容量和价格接近最大最便宜的Mn。

引入cache的理论依据是什么？使用cache有什么优缺点？

CPU速度远远超过RAM读写速度 Processor-Memory Performance Gap “Tax”. Cache是CPU和主存之间的一个高速，小容量的存储器

Cache 减小CPU和RAM的Gap Cache 价格昂贵，容量小

Cache的二种写策略及其特点

Write-Through vs Write-Back
- Write-Through
  - 总是可以丢弃cache的数据－－内存里有最新数据
  - Cache control bit 只有一个valid bit
  - Memory或者Processor总有最新数据；Cache管理简单

Write-Back
- 不能直接丢弃cache数据－－可能需要写入内存
- Cache control bit 有valid bit和dirty bit
- 应为数据经常被重写，带宽占用低得多；对于高延迟的Memory有更好的容忍度

简述cache失效的3C分类

Compulsory 强制失效

Capacity 容量失效

Conflict 冲突失效

降低Cache的失效率主要有哪些方法？

Larger cache 更大的Cache
Reduce Misses via Larger Block Size 更大的Block Size
Reduce Misses via Higher Associativity 更大的相关性
Reducing Misses via Victim Cache 引入Victim Cache
Reducing Misses via Pseudo-Associativity 伪相关性
Reducing Misses by HW Prefetching Instr, Data 硬件预取指令和市局
Reducing Misses by SW Prefetching Data 软件预取数据
Reducing Misses by Compiler Optimizations 编译器优化

降低Cache的失效开销主要有哪些方法？

  
* Read priority over write on miss  读操作比写操作在失效上更优先
* Early Restart and Critical Word First on miss 及早重启及重要词先行
* Non-blocking Caches (Hit under Miss, Miss under Miss) 不阻塞的Cache,
* Second Level Cache 二级Cache

降低Cache的命中时间主要有哪些方法？

* Small & Simple Caches 小而简单的Cache
* Avoiding Address Translation 避免地址翻译
* Pipelining Caches 管道化Cache

对于一定容量的Cache，当块大小有小变大时，失效率为什么先下降，后又上升？对于16KB的Cache，合适的块大小一般是多少？

因为随着Cache块大小的增大，强制失效会减少，而冲突失效会增加16KB的Cache, 合适的块大小一般是64byte

简述Victim Cache的原理？

How to combine fast hit time of direct mapped yet still avoid conflict misses?

Add buffer to place data discarded from cache

安排buffer存放Cache丢弃的数据

Jouppi [1990]: 4-entry victim cache removed 20% to 95% of conflicts for a 4 KB direct mapped data cache
Used in Alpha, HP machines

对于磁盘存储介质，衡量记录密度的指标是什么？它又取决于哪二个参数指标？

Areal Density = BPI x TPI 区域密度 = 单位英寸的Bits X 单位英寸的道数

Metric is Bits Per Square Inch

BPI * TPI

BPI: Bits Per Inch, Bits recorded along a track
TPI: Tracks Per Inch, Number of tracks per surface

什么是RAID？简述RAID3、RAID5的主要技术特征。

RAID: Redundant Arrays of (Inexpensive) Disks

RAID3: Parity Disk. 校验位
Parity computed horizontally
Logically a single high data bw disk

P contains sum of other disks per stripe mod 2 (“parity”)
If disk fails, subtract P from sum of other disks to find missing information
Sum computed across recovery group to protect against hard disk failures, stored in P disk
Logically, a single high capacity, high transfer rate disk: good for large transfers
Wider arrays reduce capacity costs, but decreases availability
33% capacity cost for parity in this configuration

RAID5: High I/O Rate Interleaved Parity 交错校验

A RAID 5 uses block-level striping with parity data distributed across ALL member disks

  Small write Algorithm: 1 Logical Write = 2 Physical Reads + 2 Physical Writes
  * Interleaved parity blocks
  * Independent reads and writes
  * Logical write = 2 reads + 2 writes

简述向量机的部件组成，向量处理器的特点？对以下于运算, 试写出其对应的标量指令序列和向量指令序列。

For (I=0; I<100; I++) Q[I]=A[I]*B[I]+D[I]*(E[I]-5)

Properties of Vector Processors:

Single vector instruction implies lots of work (loop)
- Fewer instruction fetches
Each result independent of previous result
- Multiple operations can be executed in parallel
- Simpler design, high clock rate
- Compiler (programmer) ensures no dependencies
Reduces branches and branch problems in pipelines
Vector instructions access memory with known pattern
- Effective prefetching
- Amortize memory latency of over large number of elements
- Can exploit a high bandwidth memory system
- No (data) caches required!

Components of a Vector Processor:

Scalar CPU: registers, datapaths, instruction fetch logic
Vector register
- Fixed length memory bank holding a single vector
- Typically 8-32 vector registers, each holding 1 to 8 Kbits
- Has at least 2 read and 1 write ports
- MM: Can be viewed as array of 64b, 32b, 16b, or 8b elements
Vector functional units (FUs)
- Fully pipelined, start new operation every clock
- Typically 2 to 8 FUs: integer and FP
- Multiple datapaths (pipelines) used for each unit to process multiple elements per cycle
Vector load-store units (LSUs)
- Fully pipelined unit to load or store a vector
- Multiple elements fetched/stored per cycle
- May have multiple LSUs
Cross-bar to connect FUs , LSUs, registers

对以下于运算, 试写出其对应的标量指令序列和向量指令序列

For (I=0; I<100; I++) Q[I]=A[I]*B[I]+D[I]*(E[I]-5)

Scalar:

        LD      R0, 5
        ADDI    R1, Ri, #800

loop: 	ld	R5, 0(Re)
        subd    R5, R5, R0
        ld      R6, 0(Rd)
        multid  R6, R5, R6
        ld      R7, 0(Ra)
        ld      R8, 0(Rb)
        multid  R7, R7, R8
        addd    R6, R6, R7
        ld      0(Rq), R6
        addi    Rq, Rq, #8
        addi    Ri, Ra, #8
        addi    Ri, Rb, #8
        addi    Ri, Rd, #8
        addi    Ri, Re, #8
        sub     R99, R1, Ri
        bnz     R99, loop

Vector:

ld    r0, 5
vld   V1, Ra
vld   V2, Rb
vld   V3, Rd
vld   V4, Re

vsub.sv  V5, V4, R0 
vmul.vv  V6, V5, V3
vmul.vv  V7,  V1, V2
vadd.vv  V8, V6, V7
vst      Rq, V8

什么是SIMD？简述MIMD并行机的二种组成结构。

SISD: Single Instruction, Single Data
- conventional uniprocessor
SIMD: Single Instruction, Multiple Data
- one instruction stream, multiple data paths
- distributed memory SIMD (MPP, DAP, CM-1&2, Maspar)
- shared memory SIMD (STARAN, vector computers)
MIMD: Multiple Instruction, Multiple Data
- message passing machines (Transputers, nCube, CM-5)
- non-cache-coherent shared memory machines (BBN Butterfly, T3D)
- cache-coherent shared memory machines (Sequent, Sun Starfire, SGI Origin)

简述MIMD并行机的二种组成结构:

分布存储器并行处理机
共享存储器并行处理机

Symmetric Multiprocessor
- Multiple processors in box with shared memory communication
- Current MultiCore chips like this
- Every processor runs copy of OS
Non-uniform shared-memory with separate I/O through host
- Multiple processors
  - Each with local memory
  - general scalable network
- Extremely light “OS” on node provides simple services
  - Scheduling/synchronization
- Network-accessible host for I/O
Cluster
- Many independent machine connected with general network
- Communication through messages

PCI、USB、FireWire、MMU、MPU、MIPS、CPI、IPL？

PCI: 外围组建互联，一种用来连接计算机和硬件设备的计算机总线

Peripheral Component Interconnect, a computer bus for attaching hardware devices in a computer.

USB: 连接计算机系统与外部设备的一个串口总线标准，也是一种输入输出接口技术规范
FireWire：The IEEE 1394 interface is a serial bus interface standard for high-speed communications and isochronous real-time data transfer

IEEE 1394，別名火线（FireWire）接口，是由苹果公司领导的开发联盟开发的一种高速传送接口，IEEE 1394是由蘋果電腦所創，其他製造商也已獲得授權生產

MMU: 内存管理单元（英语：memory management unit，缩写为MMU），有时称作分页内存管理单元（英语：paged memory management unit，缩写为PMMU）。它是一种负责处理中央处理器（CPU）的内存访问请求的计算机硬件
MPU: 电子计算机的主要设备之一。其功能主要是解释计算机指令以及处理计算机软件中的数据。
MIPS: Million Instructions per second (IPS)单字长定点指令平均执行速度, 是一種計算電腦中央處理器速度的記量單位. 是一種採取精簡指令集（RISC）的處理器架構，1981年出現，由MIPS科技公司開發並授權
CPI: 一条指令运行需要的时钟周期

In computer architecture, cycles per instruction (aka clock cycles per instruction, clocks per instruction, or CPI) is a term used to describe one aspect of a processor's performance: the number of clock cycles that happen when an instruction is being executed

IPL: 中断优先级, 是当前系统的中断状态的一部分，表示了当前将会被接受的中断请求

The interrupt priority level (IPL) is a part of the current system interrupt state, which indicates the interrupt requests that will currently be accepted.

ILP :Instruction-Level-Parallelism 指令层并行. 计算机的并行级是在指令层并行,也就是说计算机在同一时间可以执行两条以上的指令.

针对计算机体系结构的软件优化技术一般应考虑哪些方面？

编译器优化:

Loop Unrolling 循环展开
Static Branch Prediction 静态分支预测
Detecting and Enhancing Loop Level Parallelism 检测和加强循环层次并行度
代码转换，消除依赖性
软件流水线
内存结构优化, Cache优化
- 减少Cache Miss: 数组合并；循环顺序调整；循环融合；数据分块

软件应该贴合计算机体系结构，要贴合局部性原理。要根据软件所运行的硬件和系统平台来进行优化，比如大型机和PC机的区别，超线程CPU和双核CPU的区别、WINDOWS和UNIX的区别。软件的优化包括了对软件体系结构、数据结构、算法、代码等几个方面的优化，这几个方面都

gct

wiki:gct_tcpip - created

MeaCulpa — Thu, 01 Dec 2011 23:42:59 -0600

TCP/IP

Summary

Chapter 1

历史

Chapter 2

网络回顾

Chapter 3

体系结构

Chapter 4

ipv4地址

Classful 分类地址 32位 netid + hostid

A B C D E

Chapter 5

ARP协议为什么是影响互联网安全的因素之一? ARP控制了IP地址到物理地址的转换，关系到通信端点的身份问题，所以是影响互联网安全的关键因素之一。

习题

3. 管理ARP高速缓存的一种常用算法在添加新表项时替换了最近使用过的表项。在什么情况下这个算法会产生不必要的网络通信量？

答：当一个接收方机器Crash或者硬件故障，被替换，造成无法连接或者物理地址变化时，发送方可能会发送不必要的请求，等待很久的超时后才能察觉到这一变化

4. 对于一个给定的IP地址，如果Cache中已经存在相应的旧表项，ARP是否会更新Cache, 为什么？

答：不会，ARP如果在Cache中找到Binding信息，就不会发送ARP广播，而会向目标地址发送数据帧。只有当达到Cache

  Timeout时，表项信息才会清除，那时候ARP在Cache中查找不到Binding信息，就会发送广播，获取新的Binding信息，并更新Cache。
  典型的Timeout是20min
* 5. ARP软件是否需要修改高速缓存，即使接收的信息并没有专门作出请求，也需要如此吗？为什么 
  答：需要，减少广播数量，并且当其他应用程序需要进行ARP请求时，可以参考并更新缓存内的信息。提高效率，大大减少ARP广播
* 7. ARP被作为安全性弱点
  答:
  ARP控制了IP地址到物理地址的转换，关系到通信端点的身份问题，所以是影响互联网安全的关键因素之一。通过伪造的ARP
  Reply, host上的ARP信息很容易被伪造
* 9. 假设机器C收到一个来自A的寻找目标B的请求，且C的Cache中有Ib到Pb的绑定，C是否应该回答这个请求，为什么？
  答：不会，只有发送方才会检索自己的ARP Cache, C不会转发ARP, 所以也不会检查自己的Cache
* 11. 请解释，怎样向以太网上一个不存在的地址发送IP分组，才能在该网络上产生过量的广播通信量
  答：因为无法匹配到，所以会不停的发送哦你请求，要广播通信量过大，主机必须不丢弃发送的分组？？

Chapter 6

RARP: Reverse Address Resolution Protocol

习题

Chapter 7

Ethernet Frame中的 IP 数据报格式

Frame Header + Frame Data Area

Header: Dest, source, type(0x0800)
Data Area: IP Packet Header, IP Packet Data

IP Datagram 格式: ch-07.ppt, Slide7

MAX Datagram 64K octets in IPV4

IP协议的基本原理

The protocol that defines the unreliable, connectionless deliver mechanism is called the Internet Protocol (IP).

IP是在TCP/IP协议中网络层的主要协议，任务是仅仅根据源主机和目的主机的地址传送数据。为此目的，IP定义了寻址方法和数据报的封装结构。

不可靠，尽力而为，无连接
包格式，路由，错误处理

习题

2. 在以太网上发送分组，总有必要使用IP校验和么？

答：没有必要，只有首部有必要使用校验和，数据应用的校验应该和首部分开

9. 在最终目的站而不是在数据报穿过一个网络后重组，好处是什么？

答：好处是，每个分片作为数据报可以独立的路由；中间路由器不需要重组数据报; 坏处是，小分片在大MTU网络上传输效率不高；一旦某个分组丢失，整个数据报都不得不被丢弃

10: 要发送一个至少一个8位组的数据报，所需的最小MTU要多少？

答：数据报首部最小20个八位组(不包括可选项和Padding),

  在IP协议层次的MTU最小要20 + 1 = 21
  在链路层，以太网帧格式还要另加26个八位组所以最小MTU是FrameHeader + DataGram Header + Data + Frame CRC = 
  22 +(20 + 1) + 4 = 47 octects

Chapter 8

选路: 选择一条用于发送分组的路径的过程
路由器：作出选路决定的设备
缺省路由：IP选路软件首先在选路表中查找目的网络，如果表中没有路由，就把数据报发给默认路由器

当网点本地地址集很小，并且只有一个互联网的链接时，默认选路尤其有用。

  整个选路决策由两个测试组成：一个用于本地网络，一个是对唯一可用路由器的默认。
* IP 选路算法:
<code>

从数据报中提取目的IP地址D, 并计算网络前缀N: if N 与任何直接相连的网络匹配：

  then 通过该网络交付数据到D

else if 路由表中包含到具体主机D的路由:

  then 把数据报发送到表中指定的下一跳

else if 路由表中包含到网络N的路由:

  then 把数据报发送到表中制定的下一跳

else if 表中包含一个默认路由:

  then 把数据报发送到表中指定的默认路由

else 宣布选路出错

</code>

图8.2 路由器路由表结构, ch-08.ppt, Slide10

习题

8.1, 把8.2中所有路由器都加入选路表中，哪个路由器使用默认路由获益最多?

  10.0.0.0    deliver directly
  20.0.0.0    deliver directly
  30.0.0.0    20.0.0.6
  40.0.0.0    20.0.0.6

  S:
  10.0.0.0    30.0.0.6
  20.0.0.0    30.0.0.6
  30.0.0.0    deliver directly
  40.0.0.0    deliver directly

  R 获益最多，都只需要一个hop.

8.3, 路由器如何对待IP首部的寿命TTL值？

路由器接收到IP DataGram以后,

  判断DataGram中目标地址与自身相连的网络是否匹配，匹配的话则进行地址绑定并向目标地址发送数据报。
  如果没有匹配，则会对TTL减一，如果计数器为0则丢弃这个数据报，大于0则重新计算checksum,并继续转发数据报。

8.5, 考虑两个主机A,B, 他们都连接到同一个物理网N，是否有这种可能，当我们使用选路算法时候，A收到一个目的地为B的数据报？解释原因。

答：有可能，比如当我们使用IP选路时，路由表内的下一跳可以包含具体的主机地址，甚至默认路由也可以是一个主机地址。

  这样主机A也可以来参与选路。当然，如果我们在选路表中只存放网络信息而不是完整的主机信息，这样的机制效率可以更高，隔离性也更好。

8.6, 修改选路算法, 使他适用于第7章所描述的IP源路由选项

简单的说，就是在IP源路由列表还未用尽时，以列表内信息为转发依据。否则则以正常的选路算法转发。

<code>

从数据报中提取目的IP地址D, 计算网络前缀N, 取出IP路由选项信息中的路由IP列表L和列表指针Lp:

if Lp 所指值大于列表长度，即地址列表还未用尽：

  then 根据Lp取出IP地址，用路由器地址代替
       使用表中得到的地址转发数据报

else if N 与任何直接相连的网络匹配：

  then 通过该网络交付数据到D

else if 路由表中包含到具体主机D的路由:

  then 把数据报发送到表中指定的下一跳

else if 路由表中包含到网络N的路由:

  then 把数据报发送到表中制定的下一跳

else if 表中包含一个默认路由:

  then 把数据报发送到表中指定的默认路由

else 宣布选路出错

</code>

* 8.7，每当IP路由器处理一个数据报时，他必须完成一次计算，计算所需时间与该数据报首部长度成正比。请解释原因。
  答：首先，数据报首部的可变长度部分，是Datagram
  Options。在IP报文中，这些Options是连续存在的。
  也就是说，Options的长度与其代表的操作成正比。

  这些可选操作往往需要路由器进行某些运算。比如：
  Record Route, Source Route, Timestamp
  所以路由器完成一个数据报中这些运算的开销，
  与Option数目成正比，也就和数据报首部的长度成正比。

Chapter 9

ICMP 允许路由器向其他路由器或主机发送差错或控制报文； ICMP 在两台机器上的网际协议软件之间提供了通信

ICMP 作为IP的补充: DoS攻击的原理

Internet Control Message Protocol 网际控制报文协议

DoS攻击：拒绝服务攻击（denial of service（DoS）attack）是指黑客计算机向网络服务器或web服务器发送大量请求，使得服务器来不及响应从而无法正常工作

ICMP Flood: 面向广播地址的ICMP, 伪装成和目标地址一样的源地址…

习题

9.5, ???? 假设所有的路由器都发送ICMP超时报文,且你的TCP/IP软件把这些报文返回给一个应用程序。使用这个工具建立一个跟踪路由(traceroute)命令，让他报告源站和一个特定目的站的所有路由器的清单 ????
9.8, ???? 考虑以太网上有一台传统主机H，还有12个路由器与他相连, 找到一个携带IP分组的单帧,使得当主机H发送他时，会引起H接受到24个分组 ????

Chapter 10

子网划分，

习题

10.17, ????仔细考虑子网中的默认选路技术，假如到达的分组应该发往一个不存在的子网，将会发生什么情况???? {Subnet Mask, Network Address, NextHop Address}

Chapter 11

分曾

Chapter 12

UDP

Chapter 13

滑动窗口:

  允许发送方在收到ACK之前发送多个包;
  简单窗口 协议一个固定大小的向后滑动的窗口在序列中，凡是窗口内的包可以发送.
  窗口大小就是发送的最大包数量, 
  收到ACK以后，窗口向前滑动
  发送方为每个未获确认的包维护了计时器
  计时器超时，且未获的ACK时，包被重发
  TCP滑动窗口协议，窗口大小可变，流量控制

主动和被动打开

  
  TCP面向连接, 为了确保可交付服务
  被动打开进行传输时应用程序必须通知OS需要建立一个传入的链接
  另一端，应用程序必须通知OS需要建立一个链接

拥塞窗口

  拥塞窗口界限，又称拥塞窗口，用于在发生拥塞的时候把数据流量限制为小于接收方的缓冲区大小。也就是说，在任何时候，TCP按下面的公式计算窗口值
  Allowed_window = min(receiver_advertisment, congestion_window)

解决拥塞问题

卡恩算法

  TCP不应更改重传报文段的往返时间估计值，Karn算法避免了确认二义性带来的问题，
  只对没有二义性的确认(即指发送一次)的往返时间估计值进行调整
  
  Karn算法:
  计算往返时间估计值时，忽略对应于重传报文段的样本，但是要使用补偿策略，对一个重传分组的许多后续分组，其定时时限均不变，直到获得一个新的有效样本时在更改时限值
  常数因子补偿：
  <m> new_timeout = gamma * timeout </m>

慢启动

  慢启动（加法）回复：在启动新连接的传输或在拥塞之后增加通信量时，仅以一个报文段作为拥塞窗口的初始值，而每当收到一个确认之后，将拥塞窗口大小增加1。

尾丢弃

  路由器的尾部丢弃tail-drop策略:
  如果数据报到达时输入队列已被填满，则丢弃该数据报

随机早期丢弃

糊涂窗口综合征 Silly Window Syndrome: TCP的早期实现暴露出了糊涂窗口综合征的问题, 即每个确认报文通告了少量的可用空间（接收缓冲区），而每个报文段仅仅携带少量的数据。

TCP的有限状态机：状态转换的原因和依据

状态机 13.15, 各端均从关闭状态开始，每个转换标出了导致该转换的输入以及该转换的输出主动打开，被动打开，关闭，sync, ack,

习题

13.13
跟踪TCP有限状态机转换，请分析描述两个网点的主机分别使用主动与被动打开方式和三次握手的过程

Three-way handshake:

Site 1 sends SYN segment seq = x Site 2 receives SYN segmentSend SYN seq = yACK x+1 Receive SYN + ACK segmentSend ACK y+1 Receive ACK segment

* 13.14 阅读TCP/IP规范，说明在什么情况下TCP会从FIN WAIT-1状态转换到TIMED WAIT状态
  上一个报文的超时等待？？？:
  收到 => fin-ack/ack =>
      => fin/ack => ack =>
      => ack/ => fin/ack =>

13.16 假设TCP在一个带宽无限的通道上使用窗口最大值（64K字节）进行传输，其平均往返时延为20毫秒、求最大吞吐率。如果平均往返时延变为40秒，最大吞吐率？

每20毫秒可以发送一个窗口大小的数据, 所以每秒(1/0.02) 也就是 50个窗口.

  
  awk "BEGIN{ print 64*1000*8/0.04/1000/1000 }"  = 12.8 Mb/s

  awk "BEGIN{ print 64*1000*8/0.02/1000/1000 }"  = 25.6 Mb/s

13.17 如前题所示，大窗口能获得高吞吐率，TCP报文段格式的一个缺点是用于窗口通告字段的大小。怎样扩展TCP才能允许更大的窗口，同时不改变报文段格式？

窗口字段中原先是16比特无符号整数，扩大他？？

Chapter 14

路由的两种最基本算法特别是距离向量算法中路由更新的三种情况

距离向量选路（矢量距离选路）

(V, D): 目的站，距离

目的站	距离	路由
网络1	0	直接
网络2	8	路由器L

路由更新的三种情况，收到其他路由器发来的路由表

其他路由器知道去每个目的站的更短路由
列出了不知道的目的站
到目的站经过某路由而某路由到该站距离有所改变

缺点：来不及更新, 报文随网络规模增大而增大

链路状态(SPF)选路

即最短路径优先, Shortest Path First

所有路由器都有图, 独立的用相同初始状态选路
链路状态报文在传输中不会改动，调试方便
路由器在当地计算，保证收敛性
链路状态保温仅携带相邻的链接信息，报文长短独立，性能更好适合大网络

Chapter 15

了解互联网中BGP IGP 使用场合以及它们之间的配合关系

外部网关协议之一，边界网关协议BGP

当一对自治系统同意交换选录协议时，每个系统必须制定一个路由器（对等路由器，Peer），这个路由器将使用BGP协议。

边界网关，边界路由器由于采用可靠传输，所以使用TCP

Chapter 16

IGP 内部网关协议

两个自治系统在内部各自使用自己的IGP，但使用BGP在外部路由器与另一个系统进行通信

最广泛的一种IGP:

RIP 选录信息协议 routed. RIP使用跳数
HELLO 使用时延(现在几乎不用) 震荡问题

自治系统间选路:

gated
* OSPF

Chapter 17

Internet 组播与广播不同，组播允许每个系统选择是否参与组播

IP 组播的基本原理 RPF和TRPF

RPF 反向路径转发

一种广播形式，使用数据报的源地址来避免数据报反复通过一个环路

TRPF 截尾反向路径转发

遵循RPF算法，但是，通过避免不通向群组成员的路径，进一步对传播进行限制

  组播路由器需要有两种信息：常规选路表和通过每个网络接口可达的组播群组列表
  总之：
      当进行转播决策时，组播路由器使用了数据报的源地址和目的地址。基本转发机制称为截尾反向路径转发
  
  TRTF的后果：
      像RPF那样，主机会收到数据报的多个副本
      交付取决于数据报的源地址

Chapter 18

ATM 异步交换模式

怎样实现ATM和IP的技术结合，从而提高数据报文的转发效率答：使用IP交换技术，等等思路。由IETF统一，称为多协议标记交换（MPLS）

  具体包括优化的IP转发，分类，数据流，高层交换
  IP交换可作为路由器，也可将IP数据分类，并尽可能通过交换网络发送他们，
  第三层分类只使用数据报首部，第四层分类还检查TCP或者UDP首部

Chapter 19

移动IP

允许计算机从一个位置移动到另一个位置, 而不用更改其ip地址，也不需要给所有路由器传播一个特定于主机的路由。当移动计算机从原来的家网移动到外网时，它获得一个临时地址，称为转交地址。应用程序使用移动主机原来的家地址，转交地址仅由下一层网络软件使用, 通过外网进行转发和交付

移动登记，代理转发，发送的数据报将直接发给制定地址，但发回主机的数据报会沿路由到达家网络，由家代理截取，封装在IP中，利用隧道传输给主机

移动ip的基本原理和使用场合特性：透明性，与IPv4的可互操作性，安全性，宏移动性移动寻址，发现外代理，代理登记，与代理通信，数据报收发路由效率低，双交叉

Chapter 19

NAT 和 VPN

NAT的实现原理和适用场合网络地址转换NAT: 提供了从使用专用地址的主机到Internet的透明IP层访问

网点上主机和Internet进行IP层访问，NAT盒有一个有效IP, 进行地址转换，

多地址NAT, 端口映射NAT, 网络地址端口转换，NAPT.. 几种NAT变种

Chapter 23

bootp和dhcp, 自举与自动配置

bootp使用udp, 封装在ip内. 所以比rarp更通用 bootp使用两步自举：为客户提供获取内存映像所需的信息，然后客户使用第二个协议如tftp获取内存映像

动态主机配置：DHCP: 允许三类配置：

  手工
  自动
  临时租用

动态地址分配, 三个定时器，更新租用，重新绑定，停止使用

新的计算机和通信技术
新的应用
规模和负载的增长

特点：

更大地址
扩展的地址层次
灵活的首部
增强的选项
协议扩展的保障
自动配置和重新编号
支持资源分配

基本首部 + Nx扩展首部 + 数据

地址类型:

单播任意播组播

Book

Dr. Douglas E. Comer

Internetworking with TCP/IP, VolI

Quiz

Quiz I:

tcpip arp 3 4 5 7 9 11

Quiz II:

2, 9, 10

8: 8.1 8.3 8.5 8.6 8.7

ICMP: 5, 8

 B 类地址 2^8 - 2^16  10,2^14,2^16

 10 XXXXXXX XXXXXXX XXXXXXXX XXXXXXXX

10.17

13.

13 14 16 17

gct