Đề tài: Conservative Synchronization of Large-Scale Network Simulations (Đồng bộ thận trọng trong mô phỏng mạng truyền thông quy mô lớn)

ƯỜ

Ọ

Ộ

Ạ

T R

N G Đ I H C B Á C H K H O A H À N I

Ệ Ề Ệ VI N CÔNG NGH THÔNG TIN VÀ TRUY N THÔNG

Ậ Ớ

Ọ

BÀI T P L N MÔN H C

Ỹ

Ạ

Ậ Ỏ

Ệ CÁC K THU T HI N Đ I TRONG CNTT Ệ MÔ PH NG HI U NĂNG CAO

ề

Đ tài:

“Conservative Synchronization of LargeScale Network Simulations”

ộ ậ

ớ

ồ

ọ

ề

ạ

ỏ (Đ ng b th n tr ng trong mô ph ng m ng truy n thông quy mô l n)

ả ướ ẫ ạ Gi ng viên h ng d n ả : TS. Ph m Đăng H i

ự ọ ị ợ ồ ệ H c viên th c hi n : H Th L i (CA150114)

Đoàn Vũ Giang (CA150108)

ễ ề ị Nguy n Th Thu Huy n (CB140170)

Môn h cọ : Chuyên đ 2ề

ầ ọ Mã h c ph n : IT6190

Chuyên ngành ệ : Công ngh thông tin

Conservative Synchronization of LargeScale Network Simulations

ộ Hà N i: 8/2015

Conservative Synchronization of LargeScale Network Simulations

Ụ

M C L C

Ờ Ở Ầ 4 L I M Đ U ..............................................................................................................

Ổ 1. T NG QUAN 5 ............................................................................................................

Ớ Ệ 2. GI 5 I THI U BÀI BÁO ............................................................................................

6 3. PHÂN TÍCH CÁC MÔ HÌNH CMB .........................................................................

3.1. Null – message 7 .....................................................................................................

ậ 3.2. Thu t toán lazy CMB nullmessage: 8 ...................................................................

ố ư ậ 3.3. T i u hoá thu t toán lazy null – message 9 ..........................................................

ồ ộ ỏ ớ 11 3.4. Đ ng b hóa mô ph ng quy mô l n .................................................................

Ể Ự Ụ Ệ 4. ÁP D NG MÔ HÌNH PHÂN TÍCH NULL MESSAGE Đ D ĐOÁN HI U

Ỏ Ấ 11 SU T MÔ PH NG .....................................................................................................

ườ ơ ở 4.1. Mô hình đ 11 ng c s (Baseline) .......................................................................

ữ ả ị 12 4.2. Nh ng k ch b n khác nhau cho mô hình baseline ...........................................

ề ả ề ầ ầ ứ 13 4.3. N n t ng ph n c ng và ph n m m .................................................................

4.4. Ướ ượ c l ng Nullmessage 13 ..................................................................................

Ướ 4.5. ỉ ố c tính ch s Overhead 14 .................................................................................

ở ộ ủ ậ ả 15 4.6. Kh năng m r ng c a thu t toán CMB ..........................................................

Ỏ Ầ Ề 5. PH N M M MÔ PH NG NETWORK SIMULATION (NS) 16 ...............................

ớ ệ ầ ỏ 5.1. Gi ề 16 i thi u ph n m m mô ph ng NS ...............................................................

ố ượ ượ ỏ 5.2. Đ i t ng đ c mô ph ng: 17 .............................................................................

ự ể 5.3. Dùng C++ và Otcl đ xây d ng NS: 18 ...............................................................

ư ụ ấ 18 5.4. C u trúc cây th m c NS .................................................................................

ườ ủ 5.5. Môi tr 18 ng làm c a NS: ...................................................................................

Ậ Ế 19 6. K T LU N ..............................................................................................................

Ờ Ả Ơ 20 L I C M N ............................................................................................................

Conservative Synchronization of LargeScale Network Simulations

Ả Ệ TÀI LI U THAM KH O 21 ...........................................................................................

Ờ Ở Ầ L I M Đ U

ươ Mô ph ng tin h c (Computer simulation) là các ch

ọ ỏ ộ ệ ố

ộ ự ệ ỏ ể ệ ượ ừ ượ ự ế ng, các s ki n trong th c t

ờ ế ọ

ọ ỏ ụ ể ư ố ệ c mô ph ng b ng mô ph ng tin h c đã v

ượ ậ ượ ớ ng t

ặ ố ấ ọ ạ ng trình máy tính, m ng ủ ng c a m t h th ng c th thông máy tính đ mô ph ng m t mô hình tr u t ặ ố ệ ề ho c s li u đã có nh các đi u qua các hi n t ả ứ ọ ệ t, các ph n ng hoá h c, các quá trình sinh h c và các s li u kinh ki n th i ti ủ ự ệ ỏ ượ ằ ế t …. Quy mô c a s ki n đ t xa ử ụ ể ưở ể ấ ứ ề b t c đi u gì có th (ho c th m chí có th t ng) so v i cách s d ng ề mô hình toán h c truy n th ng gi y và bút.

ổ ề ữ ữ ả ớ ộ ộ

ấ ỏ

ả ệ ặ

Alfred Park, Kalyan S. Perumalla và đ c bi ả ự ứ ề ấ ố

ộ ậ ồ ọ ỏ ạ

ả ầ ượ ứ ề ộ

