（计算机应用技术专业论文）彩铃铃音服务器缓存算法的设计与实现.pdf

北京邮电大学硕士学位论文 彩铃铃音服务器缓存算法的设计与实现 彩铃铃音服务器缓存算法的设计与实现 摘要 随着彩铃业务的成熟和发展，如何有效地存储和管理大容量的铃 音数据成为了一个重要的技术问题。本文提出新增铃音服务器网元作 为集中式铃音数据存储方案，利用高效的磁盘缓存算法满足了系统设 计容量的要求。该方案的重点是缓存算法的设计与实现。首先，在理 想环境下建立了缓存分配的数学模型，用动态规划算法给出了理想模 型的最优解；为了进一步提高速度和减少空间消耗，针对理想模型的 特点用贪婪算法得到了模型的近似最优解。其次，通过分析现网中实 际的彩铃铃音订阅数据，为铃音流行度建立了数学模型，证明了铃音 播放流行度服从z p f 分布的结论，并利用该结论对经典缓存算法 l r u ( l e a s tr e c e n t i yu s e d ) 和l f u ( l e a s tf r e q u e n t i yu s e d ) 进行了分析和验 证。针对经典算法的不足和铃音服务器应用的特点，本文创新性地提 出了一种新的缓存替换算法l f u e a ( l f uw i t he x p o n e n t i a ia g i n 酊，该算 法采用指数平滑公式作为频率老化机制，使用灵活的手段来平衡资源 访问模式中的频率特性和时间特性，能够很好地与缓存周期性替换模 型结合起来，适宜应用在磁盘缓存系统中。实验结果表明l f u e a 算 法比经典算法的缓存命中率提高了l o 左右。为了有效地实现l f u e a 算法，我们引入了受限二叉堆数据结构用于快速过滤大量铃音文件， 并实现了应用双散列技术的通用散列容器，该技术从理论上有效地保 证了高负载下容器的性能不会退化，适宜应用在对实时性要求很高的 场合。实验证明该容器比标准容器速度更快并且占用更少的内存空间。 最后，详细介绍了具体实现中的负载均衡策略，给出了应用r e a c t o r 模式和l e a d e r f o o w e r s 模式作为软件并发架构的理由，讨论了容错 机制的设计等等问题。本文提出的流行度建模技术和缓存替换算法 l f u e a 对于其它的磁盘缓存系统也有良好的借鉴意义。 关键词：流行度建模、z p f 分布、指数平滑、l f u e a 、双散列技术、 负载均衡、r e a c t o r 模式、l e a d e r f o o w e r s 模式 北京邮电大学网络与交换技术国家重点实验室 d e s i g na n di m p e l m e n t a t i o no fc a c h e a l g o r i t h mf o rr l n gs e r v e rf o rc r b ts e r v i c e a b s t r a c t w i t ht h er a p i dg m 、 ，t ho fc d ，o rr ，仃g8 a 以仍，ps e n ，i c e s ，t h e m b e c o m e sa ne m e 唱i n gp r o b l e mo fs t or n ga n dm a n a g i n gi a 唱ea m o u n to f r n gd a t ae 仟e c t i v e l ya n de f f i c i e n t i y ：t h i sp a p e rp r o p o s e das o i u t i o nb y a d d i n gr i n gs e r 、f e ra sac e n t 怕ls t o r a g en o d et ot h en e t w o r ka n du t i i i z i n g d i s kc a c h ea i g o r i t h me x t e n s i v e i yt om e e tt h er e q u i r e m e n to fs ”t e m d e s i g nc a p a c i t v f i r s tw eb u i i tc a c h ea o c a t i o nm o d e iu n d e ri d e a i a s s u m p t i o n sa n dp r o v i d e d a n o p t i m a is o l u t i o nb yu s i n gd y n a m i c p r o g r a n l m i n g ，a n dt h e nw ef o u n di t ag o o da p p r o i m a t i o nb yu s i n g g r e e d ya i g o r i t h mf o r n p r o v e ds p e e da n dr e d u c e ds p a c e b ya n a i y z i n g r n gs u b s c r i p t i o n d a t aa n d b u i i d i n gm a t h e m a t i c a i m o d e i sf o r r n g p o p u i a r i t w ep r o v e dt h a tr n gp i a y i n gp o p u i a r i t yo b e y sz i p fd i s t r i b u t i o n ， u n d e rw h i c hw ee x p er m e n t e do nc l a s s i c a ic a c h ea i g o r i t h ml r u ( l e a s t r e c e n t l yu s e d ) a n dl f u ( l e a s tf r e q u e n t i yu s e d ) b a s e do nt h ep r o sa n d c o n so fl r ua n dl f ua n dt h ec o n t e x t0 fr n gs e r v e ra p p l i c a t i o n ，w e p r o p o s e dan e wc a c h er e p i a c e m e n ta i g o r i t h ml f u e a ( l f uw i t h e x p o n e n t i a ia g i n g ) ，w h i c ha d o p t se x p o n e n t i a is m o o t h i n ga sf r e q u e n c y a g i n gm e c h a n i s m ，a n dj tb a i a n c e sw e t h ef r e q u e n c yf e a t u r ea n d “m e f e a t u r eo ft h er e s o u r c ea c c e s sp a t t e r n e x p e r i m e n t ss h o wt h a tl f u e a a i g o r i t h m m p r o v e sc a c h eh i tr a t i oo v e rc i a s s i c a ia i g o r t h m sb y1 0 t o i m p i e m e n tl f u e aa l g o r i t h me 仟e c t i v e i y ，w ei n t r o d u c e di i m i t e dh e a p d a t as t r u c t u r et of i i t e rm a s s i v er i n gf j i e se 仟i c i e n t i ya n dd e s i g n e dg e n er c h a s hc o n t a i n e rw i t hd o u b i eh a s h i n gm e c h a n i s m ，w h i c he n s u r e ss t a b i e p e r f o r m a n c ee v e nu n d e rh e a v yi o a df o rt h em o s td e m a n d i n gr e a i t i m e a p p i i c a t i o n s e x p er i m e n t ss h o wt h a tt h eg e n e r i ch a s hc o n t a i n e rw e d e s i g nh a s t h ea d v a n t a g e o f h i g h e rs p e e d a n di o w e rm e m o r y c o n s u m p t j o no v e rs t a n d a r dh a s h n t a i n e r s f i n a y ，w ei u s t r a t e dt h e l o a d b a i a n c i n gp o i i c 坼 t h er a t i o n a l et oa p p i yr e a c t o rf a t t e r na n d l e a d e r f o o w e r sp a t t e r na sc o n c u r r e n ta r c h i t e c t u r e ，a n dt h ed e s i g no f f a u i tt o i e r a n c em e c h a n i s m t h ep r o p o s e dp o p u i a r i t ym o d e i i n gt e c h n i q u e s t a t ek e yl a b o r a t o r yo f n e t w o r k i 哩a n d 鼬h c h 旧t e c h n o i 吲1 a n dl f u e aa i g o r i t h mj nt h ep a p e ri sag o o dr e f e 陀n c et oo t h e rd i s k c h i n gs y s t e m s k e yw o r d s ：p 0 p u i a r i t ym o d e i i n g ，z i p fd i s tr b u t i o n ，e x p o n e n t i a i s m o o t h i n g ，l f u e a ， d o u b i eh a s h i n g ，l o a db a i a n c i n g ，r e a c t o r p a t t e r n l e a d e r ，f o i i o w e r sp a t t e r n 2 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 li ， 本人签名： 垒f 型刍日期：銎塑2 二! 二垒 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期： 日期： 劢、乒 型国，五：垒 北京邮电大学硕士学位论文 彩铃铃音服务器缓存算法的设计与实现 第1 章彩铃业务与铃音服务器 1 1 彩铃业务的发展 彩铃( c o i o rr i n gb a c kt o n e ) 是一项由被叫客户为呼叫自己移动电话的其他主 叫客户设定特殊音效音乐、歌曲、故事情节、人物对话) 的回铃音的业务。用户 开通这项业务后，对方在拨打该用户手机等待接通的时候，听到的是该用户所设 置的音乐或音效。 彩铃业务最早由韩国s k 电讯于2 0 0 2 年3 月在韩国推出，短时间内便风靡全 韩。2 0 0 3 年。彩铃业务被中国移动率先引入中国市场，并取得了巨大的商业成 功。中国联通首先在其高端用户占主流的c d m a 网中开展了炫铃业务。商用之后 进一步扩大炫铃的用户容量，使联通1 3 0 1 3 l 号段的g s m 网用户也可以和c d m a 用户一样享受炫铃服务。中移动2 0 0 4 年年报显示，短短一年间，手机彩铃注册 用户总数已经超过2 7 2 1 万，按照移动彩铃业务每月5 元的功能费计，仅此一项， 中移动每年就有超过1 2 亿元人民币的收入，占中移动去年总营运收入的0 6 左 右。据中国移动相关人士透露，彩铃将成为今年移动运营商的重要收入来源。彩 铃被认为是继短信后，移动增值业务中最有可能再现行业“神话”的业务“j 。 追求个性化的表现是时下年轻人的特性，而在手机用户群中年轻人无疑是最 大的消费者，所以作为移动服务商来说，提供更多展现时尚个性的业务种类是其 发展的主要方向之一。彩铃业务的目标客户正是3 0 岁以上的白领、3 0 岁以上的 蓝领、3 0 岁以下的白领、3 0 岁以下的蓝领、学生。他们共同的特点就是崇尚个 性，思维活跃，对移动通信的需求中娱乐休闲社交比重较高，对新事物的接受能 力比较强。同时，这一群体有一定的消费能力，容易接受相对较为低廉的彩铃业 务费用”。 集团用户也是彩铃的另一个目标客户，独特的集团彩铃也是彩铃业务的增长 点。集团彩铃是在普通多彩回铃音基础上，根据集团客户需要为其提供的与该集 团相关的特殊铃音。集团客户特别是服务行业及销售行业的集团客户的工作人员。 及销售部门可利用这一新颖的形式，介绍企业品牌和产品、业务联系方式等；可 利用集团彩铃业务宣传企业形象、企业理念；对于知名企业或单位，可为员工设 置体现企业文化和企业精神等的歌曲等等。集团彩铃主要特点在于：体现企业形 北京邮电大学网络与交换技术国家重点实验室 北京邮电大学硕士学位论文 彩铃铃音服务器缓存算法的设计与实现 象，宣传企业的品牌、文化、产品、服务理念、业务联系方式等，帮助企业加强 与客户及与员工的沟通。集团用户主要是注重提升集团形象，注重企业文化的集 团客户。尤其是服务行业及销售行业的集团客户，很容易接受这类的增值服务“。 图1 12 0 0 3 2 0 0 6 年中国彩铃市场规模 田1 - 22 0 0 3 - 2 0 0 6 年中国彩铃用户规模 作为一项全新的话音业务，彩铃业务不像短信、呼叫转移等业务那样对原有 语音业务有替代性，它所带来的完全是全新的收益，所以一开始便受到了移动运 营商的青睐。2 3 年s 月彩铃市场启动，当年年底，用户数为2 万，市场规 模达到了1 6 8 0 万元。而到2 4 年末，全国手机彩铃注册用户就达到2 2 万， 行业产值达到了8 6 亿元；截至2 s 年5 月，全国彩铃用户达3 4 0 0 万，市场规 模已经突破1 0 亿元。2 6 年用户数可达到6 0 0 0 万以上，市场规模高达5 0 亿。 图1 1 和图l - 2 分别展示了2 3 2 0 0 6 年中国彩铃市场规模和用户规模的发展情 北京邮电大学弼络与交换技术国家重点实验室 北京邮电大学硕士学位论文彩铃铃音服务器缓存算法的设计与实现 况吼 虽然与短信百亿以上的市场规模相比，彩铃市场还存在相当大的差距，但是 彩铃业务市场增长速度则是超过了1 0 0 。2 7 年之后，预计中国8 0 以上的手 机用户会申请并使用彩铃业务，其市场规模非常巨大。 1 1 2 彩铃铃膏资源增长 现有彩铃铃音s p 商大致有三类：门户网站，如新浪、t o m 在线等；设备提 供商自然转型，如上海灵通；由唱片公司成立的负责移动增值业务的新部门或公 司，如滚石移动。其他的就是一些看好彩铃业务的小公司。全国进入彩铃行业的 s p 有近s o 家公司，深圳地区约有2 0 家s p 在开展彩铃业务。其中业务较好的s p ， 从前期的5 大彩铃s p ：全天通、掌上灵通、新浪、t o m 、空中网已经又变成了 龙腾阳光、腾讯、滚石移动、新浪、t o m 和万讯通，2 0 0 5 年一年的时间里，市 场格局已经发生了很大的变化。 图1 - 3 展示了2 0 0 5 年8 月各大铃音s p 的彩铃资源数目抒j 。 图1 32 0 0 5 年8 月主要s p 彩铃资源比较 预计今后的几年内，随着市场的不断成熟，铃音资源将会得到极大的增长。 并且，随着用户自定义铃音i 彩铃d i y ) 业务的开展，如何有效地存储和管理海量 铃音数据将逐渐成为一个非常重要的技术问题。 1 2 彩铃业务呼叫处理流程 本节简要介绍一下目标网方案( 主叫交换机方案) 中彩铃业务的呼叫处理流程， 北京邮电大学网络与变换技术国家重点实验室 北京邮电大学硕士学位论文彩铃铃音服务器缓存算法的设计与实现 主要内容参考文献【4 】。 1 2 1 目标啊方案 图1 - 4 为目标网方案组网结构图，其中粗实线表示话路，细实线表示i s u 昕u p 信令链路，虚实线表示m a p b s s m a p 信令链路。 如图1 1 4 所示，网络中增加了彩铃平台，与主叫m s c 或g m s c 通过e 1 中继 接口，接口信令为i s u p ；g m s c 与它网交换机连接的信令可以是l s u p 或者t u p 。 主叫m s c g m s c 为主叫发起呼叫的交换机；h l r 中记录被叫是否具有彩铃业 务的信息s s o d e ( 2 5 4 ) ，并在s r i - a c k 响应信令时返回，以标识“彩铃”呼叫； 彩铃平台具备根据主被叫用户播放铃音的功能；被叫m s c 为被叫用户当前所在 的交换机。 田1 - 4 彩铃目标网方案组冈结构图 技术实现机制简要说明如下：主叫m s c 或g m s c 发起路由查询i s 刚) 操作时， 如果h l r 返回的s r l a c k 中具有彩铃s s - c o d e ( 2 5 4 ) ，则将本呼叫置上彩铃呼叫标 志记录本呼叫为彩铃呼叫，然后接续到被叫m s c ( 过程同普通呼叫) ：当被叫m s c 返回a c m 信令且其中状态指示为空闲时，主叫m s c 根据彩铃呼叫的标志，暂时 阻塞被叫m s c 的普通回铃音，并向彩铃平台发起呼叫，成功建立连接后由彩铃 平台根据主被叫号码的逻辑关系选择彩铃并向主叫侧播放；当主叫m s c 收到被 叫m s c 返回的a n m 应答信令时，拆除和彩铃平台的连接，向主叫侧回应答信令， 并重新激活主被叫用户之间的通话话路。 4北京邮电大学网络与交换技术国家重点实验室 北京邮电大学硕士学位论文彩铃铃音服务器缓存算法的设计与实现 可见彩铃业务由主叫m s c 、g m s c 、h l r 和彩铃平台等网络设备配合完成。 其中彩铃平台的话路连接只在播放彩铃时被占用，在呼叫应答后的通话期间并不 被占用。 本节以主被叫都是无智能签约信息的移动用户为例，给出目标方案中普通彩 铃呼叫的正常处理流程。非智能用户的彩铃呼叫处理流程如图1 s 所示，图解如 表1 1 所示。 i 葬燃冀i l主叫听彩铃音 l i 被口噼靖i i 揸听l 主被叫开始正常通话：彩铃音被旁路 j = = l 正常通话 图1 s 目标方案普通彩铃呼叫正常信令流程围 北京邮电大学网络与交换技术国家重点实验室s 北京邮电大学硕士学位论文 彩铃铃音服务器缓存算法的设计与实现 裹1 - 1 目标方案普通彩铃呼叫正常信令流程围图解 消息名解释 v 1 s 哦u p ，l a m 月a j 主叫m s c 收到重叫用户的s e t u p 消息：或者g m s c 收到外网入 i 疑溉、啉l 、虬镰食；j j ，j。j。j， ， j 主叫m s c 向被叫h l r 发s 刚，查询路由信息，其中利用扩展域带 2s r i 有彩铃支持信息标志： * 3 p r 摊 h l r 向被# q 愿户当前质在的援叫m s e 发p r n ，罨隶m s r 。 4p r na c k 被叫m s c 分配m s r n ，向h l r 回p r n - a c k ； h l r 向毛叫m s c 发s r u c k ，根据s r i 信令中带有的彩铃支持信 5 s r ia c k 息标志，s r i j i c k 中带有m s r n 以及彩铃业务码s s 鼻o d e ( 2 5 4 ) ； 主叫m s c 根据彩铃业务码将本呼叫置上彩铃标志，并利用m s r n 6i a m 向被叫侧发起i a m ； 被叫m s c 收到被叫用户的寻呼响应( 表示被叫空阑) ，发出呼叫建立 7 s e t u p 消息； 被叫用户成功建立连接后，终端振铃，同时返回振铃消息给被叫 8 a i e 嘣n g m s c ： 9a c m 被叫m s c 向主叫侧同振铃倍令a c m ，荚中用户状态为空阑；被叫 m s c 捌对努始掇放蓠通网铃音； ，。 1 0 a i e m n g ，a c m 主叫m s c 向主叫移动用户发送a i e 嘣n g 消息，或者g m s c 向外网 交换机发送a c m 誓 i 圭州m s c ，g m s c 收射被明侧网的a c m 詹。根据第6 步所置的彩 ：”1 i a 雠 铃呼叫标志，暂时挂起与被酬侧的话路连接，同时向被叫用户所属 歉胸彩铃平务发送魄蝌消息，被川号黪为“媲务码十被蛳l s d n 冀。 彩铃平台根据主被叫用户号码得出所需的铃音，向主叫m s c ，g m s c 1 2a c m 回送a c m 消息并开始播放铃音。这时起主叫用户开始听到被叫定制 的铃音。 ” 秽3 疆3。c 沁b n e c t 薇8 嗍户接骄素话，终端鼹被腿m s e 发遨e o n 臻溥怠+ 。一，囊 1 4a n m被叫m s c 向主叫侧发送a n m 应答信令 “ 一z 二 主叫m s ci 秘至叫用尸发邀c o n n e c 耄消息；或者g m s c 向外网转发 c o n n e c ta n m ，a n c 消息。同时，主叫m s c g m s c 将彩铃话路挂起，转而 1 5 ：，a n m a n c 打开到被叫m s c 的话路连接，使主被叫用户正鬻对话，双方都听不 “ 貔 嘲彰镊薏。? ? ，。 一 。，i 。蒜 在回送c o n n e c t a n m ，a n c 之后，主叫m s c ，g m s c 向彩铃平台 1 6r e l 发送拆线信令r e l ，拆线原因值为正常拆线。 北京邮电大学网络与交换技术国家重点实验室 北京邮电大学硕士学位论文 彩锋铃音服务器缓存算法的设计与实现 1 互3 智能用户彩铃呼叫的正常处理藏羞 彩铃业务与智能业务没有任何冲突，即无论什么智能业务的签约用户都可以 开通彩铃功能。下面以一个主被叫都是c s i 签约智能用户( 为图示方便，假定主被 叫用户归属于同一个s c p ) 的呼叫为例进行流程描述。智能用户的彩铃呼叫处理流 程如图1 - 6 所示，图解如表1 2 所示。 北京邮电大学网络与交换技术国家重点实验室7 北京邮电大学硕士学位论文彩铃铃音服务器缓存算法的设计与实现 图1 6 目标方案智能用户彩铃呼叫的正常信令流程图 表1 2 目标方案智能用户彩铃呼叫的正常信令流程图图解 洧息名解释 0 ” “ + | 臻 对， 。霸，坳。$ 主列m s e 收到主舛愿户麴s 瓢。u p 游息一一。一。；。囊 主叫m s c 根据主叫用户数据中的o c s i 触发主叫智能流程， 2 i d p 发送i d p 消息给s c p 8 北京邮电大学网络与交换技术国家重点实验室 北京邮电大学硕士学位论文 彩铃铃音服务器缓存算法的设计与实现 i j + ”。 一 “ ” ”+ ” 3r r b e + a c + c o n t i n u e s c p 进行智能业务逻辑处理后，下发” r r b e + a c 晦o n t 料u e 等相失信令指示m s c 继续接绫i 主叫m s c 向被叫h l r 发sr i ，查询路由信息，其中利用扩 4s r i 展域带有彩铃支持信息标志： _- * h l r 向主叫m s c 发s r l j c k ，其| l 带有被叫用户的签约 5s 剐a c k i 缡恳t e s l ；此时s r l a c i 申不带葫彩铃s 置s o d e 2 5 4 ) ，。 主叫m s c 根据被叫用户的t c s i 触发被叫智能流程，发送 6 i d p i d p 消息给s c p + |*一”。_ 一、一 s c p 进行智能业务逻辑处理屠，下发 7r r b e + a c + c o n t i n u e r r b e 螂c + c 0 n t l n u e 等相关信令指示m s c 继续接续 主叫m s c 向被叫h l r 发s r l ，查询路由信息，消息带有抑 8 s r i l 2 ) 制t c s i 的标志，并利用扩展域带有彩铃支持信息标志； h l r 向被叫用户当前所在的被叫m s c 发p r n ，寻求 9p r n m s r n ： 1 0p r na c k 被叫m s c 分配m s r n ，向h l ri 到p r n a c k ； h l r 向主叫m s c 发s r l _ 够k ，根据s r i 信令中带有的彩 1 1 s r l c 喇2 铃支持信息标志，s r l c k 中带霄m s r n 以及彩铃业务碍 ， 8 乏瓣昏缛绣+ ?： ；。 主叫m s c 根据彩铃业务码将本呼叫置上彩铃标志，并利用 1 2l a m m s r n 向被叫侧发起i a m ； 被叫i i i l s e 收瓣被刊用户的寻呼响应( 表示被蝉空阕) ，发出 1 3 s e t i i p 呼叫建立消息； 被叫用户成功建立连接后，终端振铃，同时返回振铃消息给 1 4 a l e 憎n g 被叫m s c ； 被日qm s c 向主叫侧回振铃信令a c m ，其中用户状态为空 1 5a c 酗 耀；被叫m s c 同时开始播放酱通回铃啻； 1 6 a i e r t i n g主叫m s c 向主叫移动用户发送a l e r t i n g 消息 主叫m s e ，g m 8 c 收到被叫侧翮的a c m 后，根据第6 步所 1 7l a m 譬的彩铃呼叫标志，暂时捧起与被州侧的话路连接，同时向 彩铃平台发送j 9 蝴消息，款雕号码为“业务玛+ 被川l s d n ” ， 彩铃平台根据主被叫用户号码得出所需的铃音，向主叫 1 8a c m m s c ，g m s c 回送a c m 消息并开始播放铃音。这时起主叫 用户开始听到被叫定制的铃音。 i ，。 ” p 嘻e a 聃靠翻醴 被嘲期户麓瞬蘩语，终溃f 篷被辫b 褥e 发送e o 黼e c i 游崽+ 北京邮电大学网络与交换技术国家重点实验室 9 北京邮电大学硕士学位论文彩铃铃音服务器缓存算法的设计与实现 2 0a n m 被叫m s c 向主叫侧发送a n m 应答信令 主叫m s c 向主畦用户发送c o n n e c t 消息。同时，主哦 2 1c o n n e c tm s c ，g m s c 将彩铃话路挂超，转而打开到被叫m s c 的话 糖r 路连接，馕主被h q 用户厩常对话双方都听不到彩铃膏，+ 。 主叫m s c ，g m s c 向彩铃平台发送拆线信令r e l ，拆线原因 2 2r e l 值为正常拆线。 一 2 3 r e l c o m 彩铃乎爵廊主叫m s c ，g m s c 回送r e le 0 m 信令，表示拆 线完毕e ，。 1 3 彩铃平台组网结构 图1 7 彩铃平台结构图 图1 - 7 展示了东信北邮信息技术有限公司彩铃平台的网络结构。其中最重要 的几个功能实体简介如下： 1 ) 信令前置( s a n ) ：将呼叫信令从e 1 话路转换到t c p i p 网络上，并通过一 定的负荷分担算法将呼叫转发到后台的多个控制节点i c n ) 进行处理。 2 控制节点l c n ) ：彩铃平台核心功能实体，负责业务逻辑的解释和执行， 北京邮电大学网络与交换技术国家重点实验室 北京邮电大学硕士学位论文彩铃铃音服务器缓存算法的设计与实现 提供信令和数据库接口，与其他功能实体交互，控制资源节点( r n ) 为用 户播放彩铃等等。 3 ) 资源节点( r n ) ：提供特殊资源功能，包括语音播放、语音录制、酊m f 收 号等等。在没有铃音服务器时，所有铃音资源存储在r n 的本地磁盘中。 r n 服务器群采用负荷分担的方式工作，因此所有r n 节点都是同质的。 也就是说，所有r n 节点上的铃音文件应当完全一样，因为控制节点可 能挑选任意一台r n 节点来为用户播放彩铃。 4 ) w 曲接入服务器( w 曲p o n a i ) ：提供w 曲门户接入，同时具备铃音资源 管理功能。 5 ) 铃音服务器( r s ) ：作为一个新的网元增加到网络中，用于解决海量铃音的 存储问题。 1 4 铃音服务器 铃音服务器( r s ) 提供海量的存储空间，为系统中所有的放音资源节点( r n 提 供可播放的资源，包括各s p 提供的铃音和用户d i y 的铃音。有了铃音服务器之 后，r n 的本地存储空问将成为高速缓存( c a c h e ) ，r n 仅将最常播放的铃音存储在 本地磁盘。当r n 本地磁盘不存在所要播放的铃音时，才通过网络到铃音服务器 上去寻找和播放。同时，r s 上会启动缓存管理应用r s a p p ) ，通过一定的算法统 计出最常播放的铃音，并定期通过网络更新本地r n 的缓存资源。该缓存算法的 设计及实现是本文的重点。 铃音服务器硬件一般采用h p 的d l 3 8 0p cs e r v e r ，配置千兆以太网卡。一套 铃音服务器配置两台，之间采用双机热各+ 负荷分担的方式工作。操作系统通常 采用r e dh a ta d v a n c e ds e r v e r3 o 4 o 。 图1 8 展示了陋在系统中的连接情况。细线代表n f s ( n e t w o r kf i es y s t e m ) 映射，箭尾作为客户端，箭头指向服务器，双箭头代表建立双向的n f s 映射。1 5 节将给出采用n f s 作为铃音传输协议的理由。 其中w e bp o r t a l 具备铃音管理界面，通过它用户和s p 可以将铃音上传到衢 和各个r n 。骼和所有r n 之间建立双向的n f s 映射关系，这样r n 在缓存未命中 时可以通过n f s 播放彩铃；而r s 也可以通过n f s 更新所有r n 上缓存的铃音文 件。 北京邮电大学网络与交换技术国家重点实验宣 1 1 北京鄙电大学硕士学位论文 彩铃铃音服务器缓存算法的设计与实现 圈1 - 8 铃音服务器组孵结构及n f s 映射关系 1 5 铃音传输协议 本节主要叙述铃音服务器项目选择n f s ( n e t w o r kf es v s t e m 作为其铃音传输 协议的理由。 1 5 1 黼协谈的优点 采用n f s 协议作为铃音传输协议的优点如下： 1 l 标准化：n f s 最早是由s 叽公司开发的，它不是文件系统的具体实现， 丽是一个标准化的协议，其本身的开发受到i e t f 的监管和指导，如r f c 1 0 9 4 ( n s f2 ) ；r f c1 8 1 3 ( n f s3 ) ；r f c3 s 3 0 ( n f s4 ) 2 l 跨平台性：n f s 得到众多u n i x ，l j n u x 供应商的支持，现网环境中机器种 类繁多，常见操作系统有h p u x 、s o i a r s 、a i 、u n u x 等等，因此选择一 个具有良好跨平台性的协议非常重要。 3 l 高性能：随着n f s 版本的演进。其性能也不断提升。n f s2 只能工作在 u d p 之上，其数据包大小不能超过8 k b ；n f s3 可以工作在u d p 或者t c p 之上，其数据包大小可以调整，因此可以获得更好的性能。n f s3 引入了 安全异步写入i s a f ea s y n c h m n o u sw r t e s ) 允许服务器在数据没有真正写 入磁盘之前回复客户端，因此能够批量写入大量数据，从而大大提高写 北京邮电大学同络与交抉技术国家重点实验窒 北京邮电大学硕士学位论文彩铃铃音服务器缓存算法的设计与实现 入效率1 5 】。n f s4 引入了客户端缓存( c l i e n t s i d ec a c h i n g ) 允许客户端修改 本地缓存文件而无需向服务器发送网络请求，直到别的应用需要并发访 问这些文件为止旧。在大多数情况下此特性能够明显降低网络负载，从 而提高应用的性能。 4 l 透明性：n f s 允许客户端使用标准的u n i x 文件操作a p l 访问服务器上的 文件，从应用层的角度看和访问本地磁盘上的文件没有区别。这对遗留 系统的改造，特别是放音资源节点( r n ) 的改造是有利的，能够大大节约 开发成本并且减少出错的可能。 1 5 2 _ f s 协诚性能测试 为了测试n f s 协议的吞吐量，设计了一个测试用例对其性能进行测试。测试 软硬件环境如表1 3 所示： 表1 - 3n f s 协议吞吐量测试软硬件环境 网测 服务器硬件客户靖硬件及n f s 服务器配 n f s 客户端配置 络试 及0 so s置配文 置件 博 双 彩 2 c 4 g h p 1 c ( x e o n3 ，2 6 n f s d1 6 遴程，客户端使用u d p 网 铃 r p 4 4 4 0 w i t h2 l g d 珏8 0 w 附12 为排除磁盘方式进行m o u 瞒， 卡 铃 1 0 0 0 m bn i c 、 1 0 d o m bn i c ， i o 影晌使用共超4 个脚本遴 千 音 r h l a s 4 兆 h p u x1 1 ir a m d i s k 行压力测试文 u 口d a t e3直 件 f连 测试时在客户端每一块网卡上启动两个压力测试脚本，共启动四个脚本。测 试脚本反复对大量彩铃铃音文件进行读取，如下所示： + 茹i l j 口殛。一二i “二。二。* ：一+ ”二j 4 ”一：+ j 謦 = 。， 。 d 0 。 f i e d m n n f s 一t p ef e x e cc a t ) d e v n u l 王； ” 咖e 。 。 ： 。 瓮 测试时使用h p 机器上的g l a n c e 工具对服务器端网络和c p u 负载进行性能监 测，结果如表1 4 所示。测试结果表明，在排除磁盘i o 影响的情况下，单网卡 吞吐量能够稳定地达到3 s o m b 左右。这说明n f s 协议本身不太可能成为系统性 能的瓶颈。真正决定系统性能的参数是磁盘i ，0 吞吐量，主要包括f c 带宽、阵 列对外输出带宽等。 北京邮电大学网络与交挽技术国家重点实验室 北京邮电大学硕士学位论文彩铃铃音服务器缓存算法的设计与实现 袭1 - 4n f s 协议吞吐量测试结果 网i np a c l 难t0 u tp a c l t i n k b r a t e 0 u t k b 每个n f s d 进 程的平均 卡r a 玉er a 旬er a t e c p u 占用率 12 1 6 4 3 2 4 s 6 63 0 7 5 1 1 3 3 6 2 9 33 7 9 4 4 3 l 24 3 1 9 3 4 7 2 4 1 4 o f 2 懈 m a x l 21 8 8 6 6 2 3 2 7 02 8 0 8 0 1 3 2 0 5 2 53 3 0 3 4 0 8 33 9 4 6 7 4 5 0 3 0 1 6 系统容量的估算 设缓存命中率为l l ，r n 主机数为r n ，铃音服务器忙时平均阿络带宽为b ， 单台r n 允许峰值呼叫占用率为h ，铃音文件采样率为s ，则： 8 = 单台r n 网络访问铃音的峰值带宽r n 、 = 攀台r n 峰值呼叫数每秒铃商数据节( 1 - n ) r n = h 每个中继的时隙数单弁最大中继数s ( 1 - n ) r n 曼2 圆x 3 2 3 0 s ( 均) r k 一+ 。 +。一。一 。 。 。纛 如果h = 7 0 ，b = 7 0 0 m b s ，s = 8 k h z + 1 6 b i t = 1 2 8 k b s ，则系统可以支撑的 r n 数目如式1 1 所示： 心= 嘲 式1 - 1r n 数目与缓存命中率的关系 如果缓存命中率达到8 0 ，则可同时支持约4 1 台r n 主机，理论上网络支 持的最大并发用户数可达约2 7 5 5 2 人。如果缓存命中率达到9 0 ，则可同时支持 约8 3 台r n 主机，理论上网络支持的最大并发用户数可达约1 1 3 8 2 8 人。可见提 高缓存命中率对于提高系统容量具有至关重要的作用。 1 7 本章小结 本章首先介绍了彩铃业务及其发展，从统计数据可以看到彩铃业务还有很大 的市场发展空间，用户数也远远没有达到饱和。同时，随着铃音资源的不断丰富， 以及用户自定义铃音( 彩铃d i y ) 业务的开展，如何有效地存储和管理海量铃音数 据将逐渐成为一个非常重要的技术问题。 本章的重点是提出在彩铃平台中增加铃音服务器作为解决海量铃音存储解 决方案。铃音服务器r s ) 提供海量的存储空间，为系统中所有的放音资源节点i r n 1 4 北京邮电大学网络与交换技术国家重点实验室 北京邮电大学硕士学位论文 彩铃铃音服务器缓存算法的设计与实现 提供可播放的资源，包括各s p 提供的铃音和用户d i y 的铃音。有了铃音服务器 之后，r n 的本地存储空间将成为高速缓存( c a c h e ) ，r n 仅将最常播放的铃音存储 在本地磁盘。当r n 本地磁盘不存在所要播放的铃音时，才通过网络到铃音服务 器上去寻找和播放。同时，r s 上会启动缓存管理应用i r s a p p l t 通过一定的算法 统计出最常播放的铃音，并定期通过网络更新本地r n 的缓存资源。该缓存算法 的设计及实现是本文的重点。 铃音服务器采用n f s 协议作为铃音传输协议，本文给出了采用该协议作为铃 音传输协议的理由，并通过实际的测试验证了n f s 协议的性能。最后，推导出了 系统容量和缓存命中率之间的关系，指出提高缓存命中率对于提高系统容量具有 重大意义。 北京邮电大学网络与交换技术国家重点实验室 北京邮电大学硕士学位论文彩铃铃音服务器缓存算法的设计与实现 2 理想模型 第2 章模型的建立与求解 理想模型假定可以准确预测未来一段时间t 内所有铃音的播放请求，并在该 假定下讨论最优的铃音缓存策略。播放请求包括每一首被播放铃音的播放次数和 平均播放时长。理想模型所推出的结论对缓存算法的设计有重要的指导意义。 乞1 理想缓存分配横墅 假设我们已经知道未来一段时间t 内所有铃音的播放请求情况。设总共播放 了n 首铃音，第i ( 1 i n ) 首铃音的播放次数为c i ，平均播放时长为l i 秒，铃音 文件大小为s t 。假定所有铃音都按照8 k h z 1 6 b i t 恒定比特率采样，则播放所有 这些铃音需要读取的字节数如式2 1 所示： 芝旦半 ：童枷o o 印k 式2 1 播放铃音文件读取字节数 注意读取的字节数和文件大小无关，仅和铃音被播放的时间有关系。在实际 彩铃系统中，当被叫长时间不接听电话时系统通常会进行循环播放，因此铃音播 放时长大于铃音文件完整播放一遍的时长是完全可能的。 现在我们需要决定将哪些铃音放到磁盘缓存中。设缓存大小为d ，优化目标 是最小限度地从网络上读取数据。也就是说，决定一个铃音集合尼使得将这些 铃音文件安装到磁盘缓存中的情况下，从缓存中读取的字节数最大。规划方程如 式2 _ 2 所示： 蓬c t j e 胃， s t y s i d ，詹【1 ，n 】 箭 式z - 2 未来时间t 内最优化铃音播放第台 容易看出，这是一个典型的0 1 背包问题，每首铃音的价值为v i = 1 6 0 0 0 c i b ， 代价为s i 。该问题的一般形式是一个n p 问题，无法在多项式时间内求解。但是， 在约束条件和决策变量是离散( 如整数) 的情况下，该问题能用动态规划i d y 帕m l c 北京邮电大学硕士学位论文彩铃铃音服务器缓存算法的设计与实现 p r 旧m m i n g l 在多项式时间内解决，代价是耗费较多的内存空间。具体解法如下： 令6 ( w ) 表示磁盘缓存容量不超过w 的情况下，从铃音集合【1 ，i 】中挑选铃音 安装到磁盘缓存中所能读取到的最大字节数。状态转移方程如式2 - 3 所示： f i ( 、 ，) = m a x ( 6 1 ( w s i ) + 1 6 0 0 0 c i l i ，f i 一1 ( w ) ) 式2 - 3 求解理想模型的动态规划状态转移