（通信与信息系统专业论文）高速网络qos路由技术的研究及路由仿真平台的研制.pdf

华 中 科 技 大 学 博 士 学 位 论 文 触合遗传算法和启发式搜索思想，提出了 “ 启发式遗传算法” 。 研究了d c l c m r问 压和一般网 络模型下q o s组播路由 和q o s单播 于启发式遗传策略， 由问题，并分别提出 7 d c l c m r - h g a . q o s m r - h g 和q o s u r - h g 算 法. 研究7 启 发 式 遗传 算 法的 终 止 策 略， 提出 了 静 态终 止 算法 遗 传 代数限 定 法 和 动 态 算 法 费 用 代 沟限 定 法. 入 针对q o s 单播路由问 题， 提出了 一种分布式动态路由 策略， 研究了d c l c u r问 题的分 布式动态路由 算法d c l c - d s f ，给出了d c l c - d s f 算法的有限 状态机模型. 针对q o s 组播 路由问鹿，提出了 支持动态组播成员的分布式动态组播路由 策略， 研究了d c l c m r问 题的 分布式动态组播路由算法d d d c l c m r .分析了d d d c l c mr算法的加入结点选择策略，提 山了随机点策略r c n a 、最小延时点策略l d c n a和最小费用点策略l c c n a . 研究了q o s组播路由 算法中 环路形成的机理. 提出了消除环路的小延时 路径保留 算法 p s dra. 利用路由仿真平台 n r s ，将论文中提出的各种路由算法都与当前己有的相关算法进行 了比较实验研究。 关妞词:服务质f.算法， 仿真，启发式 单播路由 飞组播路由，源路由，分布式路由户动态路由， 一 1 1一 华 中 科 技 大 学 博 士 学 位 论 文 ab s t r a c t t h e r a p i d d e v e l o p m e n t a n d d e p l o y m e n t o f r e a l - t i m e m u l t i m e d i a a p p l i c a t i o n s i n h i g h - s p e e d n e t w o r k s i n r e c e n t y e a r s h a v e r a i s e d n e w c h a l l e n g e s f o r t h e t r a d i t i o n a l c o m p u t e r n e t w o r k s , w h i c h o n l y s u p p o rt b e s t - e f f o rt a p p l i c a t i o n s . o n e o f t h e k e y i s s u e s i s q o s ( q u a l i t y o f s e rv i c e ) r o u t i n g , w h i c h a l l o w s s e l e c t i n g n e t w o r k r o u t e s w i t h s u f f i c i e n t r e s o u r c e s f o r t h e r e q u e s t e d q o s p a r a m e t e r s . i n c o m p a r i s o n w i t h b e s t - e f f o r t r o u t i n g , q o s r o u t i n g i s c o n n e c t i o n - o r i e n t e d a n d m o s t l y i s n p - c o m p l e t e . q o s r o u t i n g s u p p o rt s t r a f f i c u s i n g v a r i o u s s e rv i c e s w i t h s e v e r a l q o s r e q u i r e m e n t s . q o s r o u t i n g a l s o p r o v i d e s s u p p o rt f o r a l t e r n a t e r o u t i n g . i f t h e b e s t e x i s t i n g p a t h c a n n o t a d m i t a n e w f l o w , t h e a s s o c i a t e d t r a f f i c c a n b e f o r w a r d e d i n a n a d e q u a t e a l t e r n a t e p a t h m a n y u n i c a s t / m u l t i c a s t q o s r o u t i n g a l g o r i t h m s w e r e p u b l i s h e d r e c e n t l y . h o w e v e r , t h e r e s t i l l e x i s t a l o t o f u n s o l v e d p r o b l e m s d u e t o t h e n p - h a r d p r o p e rt i e s o f m o s t q o s r o u t i n g p r o b l e m s . a f e w e x a m p l e s a r e l i s t e d a s f o l l o w s . ( 1 ) n e a r l y a l l e x i s t e d a l g o r i t h m s a r e t a i l o r e d t o w a r d s s p e c i fi c p r o b l e m s , a n d t h e r e l a c k s a s i m p l e , g e n e r a l r o u t i n g f r a m e w o r k w h i c h c a n b e e a s i l y e x t e n d e d t o o t h e r p r o b l e m s . ( 2 ) ma n y e x i s t e d a l g o r i t h m s a r e r e s t r i c t e d t o s p e c i f i c n e t w o r k e n v i r o n m e n t s , a n d t h e y m o s t l y c a n n o t c o m p u t e r o u t e s i n r e a l t i m e a n d h a v e p o o r d y n a m i c c h a r a c t e r i s t i c s . ( 3 ) r e s e a r c h f o r q o s r o u t i n g a r e m o s t l y b a s e d o n t r a d i t i o n a l m e t h o d s , a n d t h e r e l a c k n e w a p p r o a c h e s t o q o s r o u t i n g c o m p u t a t i o n . i n o r d e r t o s o l v e t h e p r o b l e m s m e n t i o n e d a b o v e , r e s e a r c h p r o j e c t s t u d y o n q o s r o u t i n g a l g o r i t h m i n h i g h - s p e e d n e t w o r k s a n d d e v e l o p m e n t o f r o u t i n g s i m u l a t i o n p l a t f o r m i s p r o p o s e d . s e v e r a l q o s r o u t i n g s t r a t e g i e s a n d t h e o p e n s y s t e m f r a m e w o r k f o r t h e q o s r o u t i n g s i m u l a t o r a r e p r e s e n t e d a n d d e e p l y s t u d i e d i n t h i s d i s s e r t a t i o n . a t f i r s t , t h e r e s e a r c h a n d d e v e l o p i n g c o n d i t i o n o f t h e r o u t i n g s i m u l a t o r i s r e v i e w e d s y s t e m a t i c a l l y . t h e i d e a o f o p e n s y s t e m f r a m e w o r k f o r r o u t i n g s i m u l a t o r a n d t h e n e w c o n c e p t o f c u s t o m i z e d r o u t i n g s i m u l a t i o n a r e p r o p o s e d . t h e b a s i c c h a r a c t e r i s t i c a n d s o f t w a r e s t r u c t u r e o f t h e o p e n r o u t i n g s i m u l a t i o n s y s t e m a r e a n a l y z e d , a s w e l l a s t h e n e t w o r k r o u t i n g s y s t e m ( n r s ) i s d e v e l o p e d . t h e r a n d o m n e t w o r k t o p o l o g y g e n e r a t i o n a l g o r i t h m ( r n t g a ) i s s t u d i e d a n d p r e s e n t e d . t h e o u t p u t o f t h i s r a n d o m g e n e r a t o r i s a l w a y s a c o n n e c t e d n e t w o r k i n w h i c h e a c h n o d e s d e g r e e i s g r e a t e r t h a n 2 a n d a v e r a g e n o d e d e g r e e i s e q u a l t o 4 . g r e e d y h e u r i s t i c i s p r o p o s e d b y i n t e g r a t i n g t h e g r e e d y a l g o r i t h m a n d h e u r i s t i c a l g o r i t h m . b a s e d o n g r e e d y h e u r i s t i c , t h e s e l e c t i o n f u n c t i o n a l g o r i t h m a s w e l l a s o n e o f i t s i m p l e m e n t a t i o n一 i i i 华 中 科 技 大 学 博 士 学 位 论 文 l i n k j u d g e m e n t f u n c t i o n a n d n o d e s e l e c t i o n f u n c t i o n i s p r o v i d e d . t h e l i n e a r a n d n o n - l i n e a r w e i g h e d s t r a t e g i e s f o r t h e j u d g e m e n t f u n c t i o n a r e a n a l y z e d . b a s e d o n n o n - l i n e a r w e i g h e d s t r a t e g y , d c l c - s f ( d e l a y - c o n s t r a i n e d l e a s t - c o s t r o u t i n g b a s e d o n s e l e c t i o n f u n c t i o n ) f o r d e l a y - c o n s t r a i n e d l e a s t - c o s t u n i c a s t r o u t i n g p r o b l e m ( d c l c u r ) i s p ro p o s e d . s e l e c t i o n f u n c t i o n a l g o r i t h m s f o r t h e o t h e r q o s u n i c a s t r o u t i n g p r o b l e m s , s u c h a s d c c u r a n d b d c l c u r , a r e a l s o d i s c u s s e d i n t h i s d i s s e rt a t i o n . e x t e n d e d m e c h a n i s m s o f q o s u n i c a s t r o u t i n g i n q o s m u l t i c a s t r o u t i n g p r o b l e m a r e s t u d i e d t h o r o u g h l y . n s l a - d c l c m r ( n o n - s h a r e d l i n k a l g o r i t h m f o r d e l a y - c o n s t r a i n e d l e a s t - c o s t mu l t i c a s t r o u t i n g ) b a s e d o n n o n - s h a r e d l i n k a n d s l a - d c l c mr ( s h a r e d l i n k a l g o r i t h m f o r d e l a y - c o n s t r a i n e d l e a s t - c o s t mu l t i c a s t r o u t i n g ) b a s e d o n s h a r e d l i n k a r e p r e s e n t e d . b a s e d o n s l a - d c l c mr a n d d d a ( d e s t i n a t i o n d r i v e a l g o r i t h m ) , s l a - d c l c mr - s n ( s h a r e d l i n k a l g o r i t h m f o r d e l a y - c o n s t r a i n e d l e a s t - c o s t m u l t i c a s t r o u t i n g i n s y m m e t r y n e t w o r k s ) f o r s y m m e t r y n e t w o r k s a n d s l a - d c l c m r - a n ( s h a r e d l i n k a l g o r i t h m f o r d e l a y - c o n s t r a i n e d l e a s t - c o s t m u l t i c a s t r o u t i n g i n a s y m m e t r y n e t w o r k s ) f o r a s y m m e t ry n e t w o r k s a r e p r o p o s e d . d y n a m i c e x t e n d e d m e c h a n i s m f o r q o s m u l t i c a s t r o u t i n g i s a l s o s t u d i e d . i n a d d i t i o n , d y n a m i c a l g o r i t h m f a m i l y d d c l c mr ( d y n a m i c d e l a y - c o n s t r a i n e d l e a s t - c o s t mu l t i c a s t r o u t i n g ) b a s e d o n s o u r c e r o u t i n g s t r a t e g y f o r d c l c mr p r o b l e m i s p r o p o s e d . i n t e g r a t i n g g e n e t i c a l g o r i t h m a n d h e u r i s t i c a l g o r i t h m , h e u r i s t i c g e n e t i c a l g o r i t h m i s p r o p o s e d . b a s e d o n h e u r i s t i c g e n e t i c a l g o r i t h m , d c l c mr p r o b l e m i n s i m p l i f i e d n e t w o r k m o d e l a n d q o s u n i c a s t / m u l t i c a s t r o u t i n g p r o b l e m i n g e n e r a l n e t w o r k m o d e l a r e s t u d i e d . a c c o r d i n g l y , d c l c m r - h g a , q o s mr - h g a a n d q o s u r - h g a a l g o r i t h m s a r e p r o p o s e d . t h e s t o p s t r a t e g y o f t h e h e u r i s t i c a l g o r i t h m i s s t u d i e d , a s w e l l a s , t h e s t a t i c s t o p a l g o r i t h m一 g e n e r a t i o n r e s t r i c t i o n a l g o r i t h m a n d d y n a m i c s t o p a l g o r i t h m一 c o s t g e n e r a t i o n g a p r e s t r i c t i o n a l g o r i t h m a r e p r o p o s e d . a d i s t r i b u t e d d y n a m i c u n i c a s t r o u t i n g m e c h a n i s m f o r q o s u n i c a s t r o u t i n g p r o b l e m i s p r e s e n t e d . d c l c - d s f ( d e l a y - c o n s t r a i n e d l e a s t - c o s t u n i c a s t r o u t i n g b a s e d o n d i s t r i b u t e d s e l e c t i o n f u n c t i o n ) f o r d c l c u r p r o b l e m a n d t h e l i m i t e d s t a t e m a c h i n e f o r d c l c - d s f a r e g i v e n i n t h i s d i s s e rt a t i o n . a d i s t r i b u t e d d y n a m i c m u l t i c a s t r o u t i n g s t r a t e g y f o r s u p p o rt i n g d y n a m i c m u l t i c a s t m e m b e r i n q o s m u l t i c a s t r o u t i n g p r o b l e m . t h e d i s t r i b u t e d d y n a m i c m u l t i c a s t r o u t i n g a l g o r i t h m d d d c l c m r ( d i s t r i b u t e d d y n a m i c d e l a y - c o n s t r a i n e d l e a s t - c o s t mu l t i c a s t r o u t i n g ) f o r d c l c m r p r o b l e m i s s t u d i e d . t h e c o n t a c t e d n o d e s e l e c t i o n m e c h a n i s m f o r d d d c l c m r i s s t u d i e d , c o r r e s p o n d i n g l y , r c n a ( r a n d o m c o n t a c t e d n o d e a l g o r i t h m ) , l d c n a ( l e a s t d e l a y 一 奋 v 一 华 中 科 技 大 学 博 士 学 位 论 文 c o n t a c t e d n o d e a l g o r i t h m ) , a n d l c c n a ( l e a s t c o s t c o n t a c t e d n o d e a l g o r i t h m ) a r e p r o p o s e d . t h e c a u s e o f l o o p s f o r m e d i n q o s m u l t i c a s t r o u t i n g i s t h o r o u g h l y s t u d i e d a n d p s d r a ( p a t h w i t h s m a l l e r d e l a y r e s e rv e d a l g o r i t h m ) i s p r o p o s e d . e x t e n s i v e s i m u l a t i o n e x p e r i m e n t s a r e c o n d u c t e d t o e v a l u a t e a n d c o m p a r e p e r f o r m a n c e s o f t h e p r o p o s e d a l g o r i t h m s a n d t h e e x i s t i n g r e l a t e d a l g o r i t h m s . k e y wo r d s : rou t i n g , d i s t r i b u t e d q u a l i t y o f s e r v i c e , a l g o r i t h m , u n i c a s t r o u t i n g , m u l t i c a s t r o u t i n g , s o u r c e r o u t i n g , d y n a m i c r o u t i n g , s i m u l a t i o n , h e u r i s t i c ， 一一-一 一 钾 . - . 一一 . 一 - 一 - 钾 钾 ， ， ， 一 一 币 ， ， ， ， ， 户 一 v 一 华 中 科 技 大 学 博 士 学 位 论 文 图 表 索 引 图1 . 1 图1 . 2 图2 . 1 图2 . 2 图2 . 3 图2 . 4 图2 . 5 图3 . 1 图3 . 2 图3 . 3 图3 . 4 图3 . 5 图3 . 6 图3 . 7 图3 . 8 图3 . 9 图3 . 1 0 图3 . 1 1 图3 . 1 2 图3 . 1 3 图3 . 1 4 图4 . 1 q o s 单 播 路由 问 题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 q o s 组播 路由 问 题 . “ . “ ” - “ “ . . .-. . ” “ ” . “ ” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 n r s 软件总体框图” ” :. “ .” ” :. ” . ” .” ” . “ “ . ” . “ “ ” . ” “ ” “ ” ” ” “ “ ” ” “ ” ” 一3 0 n r s 软 件 系 统 的 主 界 面.” . “ . ” ” 二 “ ” ” ” ” . “ . “ . ” . ” ” ” “ ” ” ” ” ” “ ” “ “ ” ” ” ” ” . 3 1 4 。 个结点的随 机网 络拓扑实 例. “ ”“ 二 ” 二 ” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 路由 仿 真 模 块 逻 辑 框图 . . . . . . . . . . . . . 一“ . ” -. .- . . ” . . . . . . . . . . . . . . . . . . . . . . . . 一 3 3 d d c l c mr 算法仿真结果示例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 一. . . 3 5 线性加权函数与非线性加权函数特性比 较. ” -. . “ “ . . “ . “ “ ” . “ 一，. . . . . . . . . . . . . . . . . . . 3 8 三角路由问 题示例. ” ” . ” . .- 一 ” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1 三角路由实例二 价 . . ” . “ . . . . . ” . . . - . . . ” . . . . . “ . ” . . . - . “ ” “ ” ” ” ” “ 引 d c l c - s f 算法查找路径示例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 d , f 被路径( a - + b - + e ) 分割实例. ” . . .” ” ” .“ ” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 n s l a - d c l c m r 算法操作示例. ” . . . - ” ” . . . “ . . - . - . . . ” . ” . . “ ” ” ” . - . . “ . ” ” . - ” “ . . . . . . . . . . . . . 4 7 n s l a - d c l c m r 归并操作中环路形成的抽象示愈图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 8 s l a - d c l c m r - a n 算法操作示例. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 d c l c - s f 算法与l d p 算法路由请求平均成功率比较. “ . ” . ” . . “ . “ . ” ” . . . . . . . . . . . . . . . . . . . . . . 5 6 网络结点平均度数等于4 , d c l c - s f 与l d p 费用不精确度比较” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 7 网络结点平均度数等于6 , d c l c - s f 与l d p 费用不精确度比较. “ “ “ “ . . . . . “ . . “ . ” 一5 7 网络结点平均度数等于8 , d c l c - s f 与l d p 费用不精确度比较. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 7 三种扩展策略与l d t 路由请求平均成功率比 较. ” ”. “ . “ . . ” . . . . . . . ” ” ” - . . - . . . ” ” . . . - 一 5 9 s l a - d c l c m r - a n , s l a - d c l c mr - s n 与n s l a - d c l c m r 费用不精确度比较. . . . . . . 6 0 传统遗传算法的求解流程 . ” 二 ” “ . ” . . . . . . . . . . . . . . . . . . . . . . . . . 一 一一. . 一一， . . 6 3 . - . .一 - - 一一一. 一一- ， 一一一-网 一-一一. 一一- 一x 一 华 中 科 技 大 学 博 士 学 位 论 文 图 4 .2 启 发 式 遗 传 算 法 的 求 解 流 程 .“ “ .“ ” “ “ .“ ” ” ” ” ” ” ” ” ” ，. ，二 6 3 图4 . 3 d c l c mr - h g a 算法的交叉操作示例. ” ” ” ” ” “ . “ . “ ，. “ “ “ 二 ” :. “ “ 二“. . . . . . . 6 8 图 4 .4 一 般网 络模型 示 例二 “ . . . . . .- . . - . . . . ，. . . . “ .” “ .” “ “ “ ，. “ . . . . . . . . . . . . . . 7 3 图4 . 5 d c l c m r - h g a 与l d t 路由请求平均成功率比较. . . “ . . . . - - . ” ” . ” ” ” 一“ . . . . . . . . . . . . . . . 7 9 图 4 .6 q o s m r - h g a 与b c l d t , b c l d j t , b c l p k t 路由 请求平均成功率比 较:. . . . . . . . . . 7 9 圈 4 .7 d c l c m r - h g a 算法计 算实例.” .“ . . . . . ” . ” . .“ . . “ .” “ “ “ 。 “ . . . . . . . . . . . . . . . . . 8 0 图4 . 8 d c l c mr - h g a 算法搜索中组播树代价、延时随遗传代数变化曲线、 . ，. ” “ ” 一 8 0 图 4 .9 q o s m r - h g a 计 算 实 例 .，. .“ .” . .- ” ” ” ” ” . 8 1 图 4 . 1 0 q o s m r - h g a 算法搜索中组播树代价、 延时和延时抖动随遗传代数变化曲 线” . . . . 8 1 图4 . 1 1 b s m a 相对于d c l c m r - h g a 的费用不精确度百分数随网络结点变化曲线. . . . . ” 二 82 图5 . 1 d c l c - d s f 算法的有限状态机模型. . . . . . . 一 ， . . . - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 0 图 5 .2组播终点t 加入时环路形成抽象示意图. . .- . . ” ” “ ” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5 图5 . 3 d d d c l c mr 加入、删除操作示例 . . ” ， 、 . 、 ”， . . . . . . - . . ” “ ” . . “ . . . - . . . ” . ” ” 一 ， 9 7 图5 . 4稳定网络环境下， d c l c - d s f 与l d p 路由请求平均成功率比较 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0 0 图5 . 5动态网络环境下， d c l c - d s f 与l d p 路由请求平均成功率比较. “ . ” “ . . “ “ 一 ， . . 一 1 0 1 图5 .6网络结点平均度数等于4 . d c l c - d s f 与l d p 费用不精确度比较” . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0 2 图5 . 7网络结点平均度数等于8 . d c l c - d s f 与l d p 费用不精确度比较 . . . . . . . . . . . . . 1 0 2 图5 . 8稳定网络环境下， d c l c - d s f 平均消息变化曲线. . . “ “ . - . . ” . ” “ ” “ . . ” . . . . . . . . . . . . . . . . . . . . 1 0 3 图5 .9动态网络环境下，d c l c - d s f 平均消息变化曲线. . . . . . “ . “ “ . . . . . ” . ” ” ” “ . . . . . - . . . 一1 0 3 图5 . 1 0 d d d c l c mr 与l d t 路由请求平均成功率比较. . ” “ . . - . . - . ” ” ” ” “ . . . - . ” ” . . “ . ” “ “ 一1 0 4 图5 . 1 1 延时的柬 = 8 0 m s , d d d c l c m r 算法的费用不精确度. . 。 ” . . “ ” “ ” . ” . ” . . “ 一 、 0 5 图5 . 1 2 网络结点数为2 0 0 , d d d c l c mr 算法的费用不精确度. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 0 6 图5 . 1 3 r c n a , l d c n a 和l c c n a 加入机制的费用不梢确度比较. . ” . ” . . . - - . . . . . . . . . . . . . . . . . . . 1 0 7 表1 . 1 单 播 q o s 源 路由 算 法二 价 . . . . 一 ， 二 ， . . . . ， 价 价 ” ” _一一-叫一目 - . 一 一一- -一一一一一一- 一xl 一 华 中 科 技 大 学 博 士 学 位 论 文 表1 . 2 表1 . 3 表3 . 1 表3 .2 表4 . 1 表4 . 2 表5 . 1 表5 . 2 分布式q o s 单播路由 算法. ” ，. . ” “ ” . . . ” . .” . . . ” . .“ . ” ” “ . ” . “ ” “ ” ” - .“ . . ” .” . . ” “ ” 一1 3 q o s 组 播 路由 算 法 ” 一” ” ” ” . . “ “ ” ” “ ” “ ” “ ” “ “ 一 1 5 d c l c - s f 算法运行时间. ” . ” 一 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 8 三种d d c l c mr 算法运行时间比较一“ 二 “ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 0 d c l c mr - h g a 与b s ma 算法运行时间比较二 ” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 q o s mr - h g a