System Analysis and Design (Kenneth Kendall) Review Part3

6. 设计有效的输出

6.1.输出设计目标

1.设计满足特定用途或组织目标的输出
输出要面向用户,考虑用户的年龄、收入和文化层次。

2.制作对用户有意义的输出
设计要满足特定用户的需求,决定什么是内容,什么是途径。
考虑输出的时间和地点 [more…]

3.交付合适数量的输出
决定要给用户多少信息,根据对用户的调查来决定,根据对象的重要性,数量和个数来决定
如:搜索后的结果

4.合理分配输出,确保重要信息是必不可少的
如商店的门户网站,分类信息要展示
对必不可少的信息进行版本化,如计算器的科学性和普通型

5.按时提供输出
In-Time 按时,及时的展现,考虑输出的时效性
如每年南大的主页在高考时很重要
如滴滴打车,采用语音输出

6.选择最有效的输出方式:报表,屏幕输出,音频或视频输出。

6.2.选择输出技术时需要考虑

1)谁将使用,看到输出。
2)多少人需要输出
3)哪里需要输出,如配送部门和后勤部门
4)输出的目的
5)输出的速度是多少
6)访问输出的频率如何
7)输出将必须存储多长时间
8)产生、存储和分发输出必须遵循的特殊规则是什么
9)维护和供应的最初与后续的成本是什么
10)输出技术的环境需求是什么:易接近性、噪声吸收、温度控制、设备空间、电缆架设以及WiFi发射机的接近程度。 例如:打印输出噪声很大。

6.3.常见的输出技术


补充如下:
1. 打印机输出:如报表行程单、化验单、信用卡账单、财务单,具有持久性,需要考虑浪费纸张的成本,噪声,采用合适的表格形式
2. 视频输出:
补充静态的打印输出。
远程协作,将那些不能经常见面的人联系在一起
教学,帮助,培训视频
记录当前事件,方便以后的输出
保存一个重要情节,收藏,存档

3. 动画输出:增强web站点的演示效果;比抽象的图像带来更好地决策支持。
4.电子邮件输出:可以用于私密信息。
5. 输出技术两种分类:
推技术:向用户推送信息,如推送流量统计,可以采用短信或电子邮件的方式。
拉技术:用户主动发起请求数据,如web上点击链接

6.4.避免输出的偏差

1.偏差的来源
a)信息排序的方式
b)可接受的边界值引入的偏差
c)使用图形引入的偏差

2.如何避免偏差
a)明确偏差来源
b)在测试Web文档的外观过程中,设计交互式输出,让各种用户参与测试,并使用各种不同的系统配置测试输出。
c)让用户参与输出设计,使它们认识到输出信息中可能存在的偏差
d)创建灵活的输出,使得用户能修改边界值和范围。
e)训练用户依靠多种输出对系统输出执行“逼真测试”

6.5.印制报表的设计原则

1.确定报表设计约定
设计表单时要遵循的约定包括:每个位置上出现的数据类型,表单大小,以及表明连续表上数据延续部分的方式。
2.纸张质量、类型和大小
3.功能、风格和美观程度
4.报表的功能属性:标题、页码、准备日期、列标题、相关数据项的集合、控制分割行的使用

6.6.设计屏幕输出

1.原则
a)保持屏幕简单
b)保持屏幕显示的一致性
c)方便用户在屏幕间移动
d)创建吸引人的屏幕

2.在屏幕输出时使用图形要考虑
a)图形的用途
b)需要显示什么样的数据
c)读者对象
d)不同图形输出对读者的影响

3.选择仪表盘输出时考虑:
a)确保数据有上下文
b)显示合理的汇总的精度
c)选择合适的工作指标进行显示
d)公正地表现数据
e)选择正确的图表样式进行显示
f)使用精心设计的显示媒体:大小、图片、颜色、标签
g)限制项目类型的多样性
h)突出显示重要数据
i)将数据按有意义的小组进行编排
j)保持屏幕简洁
k)使整个仪表板保持在一个单独的屏幕上

4.Wedget和Gadeget输出
a)窗口小部件,可以个性化桌面
b)证券报价机、天气预报、RSS反馈可以采用widget
c)但widget会分散用户对系统支持的任务的注意力。

7.设计有效的输入

7.1.对输入的质量要求

1.输入的质量
1)有效性:输入表单、输入屏幕和Web上的输入窗体在信息系统中服务于具体的目的。
2)准确性:所作出的设计能保证用户准确输入数据。
3)易用性:表单和屏幕简单易懂
4)一致性:所有输入窗体,在不同的程序中按类似的方式组织数据。
5)简单性:设计简洁,让用户集中注意力输入数据。
6)有吸引力:精心设计表单,让用户喜欢

2.输入还需要保证
完整性
输入顺序要合理:从主体到客体,重要到次要
如简历:先基本信息,再个人获奖,个人工作经历

7.2.良好的表单设计(纸质表单)

1.设计原则
a)使表单容易填写
b)满足用户的需求
c)保证输入的完整性,准确性
d)有吸引力

2.使表单容易填写
a)表单流:从左到右,从上到下
b)表单的7个部分
i.标题
ii.标识和访问控制
iii.用法说明
iv.主体
v.签名和确认
vi.总结
vii.评论

c)加标题:行标题,行下标题,加框标题,垂直选择标记,水平选择标记。
标题要有相关注释。
标题风格保持一致。

3.满足用户的需求
创建表单目的:记录、处理、保存和获取商业所需信息。

4.确保完整性和输入的准确性
这样可以让与收集数据相关的错误率大幅度降低。

5.表单设计要有吸引力
按预期顺序组织信息:姓名、街道地址、城市、州(省)、邮政编码
吸引力来自于正确的表单布局和流向。
字体样式和线条粗细也是有用的设计元素。

6.表单设计软件:如scansoft

7.业务表单控制:
a)确保表单的输入是为了达到特定的需求,并且该需求是组织功能不可分割的。
b)避免重复信息,避免使用重复表单。
c)设计高效的表单。
d)以尽可能低的成本制作表单

7.3 良好的Web屏幕和Web窗体设计

7.3.1.屏幕设计原则

1.电子、web表单与静态表单的区别:
有光标,指示当前的数据输入位置
可以在上下文加入相关帮助

2.设计原则
a)保持简洁
b)一致性
c)易于用户在屏幕间移动
d)创建有吸引力和满意的屏幕

3.保持屏幕的简洁
屏幕输出的三个部分:
•标题:文件名称、下拉菜单和执行某些任务的图标
•主体:输入数据,从左到右,从上到下
•评论和用法说明
另一种保持简洁的方法是:使用上下文相关帮助和其他弹出窗口,利用超链接

4.保持屏幕一致性:
a)与相关的纸质表单保持一致性
b)每次访问新屏幕时信息出现在同一个区域
c)逻辑上不可分割的信息始终组织在一起

5.易于用户在屏幕间移动
a)易于用户从在不用web页之间移动
b)“三次单击”规则:用户应能在三次单击鼠标或按键之内,转到他们所需的屏幕。
c)使用向下箭头滚动屏幕
d)上下文相关的弹出窗口
e)屏幕对话

6.设计有吸引力的屏幕
a)足够的留白,让用户集中注意力到数据上
b)使用逻辑流计划屏幕信息,按用户处理问题的方式组织屏幕信息,让他们容易找到所需信息
c)将信息划分为3个部分,参见简洁性,划分遵循一致性原则
d)采用粗细不同的线条划分不同的类目
e)反转影像,闪烁光标,但要慎用。
f)使用不同的字体

7.屏幕设计中使用图标
a)每个应用程序使用的图标控制在20个之内
b)相关图标要一起出现,保持连续性和易懂性
c)图标含义越丰富,越有用。

7.3.2.GUI元素的设计

1.文本框:大小要能容纳所有的字符。要有标题。
2.复选框:标签放在复选框的右边;如果超过10个,要将他们组成一个组,并框起来。
3.单选按钮:选项文本放在右边;如果选项按钮超过6个,考虑下拉菜单。
4.下拉菜单和列表框
5.滑动块按钮和旋转按钮
6.图像映射
7.文本区
8.消息框
9.命令按钮

10.表单控件和数值:GUI界面包括的每个控件必须有某种方法来存储与控件相关的数据。 Web页面上,可以采用名称和值对来实现。 每个Web表单控件获取数值的方法是不同的。
11.隐藏字段:表单中,对用户不可见,但需发送到服务器的数值
12.事件响应图:当GUI交互很复杂时,可以采用事件响应图列出各种可能发生的事件,概要的建立商业事件和响应的模型。
13.动态web网页:根据用户操作改变网页内容,基于JavaScript,可以用来显示临时的信息。但对需要加密,提供安全保护的数据,不要采用动态web的形式。而缺点是用户禁用JavaScript后,网页不可用。
14.Ajax,异步更新,web运行更快,更流畅。缺点是JavaScript必须启用,安全性问题。

15.选项卡控件对话框设计原则:
a)为每个独特的特性创建一个分离的选项卡
b)将最常用的选项卡放在前面,并首先显示
c)可以考虑在设计的选项卡控件对话框中包含三个基本按钮:OK,Cancel,Help

16.Web中使用色彩
a)色彩搭配要协调:对比前景和背景,突出表单上重要字段,显示错误。

b)容易辨认的搭配:前景明亮,背景用不太明亮的。
i.黑底文字在黄色背景上
ii.绿色文字在白色背景上
iii.蓝色文字在白色背景上
iv.白色的文字在蓝色的背景上
v.黄色的文字在黑色的背景上

c)色彩不宜超过4种,对于有经验的用户,不要超过7种。

7.4.内联网和互联网页设计

指导原则
1)提供清楚的用法说明
2)演示窗体的逻辑填写顺序,特别是因为用户滚动而看不到的部分
3)为特殊功能增加窗体的吸引力,使用各种文本框,按钮,下拉菜单、复选框和单选按钮
4)如果我们不能确定用户响应某个问题时将在字段中输入多少个字符,或者不能确定用户使用什么语言、结构或窗体输入数据,提供一个可滚动的文本框
5)为每个Web输入窗体准备两个基本按钮:Submit 和 Clear Form
6)如果窗体很长,且用户进行滚动之外别无它法,那么最好将窗体分成几个简单地窗体,放在不同的网页上
7)创建一个错误反馈屏幕
对于电子商务应用程序还需要达到目标:阐明有关信任、隐私和退货方面公司的任务和价值;建立高效的事务处理过程;建立良好的客户关系。

8. HCI人机交互

8.1.基本概念

1.HCI是指确保系统的功能和可用性,提供有效的用户交互与支持,以及增强用户快乐体验。总体目标是实现组织和个人用户的效率和有效性。
2.主要策略:不断引出用户对原型设计(屏幕、表单、界面等)的使用经验反馈,根据修改建议提炼设计,然后再让用户试用,直到用户满意,最后由分析员固定下来。面谈就是一种获得HCI反馈的重要方式。
3.技术接受模型:感知有用性和感知易用性
4.可用性:包括产品使用的有效性、效率和在特定环境下使用的满意度、用户界面交互,开发产品的过程,组织应用以用户为中心的设计的能力
5.HCI设计中考虑用户的身体因素:视觉,听觉,触觉,考虑人的缺陷、残障和意图。

6.良好的HCI进行系统设计的指导原则
1)界面与任务相匹配
2)提高界面效率
3)提供适当的反馈
4)生成有用的查询
5)提高工作者的效率

7.评价UI的原则
1)较短的学习时间
2)用户不用多加考虑或者不用查阅手册和帮助菜单,就可以输入指令
3)界面应该与实际功能“无缝”连接,确保出出错概率小
4)用户和系统出错后恢复时间尽可能短
5)偶尔使用的用户重新学习系统时要尽可能快
6)界面提供信息准确,界面友好

8.2.对话设计的指导原则

1.交流要让用户和计算机都能理解,意义明确

2.最小化用户的行为,减少不必要的操作,可以采用以下方式:
1)输入时用代码代替词组
2)只输入系统中没有存储的数据
3)提供缺省信息
4)提供help信息,不要让用户乱操作
5)提供符合常规的快捷键

3.操作的规范化和一致性
1)界面的标题、日期、时间、操作提示和反馈信息固定在相同位置
2)使用相同的键位或者菜单退出程序
3)采用一致的方法取消事务
4)用标准化的方法获得帮助,如F1
5)屏幕采用标准化的色彩
6)GUI中使用标准化的图标
7)网站中术语要一致
8)提供一致的方法实现对话导航
9)文字大小、颜色和对齐方式保持一致

8.3.用户界面类型

1.自然语言界面:实现复杂,如ask.com自然语言查询,对资源有特殊要求
2.问答式界面,对话框,适用于不熟悉特定应用或不了解某个主体的用户

3.菜单:
优点:分类显示,不杂乱;减少界面无关信息;嵌套菜单可以提高用户的操作速度。
指导原则:
•层次和分类要清晰,不能混淆,
•主菜总是单停留在导航栏
•子菜单的层数不要超过3层
•下拉菜单按功能特征分区或者分组
•元素不要太拥挤,不重复,不遗漏,先主后次。
•选中主菜单的词后,弹出下拉菜单。
•不可用的选项灰色表示

4.Form表单
用于输入和输出
•原则:
屏幕窗体要说明应该输入什么信息,以及在哪里输出。
在空白字段中输入数据时,输入内容应该反白或闪烁显示。
为简化窗体数据的输入,可预先给出默认值。
•优点:打印出的表单内容是极好的文档
•缺点:让有经验的用户厌烦,总希望找到一种更有效的数据输入方法。

5.命令行:专业、学习难

6.对话框
采用标准的操作,保证一致性,交流要有意义,提供最少的操作交互和行为。

7.其他类型的用户界面
指示笔、触摸屏、语音识别与合成、触摸屏
语音交互的优点:让用户能腾出手来完成其他事项的同时,如驾驶,可以极大的提高数据输入速度。为有视觉或行为障碍的用户提供方便。

8.4.为用户提供反馈

1.反馈类型
a)确认接受了输入数据
b)确认输入格式正确

c)提示输入格式不正确
反馈可以是新的界面、消息框、音频反馈
反馈要保证效率和准确性

d)解释系统运行中的延迟
e)确认请求完成
f)提示用户请求无法完成
g)为用户提供更详细的反馈