ứ Đã có r t nhi u nh ng bài báo, nh ng cu c h i th o l n trao đ i, nghiên c u ư ề v mô ph ng song song và phân tán nh Parallel and Distributed Simulation, Winter Simulation Conference, Computer Simulation Methods and Applications,… t là Richard M. Fujimoto Các tác gi ự ế ữ tích c c, đóng góp r t nhi u k t qu nghiên c u trong lĩnh v c là nh ng nhân t này. Trong đó có bài báo “Conservative Synchronization of LargeScale ề Network Simulations” (Đ ng b th n tr ng trong mô ph ng m ng truy n ỷ ế ủ thông quy mô l nớ ) đ ỏ c in trong K y u c a H i th o l n th 18 v mô ph ng ạ song song và phân tán (PADS'04), t p chí IEEE năm 2004.

ạ ậ ẽ ậ ớ ể ộ

ọ ơ ở ủ ề ề ậ

ậ ọ ượ c Trong ph m vi bài t p l n môn h c, ti u lu n s trình bày các n i dung đ ỏ ế ề ậ đ c p đ n trong bài báo, trên c s c a chuyên đ v các thu t toán mô ph ng song song th n tr ng.

Conservative Synchronization of LargeScale Network Simulations

1. T NG QUAN

Ổ

ự ệ ờ ạ ệ ậ ỏ ỹ ứ K thu t mô ph ng song song theo s ki n r i r c hi n nay đã cho phép ng

ứ ớ ề ạ ớ ớ ệ ụ d ng v i các mô hình m ng truy n thông quy mô l n (ch a t i hàng tri u thi ế ị t b

ế ị ể ấ ạ ỏ ố ầ đ u cu i và thi ệ t b chuy n m ch). Tuy nhiên, hi u su t mô ph ng song song có th ể

ử ụ ể ế ữ ậ ố ồ ộ ợ ị ả b gi m xu ng đáng k n u không s d ng nh ng thu t toán đ ng b thích h p.

ề ệ ư ữ ấ ả ộ N i dung bài báo đã đ a ra nh ng nét so sánh v hi u su t và kh năng m ở

ủ ậ ồ ộ ồ ộ ộ r ng c a 2 thu t toán synchronous (đ ng b ) và asynchronous (không đ ng b )

ứ ể ậ ạ ỏ ộ ọ trong mô ph ng m ng song song th n tr ng. Nhóm nghiên c u cũng phát tri n m t

ả ở ủ ể ệ ả ố ị mô hình phân tích đ đánh giá hi u qu và tính kh m c a các tham s xác đ nh

ậ ộ ổ ế trong m t thu t toán khá n i ti ng có tên là Nullmessage.

ữ ệ ự ứ ệ ằ ỉ Bài báo cũng ch rõ r ng d li u th c nghi m đã ch ng minh tính chính xác

ườ ệ ố ớ ệ ủ c a mô hình này. Vi c phân tích và đo l ng trên h th ng song song v i hàng trăm

ấ ằ ố ớ ử ả ạ ỏ ỏ ị ộ b vi x lý cho th y r ng đ i v i các k ch b n mô ph ng mô hình m ng thu nh có

ở ộ ậ ả ị ố ượ s l ng kênh vào / ra xác đ nh thì thu t toán nullmessage có kh năng m r ng t ố t

ố ượ ả ả ụ ố ị ể ơ h n kh năng gi m s l ng tính toán giá tr toàn c c t i thi u (global reduction)

ứ ồ ộ ự d a trên các giao th c đ ng b .

2. GI

Ớ Ệ I THI U BÀI BÁO

ự ự ỉ ộ ệ ầ ỏ ươ ị Mô ph ng song song ng m đ nh s th c hi n ch m t ch ỏ ng trình mô ph ng

ế ố ộ ậ ẽ ặ trên m t t p các processors k t n i ch t ch (máy tính song song).

ế ậ ở ậ ỏ Các ti n trình logic (LPs) trong mô ph ng song song b i các thu t toán th n

ẽ ả ả ọ ượ ề ắ tr ng s luôn đ m b o đ c nguyên t c causality, đi u đó có nghĩa là các message

ượ ở ế ượ ậ ự ử ủ ả ậ nh n đ c b i ti n trình này đ c x lý theo tr t t ờ không gi m c a nhãn th i

ồ ụ ộ ả ằ ế ả ồ gian. Tuy nhiên, không có gì đ m b o r ng các đ ng h c c b trong các ti n trình

ồ ờ ớ ồ ộ ỏ ậ khác nhau đã “đ ng gi ” v i nhau. Vì v y, đ ng b hóa trong mô ph ng cũng là đ ề

ượ ề ậ ứ ế ề ướ tài đ c đ c p đ n trong nhi u nghiên c u tr c đây.

ậ ậ ọ ượ ạ ồ ộ Các thu t toán th n tr ng đ c chia thành 2 lo i, đó là đ ng b và không

ầ ậ ộ ồ ộ ồ ộ ị ồ đ ng b . Các thu t toán không đ ng b không yêu c u đ ng b hóa giá tr GVT

ượ ể ừ ậ ậ (global vitua time). Thu t toán nullmessage (đ c phát tri n t ố thu t toán g c

ả ế ượ ỏ ế ắ ề ủ ấ ộ ChandyMisraBryant) đã gi i quy t đ ụ ể c v n đ h y b b t c là m t ví d đi n

ề ạ ậ ậ ồ ộ ồ ộ hình v thu t toán không đ ng b . Bên c nh đó, các thu t toán đ ng b hóa s ử

Conservative Synchronization of LargeScale Network Simulations

ộ ờ ể ố ể ụ d ng tính toán global redution đ tìm ra biên đ th i gian t i thi u (Lower Bound on

ể ượ ủ ệ ậ ở Timestamp LBTS) c a các thông đi p có th đ ỗ c nh n b i m i LP trong t ươ ng

ự ệ ượ ề ị ể ử ụ ằ lai, đi u đó giúp xác đ nh r ng khi nào các s ki n đ c an toàn đ x lý (ví d giao

ứ ậ ạ ử ụ ế ắ ệ ỹ ộ ố th c YAWNS). M t s thu t toán khác l ậ i s d ng các k thu t phát hi n b t c và

ậ ử ổ ờ ụ ồ ỹ ph c h i (deadlock detection and recovery) hay k thu t c a s th i gian (simulation

time windows).

ặ ướ ấ ủ ứ ề ệ M c dù tr ậ c đây đã có nhi u nghiên c u đánh giá hi u su t c a các thu t

ư ứ ế ề ầ ậ ộ ọ ồ ỏ toán đ ng b hoá th n tr ng, nh ng h u h t các nghiên c u này đ u mô ph ng trên

ử ự ứ ế ậ ậ ỏ ơ ộ quy mô nh (ít h n 100 b vi x lý). Do v y, k t lu n d a trên nghiên c u mô

ộ ị ụ ả ỏ ớ ố ớ ph ng đó không áp d ng đ i v i m t k ch b n quy mô l n.

ứ ả ữ ề ế Trong bài báo này nhóm nghiên c u đã gi ấ i quy t nh ng v n đ liên quan

ệ ậ ậ ộ ộ ớ ồ trong vi c so sánh m t thu t toán không đ ng b CMB nullmessage v i thu t toán

ạ ỏ ộ ớ ề ậ ề ồ đ ng b barier trong mô ph ng m ng truy n thông quy mô l n. Bài báo cũng đ c p

ầ ầ ậ ả ế đ n thu t toán lazy nullmessage (trình bày trong ph n 3). Ph n 4 mô t ả ị các k ch b n

ượ ử ụ ứ ự ệ ỏ mô ph ng đ ữ c s d ng cho các nghiên c u th c nghi m, và trình bày so sánh gi a

ườ ữ ệ ự ầ ự d đoán mô hình phân tích và đo l ệ ng. Ph n 5 trình bày các d li u th c nghi m

3. PHÂN TÍCH CÁC MÔ HÌNH CMB

ượ ấ ủ ệ ậ ậ đ c so sánh hi u su t c a thu t toán CMB và thu t toán global reduction.

ự ự ậ ả Thu t toán CMB (Chandy – Misra – Briant) xây d ng d a trên các gi thi ế t

ề ế v ti n trình logic:

ổ ớ ử ụ ừ ộ Các LPs s d ng m t kênh vào riêng cho t ng LP khác có trao đ i v i nó.

ồ ờ ộ ồ ị ươ ỗ ứ M i kênh vào là FIFO, có m t đ ng h th i gian mà giá tr t ớ ng ng v i

ệ ở ầ ế ặ ờ ủ nhãn th i gian c a: thông đi p ệ đ u kênh vào (n u có) ho c thông đi p

ậ ượ ố ợ ỗ ế cu i cùng nh n đ c (n u hàng đ i r ng)

ệ ổ ờ LPs trao đ i các thông đi p có nhãn th i gian.

ạ ạ ấ ộ C u hình m ng tĩnh, không t o các LPs đ ng.

ượ ử ậ ự ờ ỗ Các message đ c g i trên m i link theo tr t t th i gian.

ườ ứ ự ượ ử ệ ề ế ậ Đ ng truy n là tin c y, các thông đi p đ n theo đúng th t c g i. đ

ụ ả ả ậ ớ ự ệ ỗ Thu t toán v i m c đích đ m b o x lý

ạ ỗ ế ử các s ki n trong m i LP theo tr t ậ ệ ư ự ờ t th i gian, t ẽ ự i m i ti n trình s th c hi n nh sau:

Conservative Synchronization of LargeScale Network Simulations

ư ế ỏ WHILE (mô ph ng ch a k t thúc)

{

ớ ứ ấ ỗ ợ ộ ợ Đ i cho t i khi m i hàng đ i FIFO ch a ít nh t m t msg

ấ ự ệ ấ ỏ ờ ỏ ợ L y s ki n có nhãn th i gian nh nh t ra kh hàng đ i

ự ệ ử X lý s ki n này

}

ENDLOOP

ể ễ ạ ấ ậ ộ Thu t toán có th d dàng cho th y không vi ph m ràng bu c causality, các

ẽ ượ ử ậ ự ờ message s luôn đ c x lý đúng theo tr t t th i gian, tuy nhiên l ạ ấ ễ ơ i r t d r i

ỗ ế ế ắ ề ở ộ ạ vào b t c khi mà trong m t chu trình, m i ti n trình đ u trong tr ng thái đang

ờ ợ ừ ế ể ả ế ấ ề ậ ộ ch đ i m t message t ti n trình khác. Đ gi i quy t v n đ thu t toán null –

3.1. Null – message

ượ ử ụ message đ c s d ng.

ướ ể ể ỉ ứ ế ộ ờ Tr c h t, có th hi u null – messge là m t message ch ch a nhãn th i gian

ỡ ự ế ắ ử ụ ụ ự ệ ậ ậ và m c tiêu khi s d ng chính là g s b t c khi th c hi n thu t toán th n

ơ ế ử ụ ơ ả ề ạ ằ ọ ờ tr ng c b n CMB b ng cách lan truy n th i gian nhân t o. C ch s d ng null

ấ ơ ẽ ử ể ả ộ ỗ ỉ ờ – message r t đ n gi n: m i LP s g i m t null message đ ch ra nhãn th i

ấ ủ ẽ ử ấ ộ ươ gian th p nh t c a m t messages mà nó s g i trong t ng lai

ậ ớ ả ế Thu t toán CMB c i ti n v i null – message:

ư ế ỏ WHILE (mô ph ng ch a k t thúc)

{

ớ ứ ấ ỗ ợ ộ ợ Đ i cho t i khi m i hàng đ i FIFO ch a ít nh t m t msg

ấ ự ệ ấ ỏ ờ ỏ ợ L y s ki n có nhãn th i gian nh nh t ra kh hàng đ i

ự ệ ử ỉ ử ế ử null message không x lý, ch g i ti p) X lý s ki n này (

ử ớ ữ ờ i nh ng LPs lân c n G i t ấ ậ các null messages mang nhãn th i gian th p

ủ ủ ẽ ượ ươ ộ nhât c a c a m t message s đ ử ế c LP này g i đ n trong t ng lai (Giá

ờ ộ ị ờ ệ ớ ị tr th i gian hi n th i c ng v i giá tr lookahead)

}

ENDLOOP

Conservative Synchronization of LargeScale Network Simulations

ỡ ế ế ắ ủ ấ ậ ậ Có th ể th y ngay thu t toán nullmessage đã tháo g th b t c c a thu t

ậ ạ ụ ộ ị toán CMB, tuy nhiên thu t toán này l i ph c thu c vào giá tr lookahead và t ừ

ụ ệ ẽ ề ề ấ ả ộ ả ư ế vi c ph c thu c này s phát sinh thêm nhi u v n đ ph i gi i quy t nh : giá tr ị

ứ ộ ẽ ạ ỏ ớ ị ẫ lookahead = 0, giá tr lookahead quá nh hay m c đ r nhánh m ng quá l n d n

ề ề ệ ồ ớ ế đ n phát sinh quá nhi u null – message , đi u đó cũng đ ng nghĩa v i vi c h ệ

ấ ệ ố ả ử ệ ề ố ỏ th ng ph i x lý quá nhi u nullmessage, hi u su t h th ng mô ph ng không

ư ế ể ự ả ậ ượ ợ ị cao. V y ph i làm nh th nào đ d đoán đ ộ c giá tr lookahead phù h p, m t

ụ ậ ắ ổ ượ ủ ể ượ ờ ố s thu t toán b sung kh c ph c nh c đi m c a nullmessage đ c ra đ i.

ậ

3.2. Thu t toán lazy CMB nullmessage:

ớ ủ ả ộ ượ ờ ậ M t phiên b n m i c a thu t toán CMB lazy CMB đ c ra đ i, lazy CMB

ế ố ượ ẽ ạ ệ ố ử ằ nullmessage s h n ch s l ng null message g i đi trong h th ng b ng cách

ỉ ử ầ ế ụ ể ạ ế ỉ ử ch g i chúng khi c n thi ố t. C th , các null message ch g i khi LP đ t đ n cu i

ử ủ ặ ờ ị ỉ ườ ứ th i gian x lý an toàn c a nó, t c là ch khi LP b ch n. Trong tr ợ ng h p này,

ệ ố ể ẫ ế ắ ử ế ậ ế n u không g i null message thì h th ng có th d n đ n b t c. Thu t toán lazy

CMB nullmessage s :ẽ

ờ ợ ướ ử ộ • Đ i m t th i gian c khi g i nullmessage (cid:0) tr

ỉ ử ầ • Ch g i message khi c n thi ế t

ử ấ ả ử – Khi đã x lý t ờ ợ t c các msg an toàn, g i nullmessage và ch đ i

ậ ượ ẽ ượ ướ ờ – Khi nh n đ c nullmessage, s tính đ ậ c c n d i nhãn th i gian

ế ủ c a message ti p.

ủ ậ Hình 1: Runtimes c a thu t toán Lazy CMB

ử ụ ậ ấ ỏ Hình 1 cho th y quá trình mô ph ng s d ng thu t toán Lazy CMB (gi ả ử s

ư ớ ị ự các LP có cùng lookahead) v i các giá tr "LBTS" nh trên thì lazy null message th c

Conservative Synchronization of LargeScale Network Simulations

ệ ươ ự ư ủ ờ ướ ộ ố ượ ớ ố hi n t ng t ỏ nh c a mô ph ng th i gian b c. V i m t s l ng t ể ủ i thi u c a

ơ ồ ữ ổ ươ ự ư ỏ các null message trao đ i gi a các LP, s đ này t ng t ồ nh là mô ph ng đ ng

ườ ố ượ ể ɸ ượ ử ư ộ b . Ng i ta có th tính toán s l ng null message N đ c g i đi nh sau:

(1)

ố ượ ố ượ ầ ỗ Trong đó m là s l ng LP, n là s l ng các kênh đ u ra m i LP, và s là

ố ượ ủ ề ạ ờ ỏ ệ chi u dài c a th i gian ch y trong mô ph ng. S l ử ổ ự ng các c a s th c hi n (s

ượ ở ế ố ặ ờ ướ đ c chia b i lookahead), cho bi t s vòng quay ho c th i gian b ữ c cho nh ng

ượ ử null message đ c g i đi.

ứ ằ ớ ổ Vd v i: m = 8, n = 2, s = 25, và lookahead = 0,2 giây. B ng công th c 1, t ng

ể ẽ ầ ố s null message s là 2.000. Khái quát hoá, chúng ta có th tính toán g n đúng s ố

ψ ổ ố ượ ắ ồ ộ ầ ằ ượ l ng tin nh n đ ng b hóa (N ) khi thay đ i s l ng đ u vào b ng ph ươ ng

ả ử ộ ộ ố ủ trình (gi s m là m t b i s c a 2):

(2)

ố ư

ậ

3.3. T i u hoá thu t toán lazy null – message

ể ố ư ể ử ụ ậ ươ Đ t i u hoá thu t toán lazy nullmessage có th s d ng các ph ng pháp

ẽ ử ử ỗ ỗ ơ ỳ ị ờ G i nullmessage theo chu k : m i LP s g i nullmessage m i f đ n v th i

ướ ỏ ơ ủ ỏ ị ị gian tr c khi mô ph ng (trong đó giá tr f nh h n giá tr lookahead c a các

ả ế ằ ấ ử ầ ớ LP, gi thi t r ng các LP có cùng lookahead). V i cách tăng t n su t g i null

ớ ượ ế ắ ủ ệ ố ạ message t ế ậ ẽ i các LP k c n s tránh đ c tình tr ng b t c c a h th ng.

ạ ỏ ớ ờ ả ử ừ ử Lo i b b t các nullmessage có cùng nhãn th i gian: Gi s 1 LP v a g i đi

ầ ờ ế 1 nullmessage có nhãn th i gian t, thì ngay sau đó nó không c n thi ả t ph i

ư ậ ờ ữ ử g i đi thêm 1 nullmessage nào khác có cùng nhãn th i gian t nh v y n a

ỉ ầ ượ ử ầ ừ ờ (các nullmessage có cùng nhãn th i gian ch c n đ c g i đi 1 l n t 1 LP).

ừ ố ư ươ ể ượ ử ổ ư ệ T 2 bi n pháp t i u trên, ph ng trình 1 có th đ c s a đ i nh sau:

Conservative Synchronization of LargeScale Network Simulations

(3)

ị ủ ầ ấ ỏ Trong đó c là t ỷ ệ l nullmessage b h y b và f là t n su t các nullmessage

ượ Ở ị ượ ử ụ ở ị ủ đ ử c g i đi. đây, giá tr f đ c s d ng ị v trí c a giá tr lookahead trong

ươ ph ng trình 1.

ờ ườ ợ ổ ủ ơ Bây gi ể chúng ta chuy n sang các tr ng h p t ng quát h n c a lookahead

ấ ữ ự ề ể ầ ồ ộ không đ ng đ u trên các kênh đ u ra. Nó r t h u ích đ xây d ng m t mô hình

ỏ ườ Ở phân tích mà các mô hình mô ph ng là không th ng xuyên. đây, chúng ta gi ả

ộ ượ ế ị ị đ nh m t giá tr lookahead đ ỗ c gán cho m i liên k t.

ườ ủ ợ ỗ ị Trong tr ng h p c a các giá tr lookahead là khác nhau trên m i LP, công

ể ượ ử ổ ứ ươ th c 3 có th đ c s a đ i thành ph ng trình:

(4)

ươ ấ ử ầ ớ ị Ph ng trình 14 v i các giá tr lookahead và t n su t g i null message cho

ượ ố ẽ ử ỏ ố phép ướ ượ c l ng đ c s null message s g i đi trong su t quá trình mô ph ng.

ộ ế ố ấ ọ Tính toán đ ượ ố ượ c s l ng null message là r t quan tr ng vì nó là m t y u t quan

ể ậ ọ ị tr ng đ tính toán giá tr overhead trong thu t toán null message.

ươ ỉ ố ậ Ph ng trình 5 tính toán ch s overhead trong thu t toán lazy null messge. Ở

ố ượ ế ố ừ ố ượ ầ ừ đây a là s l ng k t n i t xa, p là t ỷ ệ l ph n trăm và w là s l ạ ng t ng lo i

ế ố ườ ề ế ố ụ ể ố ượ k t n i c th . S l ng w này là y u t thông th ụ ế ng truy n thông. Ví d , n u

1) và Ethernet (w2), có th là wể

