《CICQ交换机调度算法及基于时限的优先级保证》由会员分享，可在线阅读，更多相关《CICQ交换机调度算法及基于时限的优先级保证（105页珍藏版）》请在金锄头文库上搜索。
1、东南大学博士学位论文CICQ交换机调度算法及基于时限的优先级保证姓名：李勇申请学位级别：博士专业：计算机应用技术指导教师：罗军舟20070301A B S T R A C TA B S T R A C TW i t hn Oi n t e r n a ls p e e d - u pr e q u i r e da n dp a r a l l e l ，d i s t r i b u t es c h e d u l i n ga ti n p u ta n do u t p u t , t h eC l C Q ( C o m b i n e dI n p u tC r o s s p o
2、 i n tQ u e u e do rb u f f e r e ds w i t c h ) f a b r i cp r o v i d e su n i q u ea d v a n t a g eo fd e s i g n i n gh i g hp e r f o r m a n c es w i t c h e s T h eo p e np r o b l e m si n t h i sf i e l da l e ：l o wl e v e ls c h e d u l i n ga l g o r i t h m su s u a l l yp u te m p h a
3、 s i so ni t sp r a c t i c a b i l i t y , w h i c ha i ma ta c h i e v i n gl i t t l eb u f f e r , l o wc o m p l e x i t ya n dh i g ht h r o u g h p u t H i g I Il e v e ls c h e d u l i n ga l g o r i t h mu s u a n yi sc o n s i d e r e dt os o l v es o m ep r o b l e m sw h i c hm u s ts a
4、t i s f ym o r er e s t r i c t i o n s , s u c ha sd e a d l i n eg u a r a n t e e de t c M u l t i - d e a d l i n es c h e d u l i n gp r o b l e mh a sb e e np r o v e dt Ob eN P - c o m p l e t ei ft h r e eo rm o l ed i s t i n c td e a d l i n e s ( c l a s s e s )a mp r e s e n ti nt h es e
5、 t P r i o r i t ys c h e d u l i n gp r o b l e mw i t hd e a d l i n eg u a r a n t e e dh a sa l s ob e e nah o ta n dd i f f i c u l tp r o b l e ms t u d i e di nt h ef i e l do fR e a l - T i m es c h e d u l i n g H o w e v e r , t h ep r o p o s e dl o wl e v e ls c h e d u l i n ga l g o r
6、i t h m sc 柚o n l ya c h i e v eo f I eO rs e v e r a lr e q u i r e m e n t s M e a n w h i l e ，h i l g hl e v e ls c h e d u l i n ga l g o r i t h m ss t i l lc a n n o tb r e a kt h ep e r f o r m a n c el i m i to fE D Fa l g o r i t h m si nt h er e e , e n t3 0y e a r s T h i sd i s s e r t
7、a t i o na d d r e s s e st h ea b o v eo p e np r o b l e m s I nt h el o wl e v e ls c h e d u l i n gf i e l d , p e r f o r m a n c ea n a l y s i sr e s u l t sa l ep r o p o s e du n d e ru n i f o r mt r a f f i ca n dn o u - u n i f o r mt r a f f i c T h et h r e ec r i t e r i o ni n c l u
8、 d i n gl i t t l eb u f f e r , l o wc o m p l e x i t ya n dh i g ht h r o u g h p u tm u s tb eo b e y e di nt h ed e s i g no fs c h e d u l i n ga l g o r i t h m M o r e o v e r , R Ra r b i t e ri sb e l i e v e dt ob et h eb e s tc h o i c ei nt h eo u t p u ts c h e d u l i n g B a s e do n
9、t h ep e r f o r m a n c ea n a l y s i sr e s u l t s ，as c h e d u l i n ga l g o r i t h mi sp r o p o s e dw h i c hi sl i R l eb u f f e r , 0 ( 】) c o m p l e x i t ya n d1 0 0 t h r o u g h p u ti nt h el o wl e v e ls c h e d u l i n g T h en e wa l g o r i t h mC a l la c h i e v e1 0 0 t h
10、 r o u g h p u tu n d e re i t h e ru n i f o r mO rn o n - u n i f o r mt r a f f i c ，m a i n t a i n i n gt h es i m p l i c i t ya n de f f e c t i v e n e s so fR o u n dR o b i na l g o r i t h ma n dm e a n w h i l eo v e r c o m i n gt h ei n s t a b i l i t yo f t h eR o u n dR o b i na l g
11、 o r i t h mu n d e rn o n - u n i f o r mt r a f f i c I nt h eh i g hl e v e ls c h e d u l i n gf i e l d an o v e la l g o r i t h mn a m e dF l o w - b a s e dI t e r a t i v eP a c k e tS c h e d u l i n g ( F I P S ) i sp r o p o s e d T h eF I P Sa l g o r i t h me m p l o y e de n t i r e l
12、 yd i f f e r e n ts c h e d u l i n gs t r a t e g yw h e nc o m p a r i n gt ot h ec l a s s i cE D Fa l g o r i t h m T h em u l t i - d e a d l i n ep r i o r i t ys c h e d u l i n gN P - Cp r o b l e mi sc o n v e r t e dt os o l v et h en e t - f l o wp r o b l e mw i t hu p p e ra n dl o w e
13、 rb o u n dt h r o u g hc o n s t r u c tt h ef l o w b a s e dm o d e lb e t w e e nt h ed i f f e r e n td e a d l i n e sp a c k e ts e t s F I P Sa l g o r i t h mp r o m o t e st h el o w e rp r i o r i t yp a c k e t st ot h ei d l ep o s i t i o n si nh i g hp r i o r i t yp a c k e t ss e tu
14、 n d e rg l o b a lc o n s i d e r a t i o n s n o tr a n d o m l y T h ec o m p a r i s o ne x p e r i m e n t sw i t ho t h e rc l a s s i ca l g o r i t h m ss u c ha sE D F , e t c ，i n d i c a t et h a tF I P Sh a sal o w e rp a c k e td r o pr a t ea n dh i g h e rs c h e d u l i n gS u c c e
15、s sr a t i o T h en e wa l g o r i t h mi nl o wl e v e ls c h e d u l i n gf i e l d si si n d e p e n d e n tw i t ht h et r a f f i cm o d e l s I tC a ne f f i c i e n t l yo v e r c o m et h es e r v i c el o s sc a u s e db yn o n u n i f o r mt r a f f i c B a s e do nt h eh a r d w a l ei n
16、d u s t r i a lb a c k g r o u n dt h a tt h el i m i t e db u f f e rC a l lb ei n t e g r a t e di n t oc r o s s - p o i n t s ，t h en e wa l g o r i t h mi sa b s o l u t e l yap r a c t i c a la l g o r i t h m W h i l et h eC I C Qs w i t c he m p l o y e dt h en e wa l g o r i t h m ，t h ee s t i m a t e dc o s to f f e rp o r tw h i c hs u p p o r t sO C l 9 2C a np r o m i n e n t l yr e d u c et o2 0 o ft h ee x i s t e n tc o s t T h ec o m p l e x i t yo