2.在系统设计中包含反馈
a)提供各种帮助选项,F1,
b)下拉菜单帮助
c)鼠标悬停的提示文本
d)帮助向导
e)帮助热线

8.5.电子商务网站的设计原则

1.在网站上采用各种方法从客户处获得反馈
在用户启动电子邮件程序的同时,自动把公司的邮件地址放在“收件人”处
添加反馈按钮,点击后打开信息模板

2.采用4种方法提供一次点击的导航,以确保用户容易地在网站中导航,并易于返回原来的网页。
1)建立卷滚菜单
2)在主页上按分层关系建立网站链接集,显示关键主题框架。
3)把网站地图放在主页上,并突出到该地图的链接,提高导航效率。
4)在网站内每一个页面上设置导航条,重复首页上的条目。

两个好用的Chrome插件,小伙伴们看完复习资料支持一下吧: [剪影截图:好用的网页截图,一键人人分享工具,快捷键ctrl+shift+z, 双击确定!](https://chrome.google.com/webstore/detail/剪影截图/gkloklemhahnoipikedmafefilidffko "剪影截图") [TSS下载助手:让你方便一键批量下载](https://chrome.google.com/webstore/detail/tss下载助手/odhkpoplnhfnhhhkgphckabboemiifle "TSS下载助手")

资源:
系统分析与设计part1
系统分析与设计part2
系统分析与设计part3
系统分析与设计part4

System Analysis and Design (Kenneth Kendall) Review Part2

4. 分析:使用数据流图

4.1.数据流图功能和优点

概念化数据在整个组织是如何流动的,数据经历的过程和变换,以及输出。
优点:
(1) 不必过早着手系统和技术的实现。
(2) 进一步了解系统和子系统的相互关系。
(3) 通过数据流图与用户交流当前系统的知识。
(4) 更好地了解业务,分析建议的系统以确定是否定义了必要的数据和过程。[more…]

4.2.数据流图的图例规范


1. 实体的命名:名词
2. 数据流命名:名词
3. 过程命名
在上下文图中,赋予整个系统的名称, 如“选课系统”
命名子系统时,使用诸如“预定子系统”, “Web用户执行系统”
具体过程命名:动词+形容词+名词 “计算净工资”,每一个过程要有一个唯一编号,指出它在图中的层次。

4.3.开发数据流图步骤

1. 步骤
1)制定一个业务活动列表:实体,数据流,过程,数据存储
2)创建上下文图,外部实体+输入+输出+系统,没有过程和数据存储
3)0层图:分解系统,展示高层的过程和数据存储,过程一般不超过9个,为避免数据流线交叉,同一个实体和数据存储可以出现多次。
4)画0层图中每个过程的子图
注意编号与父过程相同
纵向平衡——不能有父过程没有的输入和输出。
子图中通常不显示实体,显示接口数据流。
可以有父过程中没有显示的数据存储。
5)检查错误:编号正确,命名正确,输入输出清晰,没有back hole, 没有miracle
6)根据逻辑数据流图,开发物理数据流图:通过名字描述真实地文件和报表的物理存储,增加控制以指出合适过程完成或发生错误。
7)分割物理数据流图。

2. 注意点

  1. 图例和标识的准确性
  2. 数据流:不能从实体到实体,不能存储到存储,可以从实体到过程,过程到过程,过程到存储
  3. 数据流图的层次性
  4. 尽量不要有线性流,即一个输入和输出的过程,出现通常是遗漏了数据流,一个过程输入和输出总数在>=4个以上最好。
  5. 用户要能理解

4.4 如何向用户解释数据流图

1. 数据流图的标记要具体而有意义、
2.可以通过举例,类比和问询,让用户了解DFD的原理
3.每个DFD的过程控制在9个以内,太大的图,则要分解,保证在一页纸内
4.结合表格和图表向用户解释

4.5.逻辑数据流图 vs 物理数据流图

  1. 二者的区别

2)逻辑数据流图优势
a)更好地与用户交流
b)系统更稳定
c)更好地了解业务
d)灵活、更易维护
e)消除冗余,更容易创建物理模型

3)物理数据流图优势
a)澄清哪些过程是手工的,哪些是自动的
b)更详细的描述过程
c)标识临时数据存储
d)指定真实地文件名和打印输出名
e)增加确保正确地完成过程的控制。
物理数据流图创建方法:事件建模法,用例法.

5. 使用数据字典分析系统

5.1.数据字典的基本概念

1.数据字典定义
是一种关于数据的数据参考书,指导系统的分析与设计,包括数据流,数据结构,数据元素和数据存储。

2.数据字典的必要性
a)作为数据的记录文档
b)消除冗余,保证数据的一致性
c)验证DFD的完备性和准确性
d)为开发界面和报表提供切入点
e)找出数据流图中过程的逻辑
f)创建XML

3.DFD与数据字典的关系

5.2 数据流的描述

通过DFD确定系统的输入和输出,对每个数据流描述如下,具体实例可以看书。
1)ID:可选标识符
2)数据流名称
3)数据流描述
4)数据流来源
5)数据流目标
6)数据流类型:文件、界面、报表、表格或内部数据(中间的临时数据)
7)包含的数据结构
8)单位时间的流量
9)备注

5.3.数据结构描述

1.描述
1)= 表示组成
2)+ 表示“和”
3){} 表示重复元素,一定有至少一个 1n,可以包含固定重复次数,或上限与下限
4)[] “非此即彼”,互斥的选择
5)() 表示可选元素 0
1

2.逻辑数据结构和物理数据结构
逻辑数据结构是业务上,用户看到的数据。物理数据结构是软件实现所需要的数据。
物理数据结构需要增加:
1)键字段,唯一标识一条记录
2)标识主记录的状态代码,诸如一个雇员当前被雇佣或否。
3)如果一个文件包含不同的记录类型,则可以用交易码标识记录的类型。例如,包含返还项的记录和支付记录的信用文件。
4)重复组数据项,包含该组中有多少个数据项的计数。
5)重复组中数据项多少的限制
6)客户访问一个安全Web站点的密码。

5.4 数据元素描述

1)ID, 可选的
2)元素名称
3)别名
4)简短描述
5)是基本元素还是派生元素

6)元素长度:
对于数值金额的长度,给出最大数额。
名称和地址,给出合适的长度
对于其他字段,参照历史数据

7)数据类型:数值,日志,字母,varchar,字符
8)如果用特殊编码符号表明应当如何表示数据,则应包含输入和输出的格式。

9)验证标准,保证数据的精确性,对于离散或连续的数据有以下标准
a)某个值范围适合包含连续数据,如GPA 0.00~4.00
b)如果数据式离散的,则指出一组值
c)如果值的列表是泛指的,则可以采用一个代码表
d)对于键或者索引元素,通常包含一个校验位

10)提供某些元素的默认值
11)备注区域

5.5.数据存储描述

1)ID,必须有
2)数据存储名
3)文件的别名
4)简短描述
5)文件类型:人工文件或计算机文件
6)如果是计算机文件,则文件格式指明是数据库文件,还是传统的平面文件
7)文件上记录的最大记录数和平均记录数
8)文件或数据名指定的文件名(如果已知)
9)数据结构应使用数据字典中的名字,提供与此数据存储的元素的连接

5.6.创建数据字典

1.先创建DFD,自顶向下开发数据字典和数据流图。可以为每一个层次的DFD创建数据字典。

子数据流图上的数据流名称,包含在父过程上的数据流的元素或结构化记录中

2.分析输入输出
输入输出分析表包括:
1)输入或输出的描述名
2)负责进一步澄清细节、设计反馈和最后核准的用户联系信息
3)输入数据还是输出数据
4)数据流的格式。逻辑DFD,可以处于未确定
5)表明报表上或者界面上的数据顺序的元素
6)一个元素列表,包括元素的名称、长度,是基本元素还是派生元素,编辑标准。

3.开发数据存储
确定永久信息或临时信息。

5.7.使用数据字典

数据字典可以用来创建界面、报表和表单
1.使用数据字典产生计算机语言时要考虑
1)输出数据流中的基本元素必须出现在产生该输出数据流过程的输入数据流中。基本元素由键盘输入,而不由某一个过程创建
2)派生元素必须由过程创建,并且至少应当由一个不是该元素自身为输入的过程输出
3)输入或者输出某个数据存储的数据流中的元素,必须包含在该数据存储中

2.使用数据字典可以创建XML文档
XML是一种可用来在企业中交换数据的语言,是一种对数据进行定义、排序、过滤并把它转换成一种每个人都可以使用的统一数据语言的方法。

两个好用的Chrome插件,小伙伴们看完复习资料支持一下吧: [剪影截图:好用的网页截图,一键人人分享工具,快捷键ctrl+shift+z, 双击确定!](https://chrome.google.com/webstore/detail/剪影截图/gkloklemhahnoipikedmafefilidffko "剪影截图") [TSS下载助手:让你方便一键批量下载](https://chrome.google.com/webstore/detail/tss下载助手/odhkpoplnhfnhhhkgphckabboemiifle "TSS下载助手")

资源:
系统分析与设计part1
系统分析与设计part2
系统分析与设计part3
系统分析与设计part4

System Analysis and Design (Kenneth Kendall) Review Part1

系统分析与设计,感觉上是一个需求和软工的大汇总,不温不火,方面很多,只能算是对软件工程的overview。

1.信息收集交互式方法

交互式信息收集有:面谈、联合应用程序设计JAD和调查问卷.

1.1 面谈

1. 面谈的概念
面谈是一种面对面的会谈,目的明确,一般采用问答形式。面谈时,需要获取面谈对象的观点,他们对系统当前状态、组织和个人目标、以及非正规过程的感受。[more…]

  • 调查面谈对象的观点。
  • 尽力获取面谈对象的感受。
  • 目标是尽力收集重要信息,组织的目标。
  • 面谈也是考察HCI问题的宝贵时机。
  • *2.面谈的5各步骤**

1)阅读背景材料:与面谈对象建立共同词汇
2)确定面谈目标:问题中应该有4-6个与HCI、信息处理和决策行为有关。
3)决定面谈对象:按层次和影响力选择谈话对象。
4)准备面谈对象:打电话或者邮件提前预约
5)决定问题的类型和结构:金字塔结构、漏斗结构或者菱形的结构

3.问题类型
1)开放式问题
优点:
•让用户谈话自在
•可以收集面谈对象使用的词汇,这能反映其教育背景、价值标准、态度和信念
•提供丰富的细节,广度
•对尚未的进一步的提问方法有启迪作用。
•让面谈对象更感兴趣
•允许更多的自发性
•会见者更容易措辞
•在会见者没有准备的紧要关头采用这种类型
缺点:
•容易不切题,产生太多不相干的细节
•时间冗长,花费大量时间才能获得有用的信息
•可能会让用户觉得你没有准备,不够专业
•留下不好的印象,用户会觉得你在做没有实际意义的调查
•后期数据分析较难

2)封闭式问题
优点
•有针对性,切中要点
•能获得准确、贴切的数据
•时间上可控,节省时间,可以快速探讨大范围问题。
•保持对面谈的控制权
•数据分析容易
缺点:
•让用户厌烦
•得不到丰富的细节,失去主要思想
•不能建立和面谈对象友好的关系

4.问题结构
1)金字塔:先封闭后开放,先具体后一般化,用于用户需要预热,开始拘谨的情况
2)漏斗:先一般后具体,适用用户一开始就有激情的情况
3)菱形:具体——一般——具体,缺点是费时,优点是:具体的问题开始为面谈做好铺垫,再问一般化问题可以收集丰富的信息,再用具体的问题收尾,为面谈提供了结束的时机。

1.2 JAD联合应用程序设计

由IBM开发,一种一对多的面谈方法,目的是节省个人面谈所需的时间,减少成本;改善信息需求评估结果的质量;通过多方一起参加的过程,获得用户对新信息系统的更多的认可。
1.条件
•用户时间有限,一对一面谈不行
•公司文化允许不同层次的职员间联合问题求解
•用户想有点新东西,创新意愿强,而一对一面谈难以得到统一的意见
•组织允许关键职员离职24天
2.涉众:
分析员、用户、主管等,
一个沟通能力好的主持人
8
12位不同阶层的用户
需要有两名置身事外的观察员,保证JAD的进行。
3.召开会议地点:一般式24天的脱产会议,在远离单位的舒服环境下
4.优点
•比面谈节省时间
•联合协作,可以实现快速软件开发。
•改善信息系统所有权的可能性。让用户早日参与系统,获得用户反馈
•创造性的开发设计,类似头脑风暴
5.缺点
•要求所有参与者抽出大块时间,2
4天
•任何一方准备不充分,或者后续报告和规范文档没有完成,最终得到的设计会不尽人意
•可能还没有充分发展必须得组织技能和组织文化,组织可能还不支持JAD

1.3 问卷调查

问卷调查是一种信息收集技术,它允许系统分析员研究组织中若干关键人物的态度、信念、行为和特征,而这些关键人物可能会受到当前建议系统的影响。
1.使用条件
•组织成员分布广泛
•系统项目涉及许多人
•推荐方案之前必须做探索性工作,希望在确定系统项目具体方向之前评估总体意见。
•希望在后续的面谈中标识并解决当前系统的所有问题。

2.问题类型
1)开放式问题:
要估计开发式问题答复的种类,不能太宽泛
开放式问题适合想了解公司成员对系统的产品方面,或对系统的过程方面的看法的情况,如果不能有效的列出所有可能的答复,考虑开发式问题。
优点:探索性好,广度和深度广,准备问题容易
缺点:完成速度慢,分析数据难
2)封闭式问题
如果要调查大量人员的样本,采用封闭式,数据好统计。
如果能有效的列出问题可能的相互排斥的所有答复,采用封闭式问题。
优点:完成速度快,分析数据容易
缺点:广度和深度窄,准备问题不容易,探索性低

3.措辞的选择
使用一致的和企业业务相关的术语
•保持措辞简练
•使用明确字眼,但避免过度明确问题,如收入等敏感信息
•保持问题简短
•不要选择低水平的语言,不要用高人一等的口气
•避免措辞的偏差
•向合适的人发放问卷,不要采用太多专业知识
•确保问题中涉及的技术的准确
•使用软件检验阅读水平是否合适回答者

4.在问题中的标度的使用
定标:为了度量属性或者特征而为他们分配编号或其他符号的过程。
1)度量:类别标度,区间标度
2)构造定标时要考虑:
有效性:度量的内容的程度
可靠性:度量的一致性,如果相同条件下两次调查一致,就是外部一致性
3)避免的问题
不严格的标度:可以把平均水平移到中心的左边或右边来避免
集中趋势:回答者都回答中间值,可以通过减少两个端点的差异,调整描述符的强度,创建一个更多结点的尺度来改善
光圈效应:避免在一个问题中印象带入下一个问题

5.问卷调查表的设计准则:
•留出充足的空白空间
•留出充足的空间来填写或输入答复
•使回答者能够清楚地标出他们的答复
•保持风格的一致
•提问顺序的选择:
(i)把重要问题放在前面,问题要先人后己,先问用户最关心的问题,再问系统或者调查目的需要的问题
(ii)把相似内容的问题放在一起
(iii)首先提出非敏感和非争议的问题

6.管理问卷调查表
1)回答者:按照调查对象的级别,在公司服务的年限,工作职责和对建议系统的兴趣来选择代表,要选择足够多的代表
2)管理调查问卷的方法:
a)同时召集所有有关回答者
b)亲自发放问卷,并回收
c)允许回答者自我处理,并放入中央的箱子里,如web问卷和email问卷,常用的方法,但是回收率可能低
d)邮寄给职员,并提供截止日期,填写说明和寄回邮资
e)email和web的方式管理

2. 信息收集非干扰性方法

包括:采样、调查、观察决策者行为和物理环境

2.1.采样

1. 定义:从某一种群的系统中选择有代表性的个体
2. 必要性:节约成本、加快数据搜集过程、提高效率、减少偏差
3. 四个步骤

  • 确定要收集或要描述的数据:考虑数据收集方法(调查、面谈、调查问卷和观察等),考虑研究目标
  • 确定采样种群:硬数据(两个月或全年的报表),采样的客户
  • 选择采样类型
  • 决定采样规模
    4. 采样类型:
  1. 便利采样:容易安排,五约束的非概率型采样,最不可靠
  2. 目的采样:选择对系统了解,感兴趣的人,这是非概率型采样,只有适度的可信度
  3. 简单随机采用:每个个体的机会相同,产生一个随机编号表,在文档和报表采用中不切实际。
  4. 复杂采样是最好的
  • 系统采样:在名单中每个K个人选择一个,缺点是存在周期问题,引入偏差,采样大量不成比例的职员
  • 分层采样:最重要的方式,在不同的层次,如管理层,社会阶层,在不同层次中按比例选择。当想对不同层次用户采用不同数据收集方法时采用分层采样。
  • 聚类采样:选择一组人或文档进行研究

5. 采样规模

  1. 确定采样属性
  2. 定位能查找到的属性的数据库或报表
  3. 分析属性,估计p,一般取0.1或0.5
  4. 主观是定一个值,i 作为区间估计
  5. 选择置信度 z,如 95%时 z=1.96
  6. 计算种群比例的标准差 σ=i/z
  7. 计算采样规模:n=(p(1-p))/σ^2 + 1
    置信度越高采样规模越大
    确定面谈时的采样规模: 至少与组织中每个阶层的3个人进行面谈,3个人种至少有一个来自组织中的不同部门。

2.2 调查

调查法:发现数据并对数据进行分析的行为。需要研究不同的硬数据。

2.2.1 分析定量文档

1.用于决策的报表
通常是与库存状态、销售量和生产有关的纸质报表
生产报表:包括最近价格、当前库存、最近劳动力和设备等信息
总结报表:提供公司的背景和战略信息

2.业绩报表: 估计实际业绩和预期业绩的差距

3.记录
a)检查数量和总数的错误。
b)寻找改善记录表格设计的机会
c)观察交易的数目的类型
d)寻求能用计算机简化工作的实例(即,计算和其他数据处理)

4.数据收集表格:有助于理解企业的信息流
a)收集所有正在使用的表格样品
b)标出表格类型:内部,手写,web表等
c)记录打算采用的分发方式
d)将打算采用的分发方式和实际收到表格的人做比较
数据收集表格的分析耗时,还可以对已经填好的数据表格进行采样,需要记住5个问题:
•表格填写完整了么?缺了什么
•有从未使用过的表格么?为什么?
•所有表格都向相应地人做了详细说明么?没有,为什么?
•如果有纸质的表格,和web表格,比较填写速度
•经常使用非官方的表格么?

2.2.2 分析定性文档

电子邮件、备忘录,留言板、工作区的签名、web页面、程序指南和战略手册
5个指导原则:
•检查文档中的关键比喻或主导比喻
•在文档中寻找局内人与局外人或“我们反对他们”的思想状况
•列出褒义或贬义的术语,文档中重复出现的术语
•查找在公共区域Web页面上公布的有意义的图形、标识语和图标的用法。
•识别出幽默感。

1.备忘录: 了解组织成员对价值、态度和信念的看法
2. 公告板或者工作区的标语与海报:体会公司的主流文化
3. 公司中的Web站点:分析网站内容的比喻、幽默和使用的特性(颜色、图形、动画和超级链接),从技术、美学和管理方面调查。 调查web站点和站点间的交互性、消息的可访问性和明显的安全性
4. 指南:程序指南和在线指南,指南很少会保持更新
5. 政策手册:价值观、态度和信念。
老师说不考但是上课说道物理环境,也是调查的一部分:办公设备、布置、公司文化,楼层安排,布告栏,email 论坛,公司色调。

3. 原型化方法

3.1 原型化方法

1. 原型:是实际运行的有产品的主要特征,基于软件最初版本的演习。不需要反映所有的功能,只需有软件功能的子集。
原型化方法是通过原型来获取有关建议系统和系统如何迅速满足用户信息需求的反馈的极好办法。
2. 原型分类一:
水平原型:多种功能的展示
垂直原型:对某一个功能进行详细展示

3.原型分类二(书中的分类)
•拼凑原型:构件一个可以运行,但又是经过修补或者拼凑而得到的系统。
•非操作原型:为了试验设计方案的某些方面而建立的一个非工作比例模型。如汽车实物模型。当编码成本高时采用
•系列首发原型:创建系统的第一个实物工作模型,即试验模型,是可以工作的原型。
•精选特征原型:建立一个包含最终系统部分特性而不是全部特性的可工作模型。

4.原型分类三
•抛弃式原型:尽可能快速开发
•试用型原型:最终的开发平台和原型相同
•试验型原型:最终开发平台与原型不同。

5.原型化方法的优点
•根据用户反馈,不断调整修改
•开发周期短,成本低
•缩短产品和需求的差别,开发出更贴近用户需求和期望的系统
•界面原型在获取用户反馈时有很大优势
•可以在系统开发早期改变系统
•可以中止一个不能工作的系统开发

6.原型化方法的缺点:
•需求不充足,开发者对用户需求不清楚,误解,过早的形成一个系统
•原型和最终系统之间存在差别,用户会误以为是最终系统
•开发者容易依赖原型,不愿意放弃原型
•原型开发成本高时会过度占用开发周期宝贵的时间,最初原型不能超过20%的时间
•经济损耗

7.原型化方法不适用的地方:
嵌入式系统:界面简单,与硬件太接近,需求明确
实时控制软件:搜索引擎,
科学计算:matlab,因需求明确,精度,效率,时间要求明确,模块太多,重要性均等,无法明确判定哪些是重要的需要原型化的。
但是很多应用,如游戏是适用于原型开发的。

3.2 原型开发

1. 原型化方法的要求:
用户是熟练的专家,可以给出反馈
重视界面,如手持设备
成本低,不会占用太长的开发周期

2.开发准则
•引进便于管理的模块:但不用建立完整的工作准则
•快速建立原型
•用连续迭代来修改原型
•强调用户界面:用户可以和原型轻松交互

3.原型开发流程
听取用户意见,修改原型,用户测试,不断循环迭代。

3.3 RAD快速应用程序开发

1. 定义:是一种面向对象的系统开发方法,包括开发方法和开发工具。目标是缩短传统SDLC方法中信息系统的设计和实践之间漫长的时间,反映需求的变更,是原型化方法的一种特殊实现。

2. RAD的阶段

1)需求规划阶段:确定系统的业务目标和信息需求
2)RAD设计研讨会:RAD的核心,与用户共同合作设计系统,讨论设计的非技术方面,并对构建的工作原型给出反馈
3)实现阶段:根据设计,建立、优化、测试新系统

3. Jame Martin RAD 四个阶段

1)需求规划:高级用户决定系统的功能
2)用户设计:与用户交互讨论系统的非技术方面
3)构建阶段:根据设计,用RAD工具构建,并向用户展示新系统,让他们交互、评论和检查。
4)转换阶段:新系统取代旧系统,测试新系统,培训用户

4.优势
•传统SDLC采用的是有序的、系统的开发方法,保证系统的完整性和精确性,
但抵制变更,不能很好地处理需求的变更。
•RAD缩短SDLC,更欢迎变更。

5.使用条件
•团队中有用过RAD的程序员和分析员
•由于商业压力,要求加快应用程序某部分的开发
•从事一项全新的电子商务应用程序,并且开发团队相信,如果应用程序是第一个或第一批出现在web上,则企业作为一个创新者取得竞争优势。
•用户经验丰富,对公司的组织目标高度负责。

6.缺点:缺乏文档

两个好用的Chrome插件,小伙伴们看完复习资料支持一下吧: [剪影截图:好用的网页截图,一键人人分享工具,快捷键ctrl+shift+z, 双击确定!](https://chrome.google.com/webstore/detail/剪影截图/gkloklemhahnoipikedmafefilidffko "剪影截图") [TSS下载助手:让你方便一键批量下载](https://chrome.google.com/webstore/detail/tss下载助手/odhkpoplnhfnhhhkgphckabboemiifle "TSS下载助手")

资源:
系统分析与设计part1
系统分析与设计part2
系统分析与设计part3
系统分析与设计part4

分布式系统总结Part4

Petri网

1. 以生产者消费者为例子

Petri三元组PN=(P,T,F)即,库所,变迁,转换弧

Preset表示前集,如果x是变迁,那么preset表示某个变迁的输入库所集合,如果x是某个库所那么preset表示某个库所的输入变迁。

Postset表示后集,如果x是变迁,那么postset表示某个变迁的输出库所集合,如果x是库所,那么postset表示某个库所的输出变迁集合。[more…]
Distributed System14

2. Marking, Enable, Firing

M(p)表示当前所有库所的Token数量, 是一个快照.
Distributed System16
通过这个图,可以很简单地看出 M(p)的计算等式.
当库所的token都到位后,变迁就enable了,如上图左边t2是enable的, t1没有enable, 如果Firing点火,就会转到另一个Marking下,如图中右边的图是点火后的Marking。

3.Handle

PP—handled : 某一个Place到另一个Place有两条不相交的路径

TT handled:某一个Transition和另一个Transition有两条不相交的路径

PT—handled:某一个Place到另一个Transition有两条不相交的路径

TP—handled:某一个Transition到另一个Place有两条不相交的路径

Well-handled:只有TT和PP,没有PT,TP。 因为PT会有死锁的风险, TP会造出某一个Place内部的Token无限增长

4.State Machine和Marked Graph

Distributed System17

  • Marked Graph:库所只有单个输入和单个输出
  • State Machine: 每个变迁只有单个输入和单个输出,这是一个有限状态机
  • T-component:如果一个大的Petri可以找到一个子网符合marked graph的要求,就是 T-component, 如果所有的T-component的集合可以覆盖整个Petri网,就是T-coverability。
  • P-component:是一个大的网络中的一个Petri子网,满足state machine的,如所有的P-component可以覆盖整个Petri网,则称Petri网P-coverability

5. 活性和有界性

  • 活性:从M0状态出发,对于任何一个M和t转换后的M’,可以让任何变迁T有可能点火enable.什么是不活呢,就是死锁,但是不死锁,不等价于活性
  • 有界性:不论状态如何变化,token数量都不会无限增长,保持在一定数量
  • Petri是well-formed的:存在M0使这个Petri网有活性并且有界

6. Free-choice structure

自由选择结构:如果两个输入库所交集不为空,蕴含两个输入库所相等

t1和t2是对等的选择关系.

自由选择结构可以表达并发关系和同步关系

给定一个自由选择结构,可以很好地决定它的活性和有界性。

7. 哲学家吃通心粉

有五个哲学家围坐在一圆桌旁,桌子中央有一盘通心面,每人面前有一只空盘子,每两人之间放一把叉子。每个哲学家思考、饥饿、然后,欲吃通心面。为了吃面,每个哲学家必须获得两把叉子,且每人只能直接从自己左边或右边去取叉子。

Distributed System15

资源

分布式系统总结part1 中间件,进程迁移,移动通信失效,名称解析,移动实体定位

分布式系统总结part2 Lamport同步与向量时间戳,两大选举算法,三大互斥算法

分布式系统总结part3 复制和一致性(以数据和以客户为中心的一致性),容错(拜占庭将军问题,两阶段与三阶段提交)

分布式系统总结part4 Petri网解决哲学家问题和生产者、消费者问题

分布式系统总结Part3

复制和一致性

数据的复制是为了提高性能和可靠性,但是我们需要保持各个副本的一致性:

问题一: 数据更新的实际分发问题,它需要关心副本的位置,以及如何在副本之间传播更新。

问题二:如何保持多个副本的一致性[more…]

以数据为中心的一致性

1. 严格的一致性

(1)条件:所有访问按绝对时间排序,数据项x的任何读操作将返回最近一次对x的写操作的结果所对应的值。

(2)要求:所有写操作是瞬间可见的,系统维持一个绝对的全局时间顺序,如果发生写操作,后续的读操作都会得到最新的写入的值。

(3)缺点:依赖于绝对的全局时间,分布式系统中为每个操作分配准确的全局时间是不可能的,一般是将时间分割成一系列连续的、不重叠的时间间隔,保证没个时间间隔内最多只发生一个单一操作。
精确的定义最后一次写操作是困难的,如图可以看到严格一致性
Distributed System02

2.线性化和顺序的一致性

(1)顺序一致性

条件:所有进程以相同顺序看到所有的共享访问,访问不按时间排序。任何执行结果都是相同的,就好像所有进程对数据存储的读、写操作按照某种序列顺序执行的,并且每个进程的操作按照程序所定制的顺序出现在这个序列中。

缺点:严重的性能问题,对于任何的顺序一致性存储,改变协议以提高读操作的性能必将降低写操作的性能,反之亦然。
Distributed System03
(2)线性化一致性

条件:所有进程以相同顺序看到所有的共享访问,访问根据(并非唯一的)全局时间戳排序。

在实际应用中,线性化主要用于开发算法的形式验证。关于根据时间戳维护顺序的附加限制使得线性化的实现比顺序一致性的实现开销更大。

3.因果一致性

条件:是一种弱化的顺序一致性模型,所有进程必须以相同的顺序看到具有潜在因果关系的写操作。不同机器上的进程可以以不同的顺序被看到并发的写操作.

当一个读操作后面跟着一个写操作时,这两个事件就具有潜在的因果关系。

Distributed System04

4.FIFO一致性

条件:所有进程以某个单一进程(有两个以上的写操作)提出写操作的顺序看到这些写操作,但是不同进程可以以不同的顺序看到不同的进程提出的写操作。

优点:容易实现,不需要保证不同进程看到相同的写操作顺序,除非两个以上的写操作是同一个进程提出的。这种情况下,写操作必须按顺序达到。

缺点:仍然对许多应用存在不必要的限制,因为这些应用需要从任何位置都可以看到按顺序看到某个单一进程所产生的写操作。同时并不是所有的应用程序都要求看到所有的写操作。这就引入了弱一致性。

Distributed System05

5.弱一致性

条件:引入同步变量,只有执行一次同步,共享数据才能保持一致。

a)对数据存储所关联的同步变量的访问是顺序一致的;b)每个拷贝完成所有先前执行的写操作之前,不允许对同步变量进行任何操作;c)所有先前对同步变量执行的操作都执行完毕之前,不允许对数据项进行任何读或者写操作。