ế ố ả ộ ớ chúng ta có k t n i trên c b nh dùng chung (w

= 1 và w2 = 10.

ữ ằ ươ ỉ ử ụ B ng cách s d ng nh ng ph ng trình này, chúng ta không ch tính toán

ượ ử ấ ả ượ đ ượ ố ượ c s l ng null message đ c g i qua t t c LP, mà còn tính đ c giá tr ị

ủ ề ả ậ ỏ ị ấ ớ ừ overhead c a thu t toán null message v i t ng k ch b n mô ph ng. Đi u này r t

ệ ự ấ ủ ộ ị ụ ệ ả ớ ữ h u ích trong vi c d báo hi u su t c a m t k ch b n baseline m i (ví d nh ư

ệ ỏ các thí nghi m nh ).

Conservative Synchronization of LargeScale Network Simulations

ớ

ỏ

ộ

ồ

3.4. Đ ng b hóa mô ph ng quy mô l n

ư ươ ươ ở ỉ ằ L u ý r ng ph ng trình (1) và ph ng trình (2) trên ch khác nhau ở ệ ố h s

ượ ố ớ ả ờ n trong (1) đ ằ c thay b ng log ậ 2m trong (2). Đ i v i thu t toán qu n lý th i gian

2m, so v i t l

ộ ố ượ ỉ ệ ắ ộ ồ ậ ồ đ ng b , s l ng tin nh n đ ng b hóa tăng t l ớ thu n v i mlog ớ ỉ ệ

ữ ậ ơ ờ ồ ị ắ ủ c a m trong thu t toán CMB. H n n a, giá tr này không bao g m th i gian ng t

ạ ồ ệ ố ẽ ờ ờ ộ ở ộ và kh i đ ng l i đ ng th i toàn b các LP trong h th ng (th i gian này s tăng

ố ượ ế ả ầ ị tuy n tính khi s l ờ ng LP tăng), góp ph n tăng giá tr overhead qu n lý th i

ố ớ ẽ ượ ề ấ ỗ ậ ả gian đ i v i m i phép tính LBTS. V n đ này s đ ớ ế c th o lu n thêm v i k t

ả ệ ầ ấ qu hi u su t trong ph n 4.5

4. ÁP D NG MÔ HÌNH PHÂN TÍCH NULL MESSAGE Đ D ĐOÁN

Ể Ự Ụ

Ỏ Ấ Ệ HI U SU T MÔ PH NG

ạ ộ ủ ự Các mô hình phân tích trên đây cho phép d báo ho t đ ng c a nullmessage

ỉ ố ể ượ ử ụ ể ự ệ ị ữ và giá tr overhead. Nh ng ch s này có th đ ấ c s d ng đ d báo hi u su t

ẽ ướ ầ ỏ ủ c a các mô hình mô ph ng khác nhau. Đ u tiên chúng ta s ạ ộ c tính ho t đ ng

ệ ố ỏ ị ớ ủ c a nullmessage và giá tr overhead trên h th ng mô ph ng, sau đó so sánh v i

ỉ ố ự ế ệ ế ạ ả ự ầ các ch s đo đ c th c nghi m. Các ph n sau đây liên quan đ n k t qu th c

ệ ỗ ươ ứ ậ ớ nghi m (m i LP t ộ ng ng v i m t CPU v t lý).

4.1. Mô hình đ

ườ ơ ở ng c s (Baseline)

ử ụ ứ ẩ ượ ể ạ Nhóm nghiên c u đã s d ng các tiêu chu n đ c phát tri n t ạ ọ i Đ i h c

ư ộ ậ ể ợ ỏ Dartmouth nh m t t p h p các mô hình baseline đ mô hình hóa và mô ph ng

ạ ấ ộ ồ ượ ạ ứ ể m ng c ng đ ng [22]. C u hình baseline này đ c t o ra đ ch ng minh kh ả

ở ộ ủ ầ ạ ạ ỗ ượ ọ ỏ năng m r ng m ng mô ph ng. M i ph n c a m ng đ ộ c g i là m t Campus

Network (CN).

ế ấ ấ ồ ỗ ủ Hình 4 cho th y các c u trúc liên k t cho CN. M i CN bao g m 4 máy ch ,

ế ị ủ ổ ế ồ ỗ ố ị 30 thi t b đ nh tuy n, và 504 máy ch (t ng s là 538 nút). M i CN bao g m 4

ạ ệ ồ ế ị ế ị m ng con (subnetwork) riêng bi t. Net 0 bao g m 3 thi t b đ nh tuy n, có nút

ủ ồ ồ 0:0 là router gateway cho CN. Net 1 g m 2 router và 4 máy ch . Net 2 g m 7

ộ ị ứ ế ế tuy n, 7 router LAN, và 294 khách hàng. Net 3 ch a 4 b đ nh tuy n, 5 thi ế ị t b

ế ạ ị đ nh tuy n m ng LAN, và 210 khách hàng.

Conservative Synchronization of LargeScale Network Simulations

0:2

1:0

To other CNs

1:2

1:3

0:1

0:0

Net 0

1:4

1:1

1:5

Net 1

2:0

2:1

3:0

3:1

2:2

2:3

2:4

2:5

3:2

3:3

2:6

Net 2

Net 3

Hình 4: Campus Network

ấ ả ủ ế ể ề ả ố T t c các liên k t máy ch không ph i đi m cu i (nonend host) đ u có

ề ướ ề ộ ễ băng thông là 2Gb/s và đ tr truy n thông (delay) d i 5ms (riêng truy n thông

ố ượ ế ố ữ ế gi a Net 0 đ n Net 1 có delay là 1ms). Host cu i đ ớ c k t n i pointtopoint v i

ươ ứ ạ router m ng LAN t ng ng có băng thông 100MB/s và delay là 1ms.

ể ượ ề ế ố ớ ộ ấ ể ạ Nhi u CN có th đ ế c k t n i v i nhau đ t o thành m t c u trúc liên k t

ơ ở ể ễ ủ ạ ấ vòng. Chính tính ch t này c a m ng cho phép các mô hình c s đ d dàng thay

ướ ở ộ ỏ ổ đ i kích th c (thu nh hay m r ng quy mô).

4.2. Nh ng k ch b n khác nhau cho mô hình baseline

ữ ả ị

ứ ư ả ấ ớ ị ươ ả Nhóm nghiên c u đã đ a ra 5 k ch b n v i 5 c u hình t ệ ự ng ph n. Vi c l a

ổ ộ ễ ủ ề ế ạ ẫ ọ ch n máy ch ng u nhiên, thay đ i đ tr lan truy n trên m ng liên k t vòng và

ả ử ụ ế ẽ ạ ụ ứ ổ ị thay đ i các c m liên k t s t o ra các k ch b n s d ng trong nghiên c u này.

ả ị ư ượ K ch b n L u l ng ặ Chord? Đ c tính khác

Baseline Std. No None

BaselineR Rand. No None

Baseline2ms Rand. No Single 2ms ring link

ChordR Rand. Yes None

ChordAsym Yes Asym. Chord delays

Rand. ả B ng 1. Benchmark Scenarios

Conservative Synchronization of LargeScale Network Simulations

ề ả ề ầ

4.3. N n t ng ph n c ng và ph n m m ầ ứ

ề ề ầ ầ ỏ ỏ Ph n m m mô ph ng song song / phân tán (PDNS) là ph n m m mô ph ng

ề ạ ả m ng trên n n t ng HLA RTI ( High Level Architecture & using RunTime

ượ ứ ế ắ ồ Infrastructure based). Các PDNS đ c nh c đ n trong nghiên c u này g m có:

NS2, libSynk,..

ề ầ ồ ở ỏ ạ NS2 (Network Simulator 2): là ph n m m mã ngu n m mô ph ng m ng

ể ự ệ ẽ ướ ề ố ượ ượ ể ạ đi u khi n s ki n riêng r h ng đ i t ng, đ c phát tri n t i UC Berkely,

ế ằ ữ ề ạ vi ấ t b ng ngôn ng C++ và Otcl ch y trên n n Windows 32 và Linux. NS r t

ệ ạ ạ ỏ ố ệ ộ ữ h u ích cho vi c mô ph ng m ng di n r ng (WAN) và m ng local (LAN). B n

ả ể ế ấ ủ ể ả ớ ổ ị ợ l ủ i ích l n nh t c a NS2 ph i k đ n là: Kh năng ki m tra tính n đ nh c a

ồ ạ ứ ạ ứ ả ạ các giao th c m ng đang t n t ớ i; Kh năng đánh giá các giao th c m ng m i

ướ ử ụ ư ự ữ ả ạ ớ tr ầ c khi đ a vào s d ng; Kh năng th c thi nh ng mô hình m ng l n mà g n

ể ự ư ượ ự ế ề ả ỏ nh ta không th th c thi đ c trong th c t ạ ; Kh năng mô ph ng nhi u lo i

ạ m ng khác nhau.

ư ệ ế ố ả ờ libSynk: là th vi n qu n lý các k t n i và th i gian. libSynk đ ượ ử ụ c s d ng

ả ố ỏ ể đ qu n lý các tình hu ng trong mô ph ng song song và phân tán, nó cũng đ ượ c

ớ ữ ế ố ể ề ể ộ ử ụ s d ng đ phân chia b nh gi a các k t n i SMP và TCP/IP đ truy n thông

4.4.

qua SMPS.

Ướ ượ c l ng Nullmessage

ử ụ ể ượ ướ ậ S d ng các mô hình phân tích cho thu t toán CMB có th đ c c tính

ệ ố ẽ ử ả đ ượ ố ượ c s l ấ ố ệ ng Nullmessage s g i đi trong h th ng. B ng 2 cho th y s li u

ướ ớ ố ệ ự ả ạ ị ỏ ệ c tính cùng v i s li u đo đ c th c hi n trên các k ch b n baseline mô ph ng

ả ị song song. Trong k ch b n này có s = 25; lookahead = 0,2; f = ( 0,2/3 ); n = 2; c =

0,5 .

Nullmessage ướ ượ c l ng Nullmessage đo đ cạ

ố ượ S l ng CPUs

4 1,500 1,424

8 3,000 2,974

16 6,000 6,064

32 12,000 11,890

Conservative Synchronization of LargeScale Network Simulations

64 24,000 23,586

128 48,000 48,628

256 96,000 96,034

512 192,000 193,862

ả B ng 2. Ướ ượ c l ng s l ố ượ Null message ng

ấ ằ ố ệ ủ ả ứ S li u trên B ng 2 cho th y r ng mô hình phân tích c a nhóm nghiên c u

ố ượ ố ệ ự ệ ự d đoán khá chính xác s l ng nullmessage. S chênh l ch s li u gi a ữ ướ c

ố ệ ụ ộ ượ l ỏ ng và s li u mô ph ng ph thu c vào t l ỉ ệ ữ ố ượ gi a s l ng nullmessage đ ượ c

ố ượ ể ự ị ủ ư ỏ ử g i đi và s l ầ ng nullmessage b h y b . G n nh không th d đoán chính

ố ệ ướ ượ ư ớ ố ệ ầ xác đ ượ ỉ ệ c t l này, nh ng s li u c l ng cũng đã khá g n v i s li u th c t ự ế

ỏ đo đ c đ ạ ượ ừ ệ c t vi c mô ph ng.

4.5.

Ướ ỉ ố c tính ch s Overhead

ả ướ ừ ế ố ượ ượ ử T các k t qu c tính s l ng nullmessage đ ư c g i đi nh trên, cùng

ươ ượ ế ậ ể ể ướ ụ ớ v i ph ng trình 3 đã đ c thi t l p trong m c 3.3, chúng ta có th đ c tính

ỗ ị ả ỏ ị giá tr overhead cho m i k ch b n mô ph ng.

ứ ư ệ ớ ộ Nhóm nghiên c u cũng đã đ a ra m t khái ni m m i “Packet Transmissions

ố ượ ượ ử per Second of wallclock time” (PTS): là s l ng gói tin đ c x lý trong 1 giây

ố ượ ượ ừ ớ ủ c a wallclock hay s l ng gói tin đ ề c truy n đi t nút này t i nút khác trong

ạ ệ ố h th ng m ng.

ị ườ ớ ợ ỏ ượ Giá tr overhead và PTS trong tr ng h p mô ph ng v i 32 CPU đ c th ể

ệ ả ố ế ằ ố ệ hi n trong B ng 3. S li u th ng kê cũng cho bi ử t r ng 28 CPU (87,5%) đã g i

ộ ệ ộ ớ ạ tin nullmessage thông qua b đ m b nh dùng chung và 4 CPU còn l i (12,5%)

ử ụ ứ ế ị giao ti p thông qua giao th c TCP / IP trên Ethernet. S d ng các giá tr m = 32,

ỉ ố ị ả ơ ả p1 = 0,875, p 2 = 0,125, W1 = 1, và w2 = 10, ch s overhead cho k ch b n c b n

là 6,25.

ả ị ỉ ố K ch b n Ch s Overhead PTS

Baseline 6.25 1,512,410

BaselineR 8.52 865,385

Baseline2ms 10.54 621,008

ChordR 9.43 699,848

Conservative Synchronization of LargeScale Network Simulations

ChordAsym 12.21 684,630

ả Ướ ượ c l ng ch s B ng 3. ỉ ố Overhead

4.6. Kh năng m r ng c a thu t toán CMB

ở ộ ủ ậ ả

ậ ằ ầ ỉ ươ Trong ph n 3.3, chúng tôi đã ch ra r ng, thu t toán Nullmessage t ố ng đ i

ổ ị ướ ứ ỏ n đ nh khi tăng kích th c mô hình mô ph ng. Chúng tôi cũng đã ch ng minh

ự ệ ả ớ ị ườ ơ ở ư ớ ằ b ng th c nghi m v i cùng k ch b n Baseline (đ ng c s ). Nh ng v i các

ộ ấ ả ủ ụ ệ ề ậ ả ị k ch b n khác, hi u qu c a thu t toán nullmessages ph thu c r t nhi u vào

ự ả ị kh năng d báo giá tr lookahead.

ố ượ S l ng CPUs Null Messages Reductions

784 736 16

783 747 32

787 892 128

ả ỏ ị . Mô ph ng cho k ch b n Baseline B ng 4ả

ư ủ ầ ậ ờ ỏ ổ ỏ Th i gian mô ph ng c a thu t toán CMB g n nh không đ i khi mô ph ng

ừ ụ ả ờ ớ v i quy mô t 16128 VXL (xem B ng 4), trong khi đó th i gian toàn c c (global

ạ ề ố ượ ặ ừ ế redutions) l i đ u đ n tăng theo s l ng CPU (t 16 đ n 128 CPU). Hình 5 cho

ộ ớ ị ấ ự ổ ủ ả ứ ồ th y s thay đ i c a 2 giao th c đ ng b v i k ch b n Baseline

ố ượ S l ng CPUs Null Messages Reductions

420 508 64

414 523 128

420 563 256

436 620

ớ ớ ị ả ỏ 512 ả Mô ph ng mô hình l n v i k ch b n Baseline B ng 5.

ế ả ỏ Đây là k t qu mô ph ng trên máy Compaq Alpha Tru64 cluster.

ươ ứ ượ ể ệ ả ị Giá tr PTS t ng ng đ ử ụ ị c th hi n trong hình 6. K ch b n baseline s d ng

ị ươ ứ ớ ỏ giá tr global reductions tăng theo hàm mũ t ng ng v i quy mô mô ph ng.

ậ ố ổ ờ ị Ng ượ ạ c l i, thu t toán nullmessage l ạ ươ i t ạ ng đ i n đ nh trong th i gian ch y

ệ ế ấ hi u su t lên đ n 512 CPU.

Conservative Synchronization of LargeScale Network Simulations

Hình 5. Đánh giá PTS theo quy mô mô ph ngỏ

Hình 6. PTS trong mô hình l nớ

5. PH N M M MÔ PH NG NETWORK SIMULATION (NS)

Ỏ Ầ Ề

ớ

ỏ

ệ

ầ

5.1. Gi

ề i thi u ph n m m mô ph ng NS

ươ ề ầ ạ ướ NS (Network Simulation) ch ng trình ph n m m d ng h ng đ i t ố ượ ng

ượ ử ụ ỏ ạ ự ệ ệ ố ạ ả đ ể c s d ng đ mô ph ng l i các s ki n x y ra trong h th ng m ng.

ượ ử ụ ự ể ạ ỏ ỏ NS đ ớ c s d ng đ mô ph ng LAN và WAN, th c thi mô ph ng m ng l n

ề ạ ạ và nhi u lo i m ng khác nhau

ệ ượ ạ ọ ừ ỏ H mô ph ng NS2 đ c phát tri n ể ở ườ tr ng đ i h c Berkeylay t năm 1989,

ự ủ ầ ộ ệ là m t ph n trong d án VINT (Virtual Internet Testbed) c a phòng thí nghi m

ố qu c gia Lawrence Berkeley

Conservative Synchronization of LargeScale Network Simulations

ề ổ ướ ộ ườ T ng quan v NS d i góc đ ng i dùng ả Hình nh:

ị (cid:0) OTcl Script ả K ch b n OTcl

(cid:0) ươ Simulation Program Ch ng trình Mô phòng

ở ộ ộ ị ướ (cid:0) OTcl B biên d ch Tcl m r ng h ng đ i t ố ượ ng

ư ệ ỏ (cid:0) NS Simulation Library Th vi n Mô ph ng NS

(cid:0) ố ượ ộ ậ ị ự ệ Event Scheduler Objects Các đ i t ng B l p l ch S ki n

ố ượ ầ ạ (cid:0) Network Component Objects Các đ i t ng Thành ph n M ng

ợ ế ậ ạ (cid:0) Network Setup Helping Modules Các mô đun Tr giúp Thi t l p M ng

(cid:0) Plumbling Modules Các mô đun Plumbling

(cid:0) ế ỏ Simulation Results ả Các k t qu Mô ph ng

(cid:0) Analysis Phân tích

ạ ọ (cid:0) NAM Network Animator Minh h a M ng NAM

ố ượ

ượ

ỏ

5.2.

Đ i t

ng đ

c mô ph ng:

Wired, Wireless, Satellite

TCP Agents, UDP Agents, multicast, unicast

ợ ạ ộ ị ư ế ả ế ế t k các c ch qu n lý hàng đ i t i b đ nh tuy n nh DropTail, Thi

ơ ế Fair Queueing, Red.

ặ ị ả ộ ng đ ng và tĩnh, Dijkstra, vector kho ng cách,

ậ Cài đ t thu t toán đ nh đ ạ ườ ế ậ thu t toán tr ng thái liên k t,

Conservative Synchronization of LargeScale Network Simulations

ỗ ợ ứ ụ H tr các ng d ng WebCache, FTP, Telnet, CBR, Web, Real Audio.

ự

ể

5.3.

Dùng C++ và Otcl đ xây d ng NS:

ệ ượ ế ỏ H mô ph ng NS đ c vi t trên C++ và Otcl, ữ ệ ể ử C++ dùng đ x lý d li u,

ề ượ ử ụ ể ị ạ ấ ỏ các thao tác v gói tin và Otcl đ c s d ng đ đ nh d ng c u hình mô ph ng,

ể ề ỏ đi u khi n mô ph ng.

ể ả ệ ạ ả ờ ớ ể ệ Đây là lí do đ h mô ph ng ử ỏ NS đ t hi u qu . Đ gi m b t th i gian x lý

ữ ỏ ự ệ ự ệ gói tin và nh ng s ki n trong mô ph ng, t ấ ả ề ượ t c đ u đ c th c hi n trên C++.

ư ụ

ấ

5.4.

C u trúc cây th m c NS

ườ

ủ

5.5. Môi tr

ng làm c a NS:

ể ự ệ ạ ỏ ộ ướ ở ạ ế ả Đ th c hi n mô ph ng m t mô hình m ng tr c h t ta ph i kh i t o các

ụ ế ề ị ườ ố ượ đ i t ng, các liên k t, các Agent, các d ch v truy n tin... trên môi tr ng NS,

ỗ ợ ở ạ ố ượ ề ả ơ và đi u này khá đ n gi n vì NS đã h tr cách kh i t o ra các đ i t ng này.

ố ượ ư ế ị ở ạ Sau khi kh i t o các đ i t ng nh nút(node), liên k t(link), các Agent, các d ch

ề ệ ạ ươ ứ ẽ ượ ụ v truy n tin... thì đo n mã l nh t ng ng s đ ệ ấ c phát sinh. C u trúc câu l nh

ể ử ụ ể ạ ả ơ ộ ủ c a NS cũng khá đ n gi n chúng ta cũng có th s d ng nó đ t o ra m t mô

hình theo ý mu n. ố

Conservative Synchronization of LargeScale Network Simulations

ẽ ị ự ệ ạ ỏ ị Sau khi th c hi n mô ph ng mô hình m ng trên NS, trình biên d ch s d ch

ươ ả ượ ư ế ỏ ướ ạ ch ng trình chúng ta đã mô ph ng, k t qu đ c l u d i d ng file NAM.

ễ ử ụ ể ề ệ ộ ươ NAM có m t giao di n d s d ng (có các nút đi u khi n ch ư ng trình nh :

ể ự ệ Play, Stop, FastForward, Rewind, Pause... ), chúng ta có th th c hi n ch ươ ng

ị ướ ạ ườ ễ ộ trình đã biên d ch d i d ng file NAM trong môi tr ng NAM m t cách d dàng.

ị ờ ự ệ ươ ể Trên màn hình luôn luôn hi n th th i gian th c hi n ch ề ố ộ ng trình, t c đ truy n

ư ượ ề gói tin. Ngoài ra nó còn có màn hình quan sát l u l ng gói tin truy n đi và s ố

ỏ ườ ờ ề ẽ ạ ộ ượ l ng gói tin r i kh i đ ả ng truy n khi có đ trì hoãn cao hay ngh n m ch x y

ra trên m ng.ạ

6. K T LU N

Ậ Ế

ậ ộ Bài báo trình bày m t mô hình phân tích cho thu t toán lazy null message

ộ ể ồ ờ ươ ượ ề ấ ả không đ ng b đ qu n lý th i gian. Các ph ng trình đ c đ xu t trong bài

ể ượ ử ụ ố ượ ị báo có th đ ể c s d ng đ tính toán s l ng nullmessage và giá tr overhead

ụ ể ỉ ố ứ ự ượ ệ ố ư ươ t ng ng. C th , ch s overhead cho phép d đoán đ c vi c t i u hóa

ư ầ ậ ị ể ế thu t toán nullmessage, giá tr overhead h u nh tăng lên không đáng k n u

ư ầ ủ ư ỏ ớ ổ ỏ ị nh đ u vào/ra c a các kênh n đ nh (nh mô ph ng v i quy mô nh ).

ế ạ ấ ậ ộ ộ Thu t toán nullmessage cũng r t linh đ ng cho các mô hình m ng bi n đ ng

ố ứ ậ ố ư ể ồ ộ và không đ i x ng. Thu t toán t i u hóa CMB có th đ ng b hóa các message

ử ớ ị ế ố ụ ộ ứ ấ theo giá tr lookahead g i t i các k t n i c c b . Các tính ch t này ch ng minh

ớ ủ ế ậ ạ ỏ đ ượ ợ c l i th trong mô ph ng m ng quy mô l n c a thu t toán CMB.

Conservative Synchronization of LargeScale Network Simulations

Ờ Ả Ơ L I C M N

ề ệ ạ ậ ọ ỏ ớ ỹ ệ Môn h c các k thu t hi n đ i trong CNTT v i chuyên đ Mô ph ng hi u

ữ ứ ế ế ớ ươ năng cao đã mang đ n cho chúng em nh ng ki n th c m i các ph ng pháp mô

ặ ỏ ệ ệ ỏ ọ ph ng, đ c bi t là mô ph ng tin h c hi u năng cao.

ự ệ ể ầ ượ ể ậ Qua quá trình th c hi n ti u lu n, ph n nào chúng em cũng đ c hi u thêm

ậ ậ ọ ỏ ề v các thu t toán th n tr ng trong mô ph ng song song. Tuy nhiên, do ch đ ủ ề

ậ ủ ứ ế ể ẻ ế ạ ớ ớ ỉ ừ khá m i m và ki n th c còn h n ch nên ti u lu n c a chúng em m i ch d ng

ụ ỏ ử ệ ề ể ầ ỏ ộ ạ ở ứ l m c tìm hi u và th nghi m m t vài ví d nh trên ph n m m mô ph ng. i

ử ớ ả ờ ả ơ ầ Chúng em xin chân thành g i t ạ i Th y, TS. Ph m Đăng H i l i c m n sâu

ứ ữ ế ạ ấ ầ ậ ả ắ s c. Th y đã t n tình gi ng d y và cung c p cho chúng em nh ng ki n th c và

ế ể ể ậ ệ ầ tài li u c n thi t đ chúng em hoàn thành ti u lu n này.

Conservative Synchronization of LargeScale Network Simulations

[1] R. M. Fujimoto, Parallel and Distributed Simulation Systems. New York: Wiley

Ả Ệ TÀI LI U THAM KH O

[2] K. M. Chandy and J. Misra, "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs," IEEE Transactions on Software Engineering, vol. 5, pp. 440452, 1979.

[3] R. E. Bryant, "Simulation of Packet Communications Architecture Computer Systems," Massachusetts Institute of Technology. MITLCSTR188 MITLCS TR188, 1977.

[4] R. Bagrodia and M. Takai, "Performance evaluation of conservative algorithms in parallel simulation languages," IEEE Transactions on Parallel and Distributed Systems, vol. 11, pp. 395411, 2000.

[5] W.K. Su and C. L. Seitz, "Variants of the ChandyMisraBryant Distributed DiscreteEvent Simulation Algorithm," presented at the SCS Multiconference on Distributed Simulation '89, Miami, FL, 1989.

[6] J. Porras, V. Hara, J. Harju, and J. Ikonen, Improving the Performance of the ChandyMisra Parallel Simulation Algorithm in a Distributed Workstation Environment. Arlington, VA, 1997.

[7] W. Cai and S. J. Turner, "An Algorithm for Reducing NullMessages of the CMB

Interscience, 2000.

[8] D. M. Nicol, "The Cost of Conservative Synchronization in Parallel Discrete Event

Approach in Parallel Discrete Event Simulation," University of Exeter, 1995.

[9] K. M. Chandy and J. Misra, "Asynchronous Distributed Simulation via a Sequence of Parallel Computations," Communications of the ACM, vol. 24, pp. 198205, 1981.

[10] B. D. Lubachevsky, "Efficient Distributed EventDrive Simulations of Multiple

Simulations," Journal of the ACM, vol. 40, pp. 304333, 1993.

[11] Z. Xiao, B. Unger, R. Simmonds, and J. Cleary, "Scheduling Critical Channels in Conservative Parallel Discrete Event Simulation," presented at the 13th Workshop on Parallel and Distributed Simulation, Atlanta, GA, 1999.

[12] H. Y. Song, R. A. Meyer, and R. Bagrodia, "An Empricial Study of Conservative Scheduling," presented at the 14th Workshop on Parallel and Distributed Simulation, Bologna, Italy, 2000.

[13] M. L. Bailey and M. A. Pagels, "Measuring the Overhead in Conservative Parallel Simulations of Multicomputer Programs," presented at the 23rd Winter Simulation Conference, Phoenix, AZ, 1991.

Loop Networks," Communications of the ACM, vol. 32, pp. 111123, 1989.

Conservative Synchronization of LargeScale Network Simulations

[14] D. M. Nicol, "Scalability, Locality, Partitioning and Synchronization in PDES," presented at the 12th Workshop on Parallel and Distributed Simulation, Banff, Alberta, Canada, 1998.

[15] D. M. Nicol and J. Liu, "Composite Synchronization in Parallel DiscreteEvent Simulation," IEEE Transactions on Parallel and Distributed Systems, vol. 13, pp. 433446, 2002.

[16] D. M. Nicol, "Analysis of Synchronization in Massively Parallel DiscreteEvent

[17] D. M. Nicol, C. Michael, and P. Inouye, "Efficient

Simulation," presented at the 2nd ACM SIGPLAN, Seattle, WA, 1990.

[18] C.C. Lim, Y.H. Low, B.P. Gan, S. Jain, W. Cai, W. J.

Aggregation of Multiple LP's in Distributed Memory Parallel Simulations," presented at the 21st Winter Simulation Conference, Washington, D.C., 1989.

[19] E. Naroska and U. Schwiegelshohn, "Conservative Parallel Simulation of a Large

Hsu, and S. Y. Huang, "Performance Prediction Tools for Parallel DiscreteEvent Simulation," presented at the 13th Workshop on Parallel and Distributed Simulation, Atlanta, GA, 1999.

[20] J. Lemeire and E. Dirkx, "Performance Factors in Parallel Discrete Event Simulation," presented at the 15th European Simulation Multiconference, Prague, 2001.

[21] V. Jha and R. Bagrodia, "A Performance Evaluation Methodology for Parallel Simulation Protocols," presented at the 10th Workshop on Parallel and Distributed Simulation, Philadelphia, PA, 1996.

[22] "NMS Baseline Model. http://www.cs.dartmouth.edu/~nicol/NMS/baseline/." [23]

Number of Processes," Simulation, vol. 72, pp. 150162, 1999.

[24] R. M. Fujimoto, T. McLean, and K. S. Perumalla, "Design of High Performance RTI Software," presented at the 4th Workshop on Distributed Simulation and Real Time Applications, San Francisco, CA, 2000.

[25] K. S. Perumalla, A. Park, R. M. Fujimoto, and G. F. Riley, "Scalable RTIBased Parallel Simulation of Networks," presented at the 17th Workshop on Parallel and Distributed Simulation, San Diego, CA, 2003.

[26] G. F. Riley, "The Georgia Tech Network Simulator," presented at the ACM

"pdns. http://www.cc.gatech.edu/computing/compass/pdns/." [23] [24] G. F. Riley, R. M. Fujimoto, and M. H. Ammar, "A Generic Framework for Parallelization of Network Simulations," presented at the 7th MASCOTS, College Park, MD, 1999. [25] "libSynk. http://www.cc.gatech.edu/computing/pads/kalyan/libsynk.htm."

[27] Alfred Park, Richard M. Fujimoto, Kalyan S. Perumalla, “Conservative Synchronization of LargeScale Network Simulations” Proceedings of the 18th 22

SIGCOMM '03, Karlsruhe, Germany, 2003.

Conservative Synchronization of LargeScale Network Simulations

Workshop on Parallel and Distributed Simulation (PADS’04), Atlanta, Georgia, USA, 2004.