特点:弱一致性是在一组操作,而非单个操作上强迫执行顺序一致性。同步变量用于划分操作的组。

缺点:即当同步变量被访问时,数据存储不知道此次访问是因为进程已经结束对数据存储的写操作还是因为进程将开始读数据而进行的。我们需要区分进程进入临界区和离开临界区的区别,引入了释放一致性。

Distributed System06

6.释放一致性

条件:退出临界区时,让共享数据保持一致,提供两种类型的同步变量。获取(acquire) 操作是用于通知数据存储进程进入临界区的操作,而释放(release)操作是表明进程刚刚离开临界区的操作。

  • 对共享数据执行读操作或写操作之前,所有进程先前执行的获取操作都必须已经成功完成;
  • 在释放操作被允许执行前,所有进程先前执行的读操作和写操作都必须已经完成;
  • 对同步变量的访问是FIFO一致的(不需要顺序一致)

Distributed System07

7.入口一致性

条件:它需要程序员(或编译器)在每个临界区的开始和结束处分别使用获取和释放操作,入口一致性要求每个普通的共享数据项都要与某种同步变量(如锁或障碍)关联。即让进程在进入临界区时,让属于同一临界区的共享数据保持一致。

优点:第一,将一系列共享数据项与各自的同步变量关联起来可以减少获取和释放一个同步变量所带来的额外开销。因为只有少数的数据项需要同步。第二,增加了并行度:这也使得多个包含不同共享数据的临界区可以同时执行

缺点:第一,同步变量和共享数据的关联带来了额外的复杂性和负载,程序设计可能更加复杂,容易出错。第二,关于入口一致性的一个程序设计问题是如何正确地将数据与同步变量关联起来。解决这个问题的一种方法是使用分布式的共享对象,向用户屏蔽低层的同步细节。

以数据为中心的一致性的比较

Distributed System18
Distributed System19

以客户为中心的一致性模型

1. 最终一致性

条件: 没有更新操作时,所有副本逐渐成为相互完全相同的拷贝。最终一致性实际上只要求更新操作被保证传播到所有副本

优点:开销小

缺点:移动用户访问分布式数据库的不同副本时,如果副本没有更新,会出现不一致。

2. 单调读

条件:总是读最新值,如果一个进程读取数据x的值,那么该进程对执行任何后续读操作将总是得到第一次读取的那个值或更新的值。
如果一个进程已经在t时刻看到x的值,那么以后他不再会看到较老的版本的x的值。

Distributed System08

3. 单调写

条件:总是在最新的拷贝上写,一个进程对数据项x执行的写操作必须在该进程对x执行任何后续写操作之前完成,保证写操作以正确的顺序传播到数据存储的所有拷贝。
在单调写一致性的定义中,同一进程的写操作的执行顺序与这些操作的启动顺序相同。

比较:注意,单调写一致性与数据为中心的FIFO一致性相似。FIFO一致性的本质是,同一进程执行的写操作必须在任何地方以正确的顺序执行。

这一顺序限制也适用于单调写一致性,只是我们这里考虑的是仅为单一进程维持的一致性,而不是为许多并发进程维持的一致性。

Distributed System09

4.写后读

条件:一个进程对数据项x执行一次写操作的结果总是会被该进程对x执行的后续读操作看见。 一个写操作总是在同一进程执行的后续读操作之前完成,而不管这个后续的读操作发生在什么位置。

Distributed System10

5.读后写

条件:同一个进程对数据项x执行的读操作之后的写操作,保证发生在与x读取值相同或比之更新的值上。进程对数据项上x所执行的任何后续的写操作都会在x的拷贝上执行,而该拷贝是用该进程最近读取的值更新的。

在读取的最新值上进行写操作。
Distributed System11

容错

1. 两军问题

两军的通信信道不稳定,需要达成一致才能发动攻击,无论双方发了多少次确认,都不能确定通信兵是否把自己的消息带给对方,永远不会达成协议。
在不可靠传输的条件下,即使是无错误的进程,在两个进程之间达成协议也是不可能的。

2. 拜占庭将军问题

通信良好,进程确不好,正如拜占庭的将军有叛徒的情况。

在这个问题中,红军还是在山谷中扎营,但是在附近的山上有n个带领部队的蓝军将领。通信是通过电话双向进行的,及时而且质量很好。但是有n个将军是叛徒(故障),他们通过给忠诚的将军发送错误的和矛盾的信息(模拟故障进程)来阻止他们达成协议。现在问题在于忠诚的将军是否还能达成协议。

Lamport采用递归算法来让无故障的进程达成协议。

N个进程,其中M个故障进程:只有当N>=3m+1时,才能达成一致,即有三分之二的进程是正常的。

3. 两阶段提交

Distributed System12
状态机很能说明问题。

两个阶段:vote_commit and global_commit, 3(n-1)条消息

缺点:两阶段提交的一个问题在于当协调者崩溃时,参与者不能做出最后的决定。因此参与者可能在协调者恢复之前保持阻塞。

因此引入3PC,三阶段提交,但3PC实际中用的少,因为2PC阻塞情况很少出现。

4. 三阶段提交

Distributed System13
没有一个可以直接转换到Commit或者Abort状态的单独状态。

没有一个这样的状态:它不能做出最后决定,而且可以从它直接转换到Commit状态。 Commit之前需要经过PRCOMMIT状态。

三阶段:vote-commit, prepare-commit, global-commit

引入了PRECOMMIT状态。

  • 2PC:崩溃的参与者可能恢复到了Commit状态而所有参与者还处于Ready状态。在这种情况下,其余的可能操作进程不能做出最后的决定,不得不在崩溃的进程恢复之前阻塞。
  • 在3PC中,只要有可操作的进程处于Ready状态,就没有崩溃的进程可以恢复到Init、Abort或Precommit之外的状态。因此存活进程总是可以做出的最后决定。当协调者崩溃,达到了预备提交阶段,在2PC中其他进程就会阻塞,但在3PC中,在预备提交阶段,即使没有协调者,也可以做出决定。

资源

分布式系统总结part1 中间件,进程迁移,移动通信失效,名称解析,移动实体定位

分布式系统总结part2 Lamport同步与向量时间戳,两大选举算法,三大互斥算法

分布式系统总结part3 复制和一致性(以数据和以客户为中心的一致性),容错(拜占庭将军问题,两阶段与三阶段提交)

分布式系统总结part4 Petri网解决哲学家问题和生产者、消费者问题

分布式系统总结Part2

Lamport逻辑和向量时间戳

1.Lamport逻辑时钟

Lamport认为,重要的不是所有进程在时间上完全一致,而是它们在事件的发生顺序上要达成一致。

先发生的定义: a → b 表示a在b之前发生,此时 C(a) < C(b), a b可以是同一个进程中的两个事件或进程间的消息发送事件。并发事件没有先后关系。

Lamport算法:[more…]

  • 遵循事件的先发生关系,每个消息都应携带根据发送者时钟的发送时间,当消息到达并接收时,接收者时钟显示的时间比消息发送者时间早时,接收者就将时钟调到比发送者者的时间大1的值。
  • 为了满足全局时间的需要:在每两个事件之间,时钟必须至少滴答一次,如果一个进程以相当快的速度发送或者接收两个消息,那么他得时钟必须在这之间至少滴答一次。
  • 两个事件不会精确地同时发生

2.Lamport逻辑时钟的缺陷

不能捕捉因果关系,而向量时间戳可以。

  • Lamport时间戳导致分布式系统中所有事件都要经过排序以具有这样的关系:如果a发生在b之前, 那么C(a) < C(b)
  • Lamport时间戳只能捕捉事件发生的先后关系,而不能捕捉因果关系。C(a) < C(b)不能说明a事件发生在b事件之前。 因果关系需要通过向量时间戳来捕获。

3.向量时间戳

因果关系:如果VT(a) < VT(b) 则a在因果上处于事件b之前。向量时间戳是让每个进程P都维护一个向量V来完成,该向量的性质如下:

a)Vi[i]是到目前为止进程Pi发生的事件的数量。

b)如果Vi[j]=k,那么进程Pi知道进程Pj中已经发生了k个事件

接收者可以通过消息m的时间戳知道其他进程中有多少事件发生在它之前,消息m在因果上可能依赖于这些事件。

当Pj收到消息m,调整自己的向量,将每项Vj[k]设置为max{Vj[k], vt[k]}, 然后 Vj[i]增加1

需要会看图计算向量时间戳:
Distributed System01
向量时间戳中只有各个分量都是小于关系时存在因果关系,而平行关系是并发关系。

选举算法

1. 欺负算法(Bully Algorithm)

算法:当一个进程发现协调者不再响应请求时,它就发起一个选举:

P向所有编号比它大的进程发送一个election消息;

如果无人响应,P获胜成为协调者;

如果有编号比它大的进程响应,则响应者接管选举工作。P的工作完成。

当以前崩溃的进程恢复时,它将主持一次选举,如果该进程是当前正在运行的进程中进程号最大的,就成为协调者。

总之进程号最大的总是取胜。

2.环算法——不使用令牌环

假设进程按照物理和逻辑顺序进行了排序,那么每个进程就知道它的后继者是谁了。

当任何一个进程注意到协调者不工作时,它就构造一个带有它自己的进程号的election消息,并将该消息发送给它的后继者。

如果后继者崩溃了,发送者沿着此环跳过它的后继者发送给下一个进程,或者再下一个,直到找到一个正在运行进程。

在每一步中,发送者都将自己的进程号加到该消息列表中,以使自己成为协调者的候选人之一。

最终,消息返回到发起此次选举的进程。当发起者进程接收到一个包含自己进程号的消息时,它识别出这个事件。此时,消息类型变成coordinator消息,并再一次绕环运行,向所有进程通知谁是协调者(成员列表中进程号最大的那个)以及新环中的成员都有谁。这个消息再循环一周后被删除,随后每个进程都恢复原来的工作。

互斥算法

1. 集中式算法

(1).算法

选举一个进程作为协调者,如最大网络地址号的机器上的进程。

无论何时一个进程要进入临界区,它都要向协调者发送一个请求消息,说明它想要进入哪个临界区并请求允许。

如果没有进程在临界区就发送“允许”应答,该进程进入临界区,如果有进程在临界区,就把该消息放入请求队列,发送“拒绝请求”的应答。

当临界区中的进程退出临界区,向协调者发送“释放”消息,协调者会从请求队列中取出第一个进程,发送“允许”进入的消息。

(2)优点

实现了互斥,每个时刻,协调者只让一个进程进入临界区。

很公平,没有进程会永远阻塞,不会饥饿,不会死锁

容易实现,每使用一次临界区,只需要三条消息(请求,允许,释放)

可以管理临界区或更一般的资源
(3).缺点

协调者是单点故障,在规模较大的系统中,单个协调者会成为性能瓶颈.

如果进程在发出请求之后阻塞,那么请求者就不能区分“拒绝进入”和协调者已经崩溃的两种情况。

2.分布式算法

1)Lamport算法

  • 当进程Si想进入临界区,向其他n-1个进程广播请求REQUEST(tsi, i), 并把请求放入自己请求队列request_queuei。

  • 其他n-1个进程受到请求REQUEST(tsi, i)后,把该请求放入各自的请求队列request_queuej, 并向进程Si响应一个带时间戳的REPLY消息。

  • 进程Si进入临界区,当且仅当满足以下两个条件:

      *   Si从其他进程收到的消息的时间戳都大于自己的请求时间戳(tsi, i)
    • Si的请求是请求队列request_queuei的第一个请求
  • 当进程Si退出临界区:从请求队列request_queuei中删除该请求,并向其他n-1个进程广播一个带时间戳的释放临界区的消息。其他n-1个进程收到该消息后,从请求队列request_queuej中删除该请求

在Lamport算法中,进程Request, REPLY, RELEASE一共发送了3(n-1)条消息,其实在一个接收者收到消息后,如果不同意Si进入临界区,没有必要再发送确认。
可以改进算法在2(n-1)到3(n-1)之间

2)Ricart和Agrwala算法,改进Lamport算法

  • 当一个进程想进入一个临界区时,它构造一个消息,其中包含它要进入的临界区的名字、它的进程号和当前时间。然后它将消息发送给所有其他的进程,理论上讲也包括它自己。
  • 当一个进程接收到来自另一个进程的请求消息时,它根据自己与消息中的临界区相关的状态来决定它要采取的动作。可以分为三种情况:第一,若接收者不在临界区也不想进入临界区,它就向发送者发送一个OK消息。第二,若接收者已经在临界区,它不进行应答,而是将该请求放入队列中。第三,如果接收者想进入临界区但尚未进入时,它将对收到的消息的时间戳和包含在它发送给其余进程的消息中的时间戳进行比较。时间戳最早的那个进程获胜。如果收到的消息的时间戳比较早,那么接收者向发送者发回一个OK消息。如果它自己的消息的时间戳比较早,那么接收者将接收到的请求放入队列中,并且不发送任何消息。
  • 在发送了请求进入临界区的请求消息后,进程进行等待,直到其他所有进程都发回OK消息为止。一旦得到所有进程的允许,它就可以进入临界区了。当它退出临界区时,它向其他队列中的所有进程发送OK消息,并将请求从队列中删除。(也就是说一个进程进入临界区的条件是收到了n-1个OK消息)

算法优点:不会饥饿,死锁;每次进入临界区仅需要2(n-1)条消息;没有单点故障

算法缺点:第一,单点故障变成了n点故障,如果任何一个进程崩溃,不能应答OK,这种不应答被错误的解释为拒绝请求,阻塞了所有进程进入任何一个临界区。第二,网络通信开销多于集中式算法;第三,要么必须使用组通信原语,要么每个进程必须维护组成员清单;第四,要求所有进程参与做出与进入临界区有关的所有决定,强迫每个进程都承担这样的负载是不可能的,可以在得到大多数进程OK的情况下进入临界区,但实现复杂。

3.令牌环算法

(1)算法

  • 假设:总线式的网络中,进程没有固定的顺序,环中为每个进程分配了一个位置,每个进程都直到谁在它的下一个位置。
  • 当环初始化时,进程0得到一个令牌token。该令牌绕着环运行,用点对点发送消息的方式把它从进程k传递到进程k+1(以环大小为模)。进程从它邻近的进程得到令牌后,检查自己是否要进入临界区。如果自己要进入临界区,那么它就进入临界区,做它要做的工作,然后离开临界区。在该进程退出临界区后,它沿着环继续传递令牌。不允许使用同一个令牌进入另一个临界区。
  • 如果一个进程得到了邻近进程传来的令牌,但是它并不想进入临界区,那么它只是将令牌沿环往下传递。因而,当没有进程想进入临界区时,令牌就绕环高速传递。

(2)优点

没有饥饿现象:任何时候都只有一个进程有令牌,并且令牌以固定的顺序循环传递。

(3)缺点

如果令牌丢失,必须重新生成令牌.

检测令牌丢失很困难,网络中令牌出现两次的时间间隔不确定,没有发现令牌可能是丢失,也可能是某个进程在占用。

如果有进程崩溃,该算法会有问题。(恢复方法: 要求每个进程维护进程环的配置信息, 每个进程收到令牌后发出确认信息,当它尝试把令牌传递给它的邻近进程时,如果没有收到确认,该进程就崩溃了,从组中删除该进程,继续传递令牌。)

三种互斥算法的比较

(1)程进入临界区,需要发送的消息数目不同

集中式算法: 3条消息,请求,允许,释放,简单而有效.

分布式算法:2(n-1)条

令牌环算法: 1~(n-1)条

(2)进入临界区之前的消息延迟不同
集中式算法: 2条消息,请求,允许。

分布式算法:2(n-1)条

令牌环算法: 0~(n-1)条

(3)三种算法在这三种算法在进程崩溃的情况下都损失惨重。为了避免进程崩溃造成的系统瘫痪,必须引入专门的措施和额外的复杂性。

资源

分布式系统总结part1 中间件,进程迁移,移动通信失效,名称解析,移动实体定位

分布式系统总结part2 Lamport同步与向量时间戳,两大选举算法,三大互斥算法

分布式系统总结part3 复制和一致性(以数据和以客户为中心的一致性),容错(拜占庭将军问题,两阶段与三阶段提交)

分布式系统总结part4 Petri网解决哲学家问题和生产者、消费者问题

分布式系统总结Part1

激动哥给了一些点,总结如下吧,算是对分布式的一些理解,希望对朋友们有帮助。

分布式系统系统基本概念

分布式系统是若干独立计算机的集合,这些计算机对于用户来说就像单个相关系统。透明性, 故障透明性。

本质: 硬件上——机器是物理上独立的。软件上——对用户来说它们就像载和单个系统打交道。分布式系统位于用户的应用层和底层操作系统之间,有时也叫做中间件.

分布式系统的目标:资源链接和共享,透明性,开放性,可伸缩性。[more…]

分布式系统作为中间件技术

  1. 中间件在分布式系统中的位置

    中间件:在应用系统和网络系统之间的附加的软件层,隐藏网络操作系统中低层平台集合的异构性,提供一组完整程度不同的服务集,提高分布的透明性。

    中间件的最高目标是透明性。同时也具有开放性、可扩展性和易用性

  2. 中间件模型

  • 基于分布式文件系统:任何东西都是作为文件来处理,只对传统文件支持分布的透明性,比网络操作系统前进了一小步,仍然要求进程显式启动分布式机器,有一定的扩展。
  • 基于RPC:允许进程调用位于远程机器上的过程实现来隐藏网络通信。调用参数透明的传递到远程机器上,看起来就像在调用本地的进程一样,不知道网络通信的发生。
  • 基于分布式对象: 调用分布在远程机器上的对象的接口,通过消息传递调用

3.中间件通信技术

(1) RPC

使用客户端存根和服务器端存根,实现访问的透明性,按值传递,对引用传递的支持比较弱, 基于响应的暂时同步通信。

(2) RMI——远程对象调用

不使用用客户端存根和服务器端存根,使用针对对象的存根。本质上是RPC,但针对远程对象。

(3) MPI:面向消息的通信

RPC和RMI的不足:要求远程机器正在执行; 并且对同步要求高,客户在发出请求后阻塞

通信类型:持久通信,暂时通信;异步通信,同步通信; 两两正交共四种。

•持久异步通信:如邮件系统,消息队列

•持久同步通信

•暂时异步通信:如异步RPC,UDP

•暂时同步通信:基于接收的暂时同步通信:最弱的基于消息接收机制; 基于交付的暂时同步通信;基于响应的暂时同步通信: RMI, RPC。

MPI比套接字提供更多的抽象的消息传递原语,提供持久异步通信,用在RPC和RMI不适用的场合,它们主要用来协助将高度分散的数据库集成进大规模信息系统中。其他的应用还包括电子邮件和工作流。

(4)面向流的通信:

流是一种完全不同的通信方式,它的主要问题是两个连续的消息是否有时间上的联系。如音频流和视频流,同步很关键。

在连续数据流中,每个消息都规定了端到端的最大延迟时间。另外,发送的消息还要受端到端最小延迟时间的约束。

三种传输模式

异步传输模式:数据项是逐个传输的,但是对某一项在何时进行传输并没有进一步的限制。

同步传输模式:数据流中每一个单元都定义了一个端到端最大延迟时间。

等待传输模式:模式中数据单元必须按时传输,也就是数据传输的端到端延迟时间必须同时受到上限和下限的约束,实时系统。

进程迁移

  1. 弱迁移 vs 弱迁移

    弱迁移:即代码的可移植性,只传输代码段以及某些初始化数据,传输过来的程序总是以初始状态重新开始执行,弱可迁移性只要求在目标机器上能执行该代码段,例如Java Applet小程序,这种方法的好处在于简单性。

    强迁移:迁移执行中的进程,先停止运行中的进程,捕捉运行现场,迁移到另一台机器上,从中断处继续运行,强迁移比弱迁移实现难度大,例如D’Agent是支持强可移动性的一个例子(Dartmouth College)

  2. 发送者启动迁移 vs 接收者启动迁移

    发送者启动迁移,代码或正在执行的进程在哪台机器上,就由该机器来启动迁移,例如向Web服务器发送搜索程序运行查询。这种迁移容易实现.

    接收者启动迁移,代码迁移的主动权在目标机器手中,例如Java Applet

    区别:接收者下载代码到客户端,性能好,安全性好,客户端只有少数的资源需要保护,如内存和网络连接等;

    发送者启动迁移,上传代码到服务器端,需要认证用户,需要对服务器资源提供强保护。

  3. 在目标进程内执行迁移代码 vs 在派生进程内执行迁移代码

三种方法相互正交,形成了8中进程迁移方法,如图:

Distributed System20

移动Agent的基本概念

  1. 定义:是一种分布式的应用,移动Agent是一个运行于开放、动态网络环境中的,封装良好的计算实体,可自主地在异构的网络上寻找合适的计算资源,然后移动到资源所在机器上使用这些资源,它代表用户自主地在网络上移动,完成指定的任务。移动Agent由数据、操作、行为规则 封装而成。

  2. 基本特点:

  • 自主移动性:不拘泥于初始执行结点,可再网络各主机间自主移动。移动Agent可以将自身的状态和代码从一个环境迁移到另一个环境,并恢复执行。
  • 协作性:移动Agent可以和其他Agent进行自主通信,协作完成任务。
  • 安全性
  • 移动功能而不移动数据,减少网络负担和延迟

Mogent解决移动通信失效

1.移动通信失效定义

移动Agent最大的特性是移动性,其通信机制要求位置透明性,可靠性,高效性,异步性,自适应性。但在Agent自主移动过程中,常会导致消息发送到某一网络节点但接收者已经离开无法收到消息的情况,这种因为目标Agent的物理位置变化造成通信不正常的现象称为移动Agent通信失效。通信失效与网络和节点故障无关,完全是由Agent的移动性造成的,这是移动Agent协作的致命缺陷。

2. Mogent系统架构

一个完整的移动Agent通信协议至少包括Agent寻址和消息传送两大部分。Mogent系统采用结构化旅行计划模型。

Mogent的架构中有两个重要实体:

  • Mogent: 即移动Agent,可以协同工作。
  • Host:一个物理节点的抽象,由IP地址或域名来标识,每一个Host安装MogentServer,维护管理本地的Mogent,主要由迁移子系统、通信子系统、安全子系统和开发监控子系统构成。

3.Mogent系统的寻址

Mogent-Server中有两个部件Home和Communicator完成Agent的透明寻址。

Home:记录Host上“出生的”Agent的动态信息,Agent每次迁移到另一台Host必须向出生地登记当前的地址和物理名,基于起始位置的定位。

Communicator:记录当前Host上所有agent的信息,Agent迁移时要向Communicator register 和 unregister, 负责agent之间通信的目标寻址、信件转发和通信失效排除等通信细节。

4.通信失效的解决:消息传送

通信失效问题本质上是通信和移动所共享的“位置”信息未同步造成的。
Mogent系统中引入了“状态”的概念,每个Agent的状态分为迁移态和静止态。

同时引入两个信号量进行集中式同步控制策略,通过Home-Communicator集中管理对目标Mogent的地址信息的互斥访问,从根本上避免通信失效的发生,保证通信的可靠性。

  • 迁移状态:由Home构件记录Agent的状态,当Mogent在一个Host上时状态为静止态,当按旅行计划准备迁移时Mogent要通知Home更新状态为迁移态。
  • 在途信件数:保存在Host上,记录当前时刻以该Mogent为通信对象的在途信件数,发出信件,在途信件数增加,信件到达,在途信件数减一

消息发送机制:Mogent通过控制“在途信件数”和“迁移状态”这两个信号量,确保消息发送者仅向处于静止状态的Agent发送消息

Mogent迁移机制:Agent只有在没有消息发送给他的情况下才能移动。

5.Mogent局限性

  • 频繁迁移,Home的地址注册开销大,会拥挤
  • Agent迁移受到信号量的限制,影响Agent的自主性和移动性

两种名称解析方法:递归和迭代

分布式系统中名称用来标识一个实体,有三种类型——名称、标识符、地址,名称解析就是查询名称的过程。

1.迭代名称解析

客户端把需要解析的名称路径发给根服务器root,根服务器解析出下一个服务器server1的地址返回给客户端,客户端再查询server1,server1再解析出server2的地址…

如此迭代直到能解析出所需实体的地址。例如:考虑绝对路径名:root:<nl, vu, cs, ftp, pub, globe, index.txt>的解析,第四章PPT上有详细的说明

总之迭代名称解析是客户端发起迭代查询。

2.递归名称解析

客户端把需要解析的名称路径发给根服务器root,根服务器解析出server1的地址后,不把结果返回给客户端,直接把名称传给server1,由server1解析后,再传给server2…不断递归,最后将解析出的实体地址返回给根服务器,根服务器再将实体地址返回给客户端。

3.两种解析的比较
递归名称解析的缺陷:要求每台服务器具有较高的性能,根服务器要完成完整的名称解析,开销较大,一般在名称空间的全局层中,采用迭代名称解析。

优点:与迭代名称解析相比,递归解析可以有效的使用缓存提高性能;减少了通信开销,通信开销取决于客户主机和服务器之间的信息交换。

而在DNS解析中:从客户机到本地DNS的查询是递归查询,从本地DNS到到其他DNS服务器之间的查询是迭代查询

移动实体的定位

移动实体的定位方法:使用与位置无关的标识符有效地实现定位。

1.广播和多播

原理:包含该实体所用标识符的消息会广播到每台机器上,并且请求每台机器查看它是否拥有该实体。只有能够为实体提供访问点的机器才会发送回复消息,回复消息中包含访问点的地址。类比ARP

缺点:扩展性不好,随着网络的膨胀,广播变得更加低效。

可以采用多播向特定的一组主机发送标识符,使用多播查找最近的复制实体,但实践证明,选择最近的复制实体没有那么容易。

2.转发指针

原理:每当一个实体转移到另一个位置时,他就会留下一个指针,说明它下一步所在的位置。 例如:当实体从A移动到B时,它将在A中留下一个指针,这个指针指向它在B中的新位置。

定位实体需要遍历转发指针形成的路线。为了避免形成太长的指针链,定期缩短指针链很重要。

优点:简便,一旦找到一个实体,就可以顺着转发指针链查找到实体当前的地址。

缺点:链可能特别长,定位实体的开销较大。链很脆弱,容易断开,只要一个转发指针丢失,就无法定位实体。一个解决办法是让指针链相对短一些,确保转发指针链的健壮性。
链中所有中间位置就必须维护它们的那一部分指针链。

3.基于起始位置的方法

原理:每当实体转移到一个地方时,他会通知起始位置,告诉起始位置自己当前的位置,在定位实体时,首先询问起始位置,以便了解实体的当前位置。起始位置就是创建实体的位置。

优点:大型网络中进行实体定位,如Mogent

缺点:为了与移动实体通信,需要先和起始位置通信,而起始位置和实体本身的位置处于完全不同的位置,增加了通信延迟。 使用起始位置,必须保证起始位置始终存在,否则将无法定位实体。起始位置如果转移到另一个网络,将会无法定位实体。一种解决的办法是:注册起始位置,客户先查找起始位置所在的位置,起始位置相对稳定,可以缓存它。

4.分层方法——创建一颗搜索树

原理: 网络划分成不重叠的分层域。只有一个顶级域,它覆盖了整个网络,每个域又可以划分为更多的子域。最低层的域叫做叶域,与网络中的局域网向对应。

每个层次的每个域都有关联的目录节点,目录节点会持续跟踪实体,形成目录节点树。

顶级域拥有每个实体的位置记录(指针),其中每条位置记录都存储一个指向更低层子域目录节点的指针

优点:查询操作是在局部进行,最差情况下,搜索会从叶域一直查到根域,再从根域到达包括该实体地址的子域。更新,插入和删除操作是局部进行:从叶节点到根节点。

缺点:第一, 定位实体的开销较大,从叶节点到根节点,再到叶节点。一种解决方法是采用指针缓存。第二,扩展性问题: 根节点需要存储所有实体的位置记录, 并为每个实体处理请求, 太多的查询和更新请求会成为瓶颈。解决办法是把根节点和其他高层目录节点划分成多个子节点,每个子节点处理实体的定位请求。
这些子节点最好均匀的扩散到网络中

资源

分布式系统总结part1 中间件,进程迁移,移动通信失效,名称解析,移动实体定位

分布式系统总结part2 Lamport同步与向量时间戳,两大选举算法,三大互斥算法

分布式系统总结part3 复制和一致性(以数据和以客户为中心的一致性),容错(拜占庭将军问题,两阶段与三阶段提交)

分布式系统总结part4 Petri网解决哲学家问题和生产者、消费者问题

Netkit Filesystem 定制和裁剪

Netkit, “The poor man’s system for experimenting computer networking”,是基于Linux的开源网络实验环境,该环境通过启动多台Linux虚拟机,模拟路由器,交换机和PC的网络通信功能,Netkit中预装了路由协议软件包Quagga,可以提供多种路由协议功能,如RIP, OSPF, BGP,IS-IS等,Netkit主要用于网络功能的模拟,而不做网络性能的模拟。

最近花了一周的时间实验Netkit,是网络的大作业,如果不是作业的机会,也不会有空去看这么古老的Netkit,他是北欧开发的一个开源网络实验环境,相比Packet Tracer美观的图形界面,对于没有图形界面的Netkit来说,Netkit的优势在于提供了用户模式的Linux内核,每一个虚拟机就是一个Linux系统,可以更真实地模拟路由等网络功能,用户通过命令行操作虚拟机,能更好地学习和实验网络,而不是学习一个Cisco设备。如果有朋友以后用到Netkit,希望这个Blog会helpful。

Netkit主要由三部分构成:

  • netkit-core: 包含启动虚拟机和网络实验的脚本文件,如vstart,lstart等。
  • netkit-uml-filesystem: 这是一个基于Debian的文件系统,Netkit在该文件系统中安装了软件包,并配置了quagga,ebtables, iptables等服务。Netkit的文件系统是“copy-on-write”的模式,每个虚拟机启动时会生成一个*.disk文件,该文件就是该文件系统的拷贝,在虚拟机中作的任何更改都不会影响Netkit的Filesystem,修改写入*.disk文件.
  • netkit-uml-kernel: 这是一个linux kernel, Netkit通过patch文件对kernel进行了相关配置,Netkit的kernel是用户模式的linux进程,也叫做虚拟机,我们可以在Linux系统如Ubuntu中启动netkit,kernel进程的运行依赖于文件系统。
    我们发现Netkit的文件系统解压后超过10GB,每次启动一个虚拟机就会产生一个10GB的*.disk文件,占用空间较大,我们主要使用Netkit的Quagga进行路由协议的模拟,而Netkit很强大,提供了apache, FTP, openssl,openvpn, DNS, email等功能,我们不需要这些冗余功能,因此我们着手重新制作一个文件系统,并尽量让文件系统容量小,提高Netkit网络实验的性能。

Netkit官方提供了Makefile文件让开发者自己Build文件系统,然而实验后发现官方Makefile无法运行通过,并且Netkit官方指南中并不建议自己Build一个文件系统,在Google后也没有发现更多有用的文档,因此希望通过本Blog详细地描述如何制作一个小巧可用的Netkit文件系统以及遇到的问题。 [more…]

实验成果

最终定制和裁剪的文件系统只有335M,该文件系统基于Debian Squeeze版本定制,没有采用当前的最新版本Wheezy版,因为并不修改Netkit-Kernel,最新版的Wheezy文件系统和现有的Netkit Kernel不兼容。

该文件系统的制作简单来说,分为三个阶段:制作基础的linux filesystem, 配置为可用的Netkit文件系统,安装quagga和必要的软件包。这些步骤都是通过shell命令来完成的。

你可能会问,为什么是335M?我们最早制作的文件系统是2GB,在运行稳定后,我们发现2GB是稀疏文件,在虚拟机中通过df命令我们看到磁盘空间只占用了310M,在基础的Linux文件系统安装好后,磁盘占用空间在250M左右,而我们安装了less,vim,chkconfig,quagga,telnet, telnetd, tcptraceroute这7个必要的包后,磁盘占用空间为310M+,因此我们取文件系统320M来制作,在制作完成后,大小为335M。

最终制作和裁剪的文件系统通过了静态路由,RIP, OSPF Single Area, OSPF Multi Area, BGP的测试。

定制文件系统的源代码在:NetkitNewFS

测试的实验拓扑文件在:NetkitLabs

准备工作

1. Ubuntu 32位环境或虚拟机

Netkit是基于32bit的Linux系统编译的,建议在32bit环境下运行,64Bit的机器安装会缺一些lib包,让工作更加麻烦.

2. 安装Netkit

其次,安装Netkit,参见官方网站,安装很简单,解压+配置环境变量。

也可以看NetkitNewFS源码下的README,有安装方法。

定制流程

整个定制过程大体可以分为三歩:制作基础的Linux内核文件系统,修改文件系统为可用的Netkit文件系统,为文件系统安装Quagga。下面让我们按照这个顺序来看看整个定制流程。

step1.制作基础的Linux内核文件系统:

我们直接写一个bash脚本来完成第一步制作基础的Linux内核的文件系统的工作,完整的脚本内容如下:

脚本不长(netkit-fs-build.sh)
[bash]
#!/bin/bash
echo "====================Installing Base Linux System======================"
FS_NAME=netkit-fs-light
MOUNT_DIR=/mnt/nkfs2
FILESYSTEM_SIZE=320

each cylinder has 63 sectors, each of which is 512 bytes

let CYL_COUNT=$FILESYSTEM_SIZE*1048576/32256

Create empty netkit-fs file

dd if=/dev/zero of=$FS_NAME bs=1M count=0 seek=$FILESYSTEM_SIZE

Create image partition

echo ",,L,*" | sfdisk -q -H 1 -S 63 -C $CYL_COUNT $FS_NAME

Binding lookback device to netkit-fs

device_name=$(losetup -f)

The offset is the size of one track

losetup –offset 512 $device_name $FS_NAME

Create ext2 filesystem

mkfs.ext2 $device_name
losetup -d $device_name

Mount netkit-fs

rm -rf $MOUNT_DIR
mkdir $MOUNT_DIR
mount -o loop,offset=512 -t ext2 $FS_NAME $MOUNT_DIR

Install the base filesystem from Internet

debootstrap –arch i386 squeeze $MOUNT_DIR http://ftp.cn.debian.org/debian
echo "=================Base Linux System Installed Success=================="

umount $MOUNT_DIR
echo "done!"
[/bash]
脚本的功能是创建一个320M的文件,采用sfdisk创建Linux分区表,绑定到环回设备上创建ext2文件系统,在mount到主机的/mnt/nkfs2下,通过debootstrap命令联网联网下载并安装Linux Squeeze 文件系统。具体每一歩,在脚本注释中。
值得注意的是,脚本的最后部分,即命令:
[bash]
debootstrap –arch i386 squeeze $MOUNT_DIR http://ftp.cn.debian.org/debian
[/bash]
需要通过联网安装debian squeeze内核,该文件系统下载解压后只有200多兆,选择squeeze主要是为了和netkit-kernel兼容。
保存脚本文件,比如存为netkit-fs-build.sh,打开终端,cd到脚本文件所在目录下,使用命令:
[bash]
sudo sh netkit-fs-build.sh
[/bash]
运行脚本(注意使用root权限),即可得到基础的Linux文件系统了。

step2.修改文件系统为可用的Netkit文件系统:

1. 从Netkit原始文件系统中拷贝必要的文件,并修改netkit-phase1和netkit-phase2

上一步得到的文件系统,并不可以直接用于Netkit,启动虚拟机会失败,需要用到Netkit原始的文件系统中的部分文件进行补充,将其配置成可用的Netkit FileSystem。
所有需要添加到自制文件系统中的Netkit原始文件系统中的文件我们把他们放在了netkit-tweaks文件夹下,其目录结构如下,各自作用见注释:
[text]
netkit-tweaks
—- etc
———init.d #contains netkit-phase1 and netkit-phase2, the two important file for netkit bootstrap
———network #interfaces configure
———inittab # inittab file for bootstrap runlevel
———resolv.conf # DNS parse
———sysctl.conf # net.ipv4.ip_forward=1 for ip forwarding, important configure, enable ip packet forwarding
—–sbin
———mingetty # mingetty is a minimal getty program for watching virtual termianl
[/text]

该文件夹下所有的文件都可以在Netkit原始文件系统下找到,可以通过挂载原始文件系统把他们从挂载地址拷贝出来,其中/mnt/nkfs1为自定义的挂载地址:
[bash]
mount -o loop,offset=32768 netkit-fs-i386-F5.2 /mnt/nkfs1
[/bash]
文件netkit-phase1和netkit-phase2需要稍作修改, 修改netkit-phase1中开头部分为:
[bash]

BEGIN INIT INFO

Provides:

Required-Start:

Required-Stop: $all

Default-Start: 2 3 4 5

Default-Stop: 0 1 6

Short-Description:

Description:

END INIT INFO

[/bash]

修改netkit-phase2中开头部分为:
[bash]

BEGIN INIT INFO

Provides:

Required-Start: $all

Required-Stop:

Default-Start: 2 3 4 5

Default-Stop: 0 1 6

Short-Description:

Description:

END INIT INFO

[/bash]
$all的意思是最后,在netkit-phase1中表示最后停止,在netkit-phase2中表示最后开始,这是启动优先级的配置。
同时在netkit-phase2中,并将文件中/bin/sh -c ‘source /hostlab/$HOSTNAME.startup’这种类似的语句修改为”source /hostlab/$HOSTNAME.startup”。
因为用/bin/sh启动 startup脚本会会报”/bin/sh: source not found”的错误,默认用bash启动startup脚本就不会报错。
至此,所有需要添加进自制文件系统的文件已经全部在netkit-tweaks文件夹中了。

2. 拷贝必要的文件到文件系统中

首先挂载刚刚创建的文件系统netkit-fs-light:
[bash]
FS_NAME=netkit-fs-light
NETKIT_TWEAKS_DIR=netkit-tweaks
MOUNT_DIR=/mnt/nkfs2
mount -o loop,offset=512 -t ext2 $FS_NAME $MOUNT_DIR
[/bash]
下面需要把一些必要的文件拷贝到自制的文件系统中,其中**/etc/sysctl.conf**文件很重要,作用是将ipv4.ip_forward设为1,否则虚拟机无法ping通:
[bash]
cp -Rvf $NETKIT_TWEAKS_DIR/etc $MOUNT_DIR/
cp -Rvf $NETKIT_TWEAKS_DIR/sbin $MOUNT_DIR/
[/bash]

3. 改变root根目录位置,准备安装必要的工具和软件

改变root的执行程序参考的根目录位置至挂载文件系统的位置,方便我们直接配置文件系统和使用文件系统中的命令:
[bash]
chroot $MOUNT_DIR
[/bash]
挂载proc文件系统,proc文件系统是提供Linux内核数据结构接口的伪文件系统,文件系统并没有挂载proc文件系统,proc文件系统一般挂载在/proc目录下,如果没有挂载,虚拟机启动时会出现mtab无法初始化错误,也就是mtab文件会被损坏,因此我们为了让文件系统更完善,增加挂载proc文件系统的命令。
[bash]
mount -t proc none /proc
[/bash]

4. 安装必要的软件包

紧接着为文件系统更新和安装一些必要的工具和软件:
[bash]
apt-get update
apt-get install less
apt-get install vim
apt-get install chkconfig #为设置netkit-phase文件的启动优先级
[/bash]

5. 设置netkit-phase1和netkit-phase2脚本的启动优先级

在Debian 6.0之后,不能采用update-rc.d命令设置init.d目录下启动文件的优先级,采用insserv命令可以简单设置。我们尝试过将rcX.d文件从原始netkit文件系统中拷贝到新的文件系统中,发现不能使用,rcX.d这些链接文件是需要通过命令来生成的。在原始的netkit Makefile中采用update-rc.d设置是不成功的,采用insserv是我们做出的改进。
将netkit-phase1和netkit-phase2链接到rcX.d并设置优先级:
[bash]
insserv netkit-phase1
chkconfig netkit-phase1 on
insserv netkit-phase2
chkconfig netkit-phase2 on
[/bash]

6. 禁止不必要的启动项,取消挂载

取消cron job的启动项,加快启动
[bash]
update-rc.d cron remove
[/bash]
最后退出并取消挂载:
[bash]
exit # 退出新文件系统的根目录环境,回到ubunu根目录环境下
umount $MOUNT_DIR/proc
umount $MOUNT_DIR
[/bash]
如果因为设备正忙而无法取消挂载,可以察看相应进程,先杀死进程再取消挂载:
[bash]
fuser -m $MOUNT_DIR

if out put is /dev/sdc1: 538

ps -aux | grep 538

then kill the process by proccess id

[/bash]

step3.为文件系统安装quagga:

以上两步都是在Ubuntu主机下运行的,现在我们自制的Netkit FileSystem应该可以正常启动虚拟机了,最后一步需要启动虚拟机并在虚拟机内安装quagga。
首先启动Netkit虚拟机:
[bash]
FS_NAME=netkit-fs-light
vstart pc1 -m $FS_NAME -M 512 –eth0=tap,10.0.0.1,10.0.0.2 –append=rout:98:1 –W
[/bash]
该命令中参数解释如下:
–m $FS_NAME 表示以指定的文件系统作为虚拟机的文件系统
-M 512 指定内存512M,以为要联网安装,所以不能用默认的32M内存,太小
–eth0=tap,10.0.0.1,10.0.0.2 绑定eth0网卡到tap碰撞域,tap碰撞域是netkit保留的碰撞域,通过tap可以连接主机上外部因特网,10.0.0.1是TAP-ADDRESS是在Tap碰撞域中分配给主机Ubuntu的地址,10.0.0.2是GUEST-ADDRESS是分配给虚拟机的地址,此时可以ping任意的因特网,如baidu.com是可以成功的。
–append=rout:98:1 为netkit-kernel提供的参数
-W 表示对虚拟机的修改就是对Netkit文件系统的修改,不产生*.disk文件
启动后的虚拟机如图:
netkit
接下来在虚拟机中安装必要软件和工具:
[bash]
apt-get install telnet
apt-get install telnetd
apt-get install tcptraceroute
[/bash]
接着安装quagga,注意安装的quagga 版本为0.99.20.1,太高的版本可能会因为与内核版本不兼容:
[bash]
apt-cache policy quagga # 查看quagga可安装的版本,默认就有 0.99.20.1版本
apt-get install quagga -v 0.99.20.1
[/bash]
察看占用空间,最后退出虚拟机:
[bash]
dh -lf # 320M is the smallest solution, since up to now, 310M has been used
halt
[/bash]
至此,我们的文件系统就制作成功了,以上step2和step3的脚本,请参考configure-netkit.sh,我采用的是手工配置,一方面命令不多,另一方面手工配置可以保证每一步的正确性。通过查看文件系统的信息我们看到文件系统为335M左右。
使用这一自制文件系统,我们通过了rip, ospf single area, ospf multi area和simple bgp的网络实验测试。Netkit lab实验在官方网站中有详细的教程,在此就不详细描述实验了,能做出这个文件系统,我表示很欣慰,同时也学习到文件系统的制作是通过shell命令完成,开始以为需要C方面的知识。

遇到的问题

在实验中,遇到了很多问题,这些问题对定制该文件系统有很大价值,在此做一个记录和说明,如果遇到相似的问题,可以参考。

1. 虚拟机启动闪退

我们在做netkit文件系统时,有三个组员出现了启动虚拟机闪退的问题,我们为此花费了很多时间,的解决方法如下:
1.检查基础Linux文件系统是否安装成功,之前是因为文件系统的分区就没有创建成功,造成debootstrap也没有成功,文件没有安装好,启动闪退。
2.基础文件系统安装好了,拷贝了netkit-phaseX等文件后,启动虚拟机闪退,这是因为netkit-phaseX文件没有设置好优先级,需要在Ubuntu主机中通过insserv和chkconfig设置优先级。方可启动不闪退。

2. Quagga安装失败

我尝试过在Ubuntu中,通过chroot后,在文件系统中安装quagga,此时安装的quagga的版本不是0.99.20.1版,安装失败,之后又在虚拟机种通过手工编译安装quagga,依然失败。
最后的解决方法是,在虚拟机中,采用apt-get install quagga –v 0.99.20.1安装,-v指定版本,quagga的安装需要依赖netkit提供的内核,在ubuntu安装是没有netkit内核的,造成不能使用。

3. IP Forwarding问题

Quagga安装成功后,lab可以启动了,路由可以学习到路由,但是不能ping通,纠结一阵之后,我们发现是ip forward在Linux中默认关闭了,打开就可以。因此从原netkit文件系统中拷贝sysctl.conf文件,该文件可以永久设定net.ipv4.ip_forward=1,这样ip forward在启动时就已经打开,虚拟机之间就可以ping通了。

4. Fedora- x64下配置虚拟机和配更改文件系统的问题(from Aqua)

在Ubuntu系统中配置完成实验之后,我们尝试了在64位Fedora系统中配置Netkit虚拟机。由于Netkit是基于32位系统编译,所以要首先解决64位系统中的不同函数库的依赖问题。在Debian系统中,解决32位函数库依赖只需要apt-get ia32-libs即可。但是在Fedora的yum系统中,并不存在这个名称的包。经验证,如下命令解决问题。
[bash]
su -c ‘yum -y install –skip-broken glibc.i686 arts.i686 audiofile.i686 bzip2-libs.i686 cairo.i686 cyrus-sasl-lib.i686 dbus-libs.i686 directfb.i686 esound-libs.i686 fltk.i686 freeglut.i686 gtk2.i686 hal-libs.i686 imlib.i686 lcms-libs.i686 lesstif.i686 libacl.i686 libao.i686 libattr.i686 libcap.i686 libdrm.i686 libexif.i686 libgnomecanvas.i686 libICE.i686 libieee1284.i686 libsigc++20.i686 libSM.i686 libtool-ltdl.i686 libusb.i686 libwmf.i686 libwmf-lite.i686 libX11.i686 libXau.i686 libXaw.i686 libXcomposite.i686 libXdamage.i686 libXdmcp.i686 libXext.i686 libXfixes.i686 libxkbfile.i686 libxml2.i686 libXmu.i686 libXp.i686 libXpm.i686 libXScrnSaver.i686 libxslt.i686 libXt.i686 libXtst.i686 libXv.i686 libXxf86vm.i686 lzo.i686 mesa-libGL.i686 mesa-libGLU.i686 nas-libs.i686 nss_ldap.i686 cdk.i686 openldap.i686 pam.i686 popt.i686 pulseaudio-libs.i686 sane-backends-libs-gphoto2.i686 sane-backends-libs.i686 SDL.i686 svgalib.i686 unixODBC.i686 zlib.i686 compat-expat1.i686 compat-libstdc++-33.i686 openal-soft.i686 alsa-oss-libs.i686 redhat-lsb.i686 alsa-plugins-pulseaudio.i686 alsa-plugins-oss.i686 alsa-lib.i686 nspluginwrapper.i686 libXv.i686 libXScrnSaver.i686 qt.i686 qt-x11.i686 pulseaudio-libs.i686 pulseaudio-libs-glib2.i686 alsa-plugins-pulseaudio.i686’
[/bash]
这个长命令涵盖了ia32-libs中包含的所有依赖文件。
但是在生成文件系统过程中,由于Debian的Debootstrap并不能很好的兼容Fedora系统,导致生成文件系统失败。尚未找到更好的解决方案。
在Fedora下的尝试不成功,这也就是我们选取Ubuntu的原因,Netkit是32bitDebian系统,在32bitDebian系统下编译会更好。

参考资源

[1] Netkit官方网站
[2] Netkit官方FAQ
[3] Netkit 官方实验和介绍
[4] Netkit用户问答
[5] Debian内核release介绍
[6] An introduction to services, runlevels, and rc.d scripts
[7] Install quagga as linux router
[8] Quagga Tutorial for ip forwarding
[9] How to umount when device is busy

IPsec之IP层安全架构

什么是IPSec

IP层的安全架构由IPsec定义,IPsec(Internet Protocol Security), 是一个开放标准的框架,它是为IP层提供端到端的数据加密,数据完整性和数据认证的协议簇。

IPsec最早于1995年在RFC1825和RFC1829中定义,之后在1998年IETF又重新修改为RFC2401和RFC2412, 在RFC2401中引入秘钥交换协议(IKE)管理安全联盟(Security Association, SA), 而后在2005年,IETF又发布了新的文档定义RFC4301和RFC4309,引入IKEv2管理SA。本文即基于RFC4301来阐述IPsec的主要功能和工作机制。

IPsec的设计意图是为IPv4和IPv6提供安全保护,在RFC6434之前IPsec是必选内容,而对IPv4是可选的。IPv6的地址空间广阔,更有可能成为DDos, IP欺诈等网络攻击的目标,因此IETF旨在随着IPv6的发展,推广IPsec,提高IP层的安全性。

IPsec是OSI第三层协议,它可以为上层的基于TCP和UDP协议的数据流提供数据安全保护,如SSL不能保护UDP的通信流,就可以借助IPsec保护数据流。

IPsec可以在一个主机、网关或独立的设备中进行实现,从IP层提供高质量的安全服务,包括访问控制,无连接的完整性,数据源认证,重放攻击检测和拒绝和数据加密等.

IPsec定义了IPsec作为一个IP层防火墙所需的最小功能集。IPsec进行访问控制的规则主要定义在安全规则数据库中(Security Policy Database, SPD),IPsec根据这些规则对数据包进行保护、丢弃或通过的处理。[more…]

IPsec安全功能组成

总体来说IPsec的安全功能由两个安全协议(AH和ESP)和建立安全联盟的协议(IKE)组成。

1. 两种安全协议

包括认证头协议(Authentication Header,AH)和封装安全载荷协议(Encapsulating Security Payload, ESP)。

AH,提供数据完整性,反重放攻击和可选的数据源认证的安全特性。通常使用单向Hash函数的摘要算法——MD5和SHA1实现其安全特性。

ESP,可以同时提供数据完整性,数据加密,反重放攻击等安全特性。通常使用DES,3DES和AES等加密算法来进行数据加密。使用MD5和SHA1实现数据认证。

AH和ESP都采用SPD来提供访问控制。IPsec要求一定要实现ESP,AH可选,一般ESP就可以满足大部分的安全需求.

AH在实践中用的少,其原因有二:第一,没有数据加密,数据是以明文传输,而ESP提供数据加密。第二,AH提供数据源认证,一旦数据源地址发生改变,校验失败,所以AH不能穿越NAT。但是在PC到PC的通信中,采用AH更好,因为ESP的开销较大。

2. 建立安全联盟的协议

Internet Key Exchange, IKE是用于建立和维护SA的协议,在端到端之间进行协商,确认通信端的身份,建立安全的通信关联。

在1998年RFC2401中第一次在IPsec中引入IKE,8年后RFC4301中更新为IKEv2,RFC4301中采用的是IKEv2。IKEv1和IKEv2的主要区别是:

  • IKEv2比IKEv1消耗的带宽更少。
  • IKEv2支持扩展认证头协议(Extensible Authentication Protocol, EAP), 而IKEv1不支持,IKEv2对无线的支持更好。
  • IKEv2支持MOBIKE,而IKEv1不支持,IKEv2可以提供移动通信支持。
  • IKEv2内内嵌支持NAT,而IKEv1不支持。
  • IKEv2可以检测隧道是否alive,但IKEv2不支持。
  • IKEv2的引入可以在建立安全关联时,提供更好的安全特性。

IPsec数据处理模型

1.1Top Level IPsec Processing Model

Psec在数据处理时,在保护接口(Protected Interface)和非保护接口(Unprotected Interface)之间创建了一个分界(Boundary)。数据从非保护接口进入,IPsec会基于AH或ESP进行访问控制,对数据的处理结果有三种:保护(Protected), 丢弃(Discard), 通过(Bypass)。

IPsec对IP数据包处理有两种情况:

Inbound,即IP输入,数据从非保护接口端进入穿过IPsec,从保护接口端输出。

Outbound, 即IP输出, 数据从保护接口端进入,从非保护接口端输出。

IPsec两种封装模式和应用场景

IPsec的一个重要应用场景就是VPN。
1.2IPsec VPN应用场景

如图上图所示,企业的各个内网间通过隧道连接,而隧道模式是IPsec重要的应用模式。

IPsec提供两种封装模式,传输模式和隧道模式,主要分为四种场景:

1.3IPsec四种应用场景

1. Gateway-to-Gateway网关到网关,如上图的A场景,Alice的PC要访问公司HR的服务器,需要通过隧道模式进行安全连接,该隧道就是建立在两个网关之间。这是通常的VPN的场景。

2. End-to-Gateway端到网关,如图中的B场景,从Alice的PC端连接到另一个IPsec网关,这也是在隧道模式下。

3. End-to-End端到端,如图中的C场景,采用隧道模式一个Cisco路由器和PIX防火墙通过隧道模式连接。

4. 传输模式,如图中的D场景传输模式,IPsec传输模式一般用于端到端的情况,或者端到网关,此时网关被当作一个主机。D场景中Alice PC用传输模式连接PIX防火墙,对防火墙进行管理。

可以发现,IPsec的传输模式和隧道模式的区别:

传输模式一般只用于端到端的情况,如PC-to-PC。传输模式下,AH,ESP不对IP头进行修改和加密。

隧道模式可以用于任何一种场景,多用于网关到网关的场景,但是隧道模式下,AH,ESP会在源IP报文前面添加外网IP头,隧道模式会多一层IP头的开销,在端到端的模式中,建议使用传输模式。

IPsec重要加密和认证算法

IPsec为了保证数据的完整性,实现数据的认证和加密,相关算法有:
数据加密算法:

  • DES,基于共享秘钥进行数据加密和解密,采用56bit的秘钥保证加密的性能。
  • 3DES,与DES相似,提供数据加密和解密,采用变长的秘钥。
  • Diffie-Hellman(D-H): 这是一个公钥加密协议。它可以在通信的两端基于MD5或DES算法建立共享秘钥,实现安全通信。D-H主要用于IKE,建立安全session会话。秘钥一般为768bit或1024bit。
  • RSA,基于公钥的加密,来实现数据认证,例如在Cisco的路由上的IPsec采用D-H交换来决定两端的私钥,并生成共享秘钥,采用RSA签名进行公钥认证。

数据认证算法:

  • Message Digest 5(MD5): 是一个Hash算法,用于数据包验证。这是一个单向的加密算法,IKE,AH和ESP中采用MD5进行数据认证,防止重放攻击。
  • Secure Hash Algorithm(SHA-1): 是一个Hash算法,用于数据包验证。IKE,AH和ESP中采用MD5进行数据认证,防止重放攻击。

IPsec安全协议之AH认证头协议

AH协议主要用于保护传输分组的数据完整性,并可以进行数据源认证。它采用滑动窗口和丢弃旧数据包的技术来防止重放攻击。但是AH不提供数据加密。

在IPv4和IPv6中,AH试图保护所有的IP头字段,除了TTL,ECN, Flags等可变字段。

2.1AH的两种数据封装模式

如图,AH提供两种封装模式,传输模式和隧道模式。

传输模式下,AH采用单向Hash算法,对IP头和数据载荷进行摘要,形成AH头部,AH头部放在IP头部和数据之间。在AH处理前后IP头部不发生变化。

隧道模式下,AH对原IP头进行Hash摘要,生成新的IP头。摘要生成的头被放于新的IP头之后,原IP头之前。

AH不能通过NAT,因为NAT会改变源IP地址,破坏AH头部,造成包被IPsec另一端拒绝。

2.2AH头部字段

如所示是AH的头部字段,包括:

下一个头(Next Header):8bit,标识被传输的IP报文采用的是什么协议,如TCP或UDP。

载荷长度(Payload Len):8bit认证包头的大小。

保留字段:16bit为将来应用做保留,目前都置0。

安全参数索引(SPI): 32bit与目的IP地址一起来标识与接收方的安全关联。

序列号(Sequence Number):32bit,单调增值的序列号,防止重放攻击。

完整性检查值(Integrity Check Value, ICV): 变长字段,一般32bit的倍数,包含认证当前包所必须的数据。

IPsec安全协议之ESP封装安全载荷协议

ESP协议为IPsec提供数据源认证,数据完整性和数据加密功能。与AH不同的是在传输模式下,ESP不提供对整个IP数据包的数据完整性和认证功能,只对IP数据载荷进行加密和认证。然而在传输模式下,提供对整个IP包的加密和认证,生成新的包头。

2.3ESP的两种封装模式

如图是ESP的两种封装模式。

传输模式下,ESP只对上层协议数据加密,不加密IP头,只对ESP头和加密的上层协议数据进行认证,不认证IP头,生成的新IP报文,IP头不变,ESP头和加密的数据放在IP头之后。

隧道模式下,ESP对整个IP头和上层协议数据加密,对ESP头和加密数据进行认证,生成新的IP头,包括外部IP源、目的地址。但新的IP头不参与认证。

在ESP加密和认证中,总是先对数据加密再HASH认证,这样可以让接收端在解密之前,对数据包进行快速检测,防止重放攻击。

2.4ESP的头部字段

如图2.4,是ESP定义的头部字段:

安全参数索引(SPI): 32bit与目的IP地址一起来标识与接收方的安全关联。

序列号(Sequence Number):32bit,单调增值的序列号,防止重放攻击。

载荷数据(Payload Data): 变长,受保护的IP数据,其数据内容由下一个头字段标识。

填充(Padding):一些加密算法用此字段将数据填充至块的长度,和下一字段对齐。

填充长度:8bit,标识填充字段的长度。

下一个头(Next Header): 标识被传输数据所用的上层协议。

完整性检查值(Integrity Check Value, ICV): 变长字段,一般32bit的倍数,包含认证当前包所必须的数据。

SA安全联盟

安全联盟(Security Association, SA也有翻译为安全关联、安全连接),是IPsec中的重要概念。在IPsec发送端和接收端进行安全通信之前,IPsec需要通过SA建立安全关联来确定如何建立安全通信。

IPsec为安全通信提供数据加密,数据完整性和认证这三种服务,当服务的类型确立后,通信的两端需要确立采用什么加密(DES或3DES)和认证(MD5或SHA-1)算法, 再决定算法后又需要交换session秘钥。可以对于一个安全通信会话,需要交换很多信息,所以引进SA的概念来管理安全通信参数和算法等信息。

总之,SA就是IPsec进行安全通信的一簇算法和安全参数,如封装模式,发送方和接收方的IP地址,兴趣流等,这些参数被用于加密和认证。

SA是单向的,通信的两端如果要双向通信,则需要建立一对SA,这样当任何一方的SA被破解,另一方的SA不会受影响。

3.1SA的结构示例

如图是一个SA的结构示例,包括:

目的地址

安全参数索引(SPI): 每一个通信端都有唯一的SPI,IPsec将基于SPI,源地址和目的地址在SAD数据库中搜索安全参数记录。

IPsec安全协议

秘钥

其他的SA属性,如IPsec Lifetime

3.2SA的工作机制

如图所示,是一个在具体通信中路由器R1和R2的IPsec SA参数,可以看到SA是单向的,从任何一方到另一方都要建立SA。当一个数据包需要IPsec保护,首先它会查询SAD数据库(安全关联数据库),将SA中的SPI插入到IPsec的头部,当接收端收到数据包后,接收端会根据目的地址和SPI在自己的SAD中找到相应的SA, 如果SA匹配,则进一步采用AH或ESP对数据包进行处理。

3.3不同通信端的不同SA

如图所示,是在一个网络中,不同的主机间的通信采用了不同IPsec安全参数,从Client到Router A采用传输模式ESP,Router A到Router B采用隧道模式AH,这些安全参数都需要SA来管理。

SA如何判断网关的安全性—-IKE

SA是安全连接,而如何建立安全连接呢?如何确定网关的安全信呢?需要因特网秘钥交换(Internet Key Exchange)协议,IKE旨在对IPsec通信的两端进行安全会话秘钥交换,建立和维护SA。

IKE的具体工作机制在RFC2409中定义,而在RFC2401中使用的IKEv2在RFC4306中有定义。

IPsec重要数据库

  1. Security Policy Database (SPD)

    SA是管理安全通信的参数,但不管理具体的数据包的处理,对每一个IP数据包采取什么样的安全服务,如何进行访问控制,需要这些访问控制的信息就存储在安全规则数据库SPD中。

    每一个IPsec至少要实现一个SPD,SPD是一个有序数据库,它存储访问控制列表(Access Control List, ACL),防火墙或路由的包过滤规则等。

    SPD中的记录,对数据的处理有三种选择:丢弃(Discard),通过(Bypass)和保护(Protect)。

    SPD在逻辑上被分为三部分:

    SPD-I:包括对于inbound的数据包,需要采取丢弃和通过的规则。

    SPI-S:包括需要对数据进行保护的规则。

    SPI-O:包括对于outbound的数据包,需要采取丢弃和通过的规则。

  2. Security Association Database (SAD)

    SA安全管理的相关信息,需要存储在SAD中,SAD是一个概念上的数据库,只是以某种列表的数据结构来存储SA。
    每一个实体定义了SA的安全参数。对于Outbound的数据包,SAD的实体指向SPD缓存中的SPD-S部分。对于Inbound的数据包,只通过SPI或IPsec协议来查找SA。

    具体的结构SA实体结构参见前面给出的示例.

  3. Peer Authorization Database (PAD)

    PAD,端认证数据库,提供SA管理协议,如IKE与SPD的之间的管理。有时候SA发生变化,SPD就地不到及时更新,此时就需要借助PAD对SA和SPD做出调整。

    PAD是一个有序数据库,它建立了IKE ID和SPD实体的关联。PAD支持6种ID类型:

    DNS Name

    Distinguished Name

    Email Address

    IPv4 Address

    IPv6 Address

    Key ID

    PAD的相关工作机制是:

    在IKE SA建立时,发送方和接受方都会通过IKE ID进行身份确认,确认之后向对方发送认证信息。当一个IKE信息收到后,便会通过IKE ID在PAD数据库中找到匹配的实体,每一个PAD实体都记录了进行身份认证的方法,它可以保证对不同的通信端采用正确的身份认证。

IPsec的工作机制

5.1IPsec工作机制

如图5.1所示,IPsec的工作流程可以分为5个阶段:

1. 决定兴趣流

IPsec对IP包的保护是需要消耗资源的,并非所有的流量都需要IPsec保护,那些需要IPsec保护的数据流就叫做兴趣流,IPsec会对兴趣流进行访问控制。
如发起方的兴趣流式192.168.1.0/24 -> 10.0.0.0/8,接收方的兴趣流是10.0.0.0/8->192.168.1.0/30,那么取交集,兴趣流IPsec保护的兴趣流就是192.168.1.0/30 <-> 10.0.0.0/8

IPsec通信开始时,发送方如图5.1的Router A要将兴趣流发送给接收方Router B。

2.IKE 第一步

对IPsec的通信端进行身份认证,协商并建立IKE SA。这一步建立的是IKE安全连接,通过Diffie-Hellman算法交换共享秘钥,为IKE第二步通信建立安全隧道。

3.IKE第二步

IKE第二步,主要是建立IPsec SA,在IKE第一步建立的IKE SA的基础上协商并建立IPSec SA。周期性的协商,保证SA的安全性,可选采用Diffie-Hellman交换算法。

4.IPsec数据传输

在IPsec安全隧道建立后,采用IPsec SA确立安全参数,秘钥,进行数据通信。

5.IPsec会话停止

IPsec SA通过检测和超时来停止会话,在SA停止IPsec后,如果还需要数据传输,则需要重新进入IKE第一步或IKE第二步重新协商建立新的SA。

References

RFC4301

Cisco IPsec Overview

技术点详解—IPSec VPN基本原理

如何配置VPS并发布WordPress Blog?(第一篇)

最近将VPS放到digitalocean上, 因为之前的VPS被关停了,所以再找一个, 相信这次会稳定了,之前的服务器是CentOS5.9,而现在的版本是CentOS7,以下的一些配置可能不正确了,可以参考这个链接LAMP with Centos 7.0

目标

发布个人的WordPress博客网站,配置LAMP环境,并用GitHub来发布Blog,不用FTP,会很慢。
[more…]

连接VPS

我在Mac下,所以很方便的连上VPS, 为了方便管理直接用root登陆, 第一次配置安全性先不考虑,用root方便些
[bash]
ssh -l root ip.address
[/bash]
如果在Windows下,下载一个putty就可以很方便的连上VPS,SSH端口是22,VPS默认可以用SSH连接。

有用的命令

[bash]
cat /etc/release #查看Linux的版本
uname -a # 查看内核的版本
ifconfig -a # 查看网卡情况
nman localhost # 查看端口的情况
iptables -vL # 查看防火墙的情况
netstat -aln | grep 80 # 查看网络连接情况
init 6 # 重启
passwd # 修改当前用户的密码,可以该root密码
[/bash]

Linux running level

Linux下的运行级别,一个常识

0 – halt

1 – Single user mode

2 – Multiuser, without NFS

3 – Full multiuser mode

4 – unused

5 – X11

6 – reboot

[bash]
init running-level # 触发运行级别,关机,重启各种方便
[/bash]

关闭selinux

selinux经常捣乱,先把它关了,还要永久关
[bash]
getenforce # 查看selinux的状态
sestatus # 一样,查看selinux状态
vim /etc/sysconfig/selinux # 将SELINUX 改为disabled状态,然后重启
setenforce 0 # 只能暂时改变selinux状态,不能永久更改,只有上面的方法可以
init 6 # 重启
[/bash]

这个在DigitalOcean的镜像中不需要配置.

安装Apache

[bash]
yum -y install httpd
chkconfig –levels 235 httpd on # 将httpd进程设置为开机启动
service httpd start # 此时可以用ip访问VPS,如http://129.29.10.10,如果可以访问便安装成功
[/bash]
Apache在CentOS的DocumentRoot是“/var/www/html”, 配置文件在”/etc/httpd/config/httpd.conf”

无奈,第一个问题遇到了,我的Apache访问不了,纠结半天,原来是防火墙iptables的问题。

打开防火墙

CentOS的iptables默认只让注册过的端口通过,而80端口没有注册过,不能通过防火墙。
[bash]
vim /etc/sysconfig/iptables

将 “-A RH-Firewall-1-INPUT -j REJECT –reject-with icmp-host-prohibited” 这行注释了,保存退出

service iptables restart
[/bash]
BTW,如果采用以下的方法enable 80 端口,我今天成功了, 以前没有成功不知为何,不过上面的方法是肯定好的,下面的方法是一个安全点的办法。
[bash]
iptables -A INPUT -p tcp –dport 80 -j ACCEPT
iptables -A INPUT -p tcp –dport 443 -j ACCEPT // 添加443 SSL端口未来会用
service iptables save // /etc/sysconfig/iptables 文件会被重写
service iptables restart
[/bash]
此时再访问http://youripaddress就会有apache界面了。

在DigitalOcean中,不需要配置本项.

安装MySQL

[bash]
yum install -y mysql mysql-server
chkconfig –levels 235 mysqld on
service mysqld start
mysql_secure_installation // 设置root密码,我这次谨慎了一下,没有全部选yes,大家看情况,记住自己的root密码
mysql -uroot -p // 进入MySQL,看看玩玩
[/bash]

在DigitalOcean中安装的是MariaDB, 兼容MySQL, 具体看参考链接.LAMP with Centos 7.0

安装PHP

我被坑过,CentOS 5.9的yum的默认包库中PHP是5.1.6,后来WordPress跑不了(至少5.2.4),所以需要更新一下yum。

如果想了解更详细的信息,可以看看这个链接
Install Apache, MySQL 5.5.32 & PHP 5.5.0 on RHEL/CentOS 6.4/5.9 & Fedora 19-12
[bash]
yum info name of module # 查看某个包的信息
rpm -Uvh http://dl.fedoraproject.org/pub/epel/5/i386/epel-release-5-4.noarch.rpm
rpm -Uvh http://rpms.famillecollet.com/enterprise/remi-release-5.rpm
yum –enablerepo=remi,remi-test install -y php php-common
yum –enablerepo=remi,remi-test install php-mysql php-pgsql php-pecl-mongo php-sqlite php-pecl-memcache php-pecl-memcached php-gd php-mbstring php-mcrypt php-xml php-pecl-apc php-cli php-pear php-pdo # 安装PHP会用到的module
service httpd restart
vim /var/www/html/phpinfo.php
[/bash]
输入:
[php]
<?php
phpinfo();
?>
[/php]
再访问http://ipaddress/phpinfo.php, 查看php的状态

VPS DNS解析

有了VPS,再买一个域名吧,我在godaddy上买了一个域名,用DNSPod来解析,国内的DNS解析,会快一些。

需要在godaddy上将NameServer更改为:

[text]
F1G1NS1.DNSPOD.NET
F1G1NS2.DNSPOD.NET
[/text]
再到DNSpod上注册,填写IP,等信息,就能简单完成DNS解析,从此以后就可以用域名访问VPS了。

本章结束

OKay, that’s it! LAMP环境安装好了,一切就绪,坐等发布WordPress了,请看如何配置VPS并发布WordPress Blog?(第二篇)