BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYỄN LÊ ANH LÝ THUYẾT CHUYỂN MẠCH VÀ LƯU LƯỢNG TRONG MẠNG TÍCH HỢP BĂNG RỘNG LUẬN VĂN THẠC SĨ NGÀNH ĐIỆN TỬ VIỄN THÔNG Hà Nội, 2004 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI NGUYỄN LÊ ANH LÝ THUYẾT CHUYỂN MẠCH VÀ LƯU LƯỢNG TRONG MẠNG TÍCH HỢP BĂNG RỘNG LUẬN VĂN THẠC SĨ NGÀNH ĐIỆN TỬ VIỄN THÔNG NGƯỜI HƯỚNG DẪN : TS.VŨ QUÝ ĐIỀM Hà Nội, 2004 C¸c thuật ngữ viết tắt ARPA Advanced Research Project Agency Cơ quan nghiên cứu dự án tiên tiến ATM Asynchronous Transfer Mode Chế độ truyền tải bất đồng BCN Broadcasting Circuit Number Số kênh quảng bá B-ICI Broadband Inter Carrier Interface Giao diện mạng băng rộng B-ISDN Broađband ISDN CATV Cable TV Truyền hình cáp CE Circuit Emulation Giao diện mô Non ISDN băng rộng ATM ESS Electronic Switching System Hệ thống chuyển mạch điện tử FDM Frequency division multiplexing Ghép kênh phân chia theo số FR Frame Relay FCFS First Come First Service Nguyên lý vào tr ớc, phục vụ tr ớc HOL Head of Line Đầu hàng IDN Interconnection Digital Networks Mạng số đa liên kết ISDN Integrated Services Digital Networks Mạng số đa dịch vụ ITU International Telecommunication Union Liên hiệp viễn thông quốc tế IP Internet protocol Giao thøc Internet GAN Global Area Network Mạng toàn cầu LAN Local Area Network Mạng nội MAN Metropolitan Area Network Mạng đ ờng trục NIC Network Interface Card Card giao diƯn m¹ng NNI Network to Network Interface Giao diện mạng- mạng N-ISDN Narrow ISDN ISDN băng hĐp P-NNI Private NNI Giao diƯn m¹ng - m¹ng dïng riªng POST Plain OLD Telepone Service PSTN Public Swiched Telephone Network Mạng điện thoại công cộng PCM Pulse Code Modulation §iỊu chÕ m· xung SDTV Standard Digital TV Trun h×nh số chuẩn SDS Space division switching Chuyển mạch không gian SDM Space division multiplexing Ghép kênh theo không gian SSS Space - Space - Space Chuyển mạch tầng không gian-không gian-không gian ST Space - Time Chuyển mạch tầng Không gian - thời gian STM Synchronous Transfer Mode Chế độ truyền tải đồng TDM Time division Multiplexing GhÐp kªnh theo thêi gian TDS Time division switching Chun m¹ch theo thêi gian TMS Time Multiplexed Switch Chun m¹ch ghÐp theo thêi gian TSI Time Slot Interchanger Bé trao ®æi khe thêi gian TST Time - Space - Time Chuyển mạch tầng Thời gian - không gian - thời gian VCI Virtual Circuit Identifier Bộ nhận dạng kênh ảo UNI User Network Interface Giao diện mạng thuê bao WAN Wide Area Network Mạng diện rộng Danh mục hình vẽ Hình 1.1: Mô hình trạng thái tho¹i 10 T 32 T 32 Hình 1.2: Mô hình cụm trạng th¸i 10 T 32 T 32 Hình 1.3: Mô hình trạng thái cho thoại đồng gói có loại bỏ khoảng im lặng10 T 32 T 32 Hình 1.4: ma trận chuyển m¹ch ngang däc 11 T 32 T 32 Hình 1.5: Bộ trao đổi khe thêi gian 12 T 32 T 32 Hình 1.6: chuyển mạch ghép thêi gian 13 T 32 T 32 Hình 1.7: Chuyển mạch TS để liên kết tuyến TDM 13 T 32 T 32 H×nh 1.8: Sù t ¬ng øng cđa chun m¹ch SS víi TS 14 T 32 T 32 H×nh 1.9: mạng chuyển mạch tầng TST SSS 14 T 32 T 32 H×nh 2.1: Diễn tả đồ thị mạng TST SSS t ¬ng øng 15 T 32 T 32 Hình 2.2: Biểu đồ diễn tả nối 16 T 32 T 32 Hình 2.3: Kích cỡ mạng clos 17 T 32 T 32 Hình 2.4: Đ ờng nối mạng tầng 18 T 32 T 32 Hình 2.5: Ma trận Paull để biĨu diƠn c¸c cc nèi 18 T 32 T 32 Hình 2.6: Điều kiện ma trËn Paull cho cc nèi ®iĨm - ®iĨm 19 T 32 T 32 H×nh 2.7: Các mạng không nghẽn chiều 22 T 32 T 32 H×nh 2.8: Phân tách đệ quy cho mạng Benes 22 T 32 T 32 H×nh 2.9: M¹ng Cantor 23 T 32 T 32 H×nh 2.10: Giải thuật vòng 25 T 32 T 32 Hình 3.1: Các chức kết nối với đầu không đ ợc định 27 T 32 T 32 Hình 3.2: Nút chuyển mạch 2x2 với hai trạng thái 28 T 32 T 32 Hình 3.3: Xây dựng siêu tập trung dùng siêu tập trung nén 31 T 32 T 32 Hình 3.4: Phân tách hai tầng cho siêu tập trung nén 32 T 32 T 32 Hình 3.6: Mạng Banyan đảo đ ợc hình thành phân tách hai tầng đệ quy 33 T 32 T 32 H×nh 3.7: CÊu tróc mạng phân tán 35 T 32 T 32 H×nh 3.8: Mét kiĨu kết nối nén đơn điệu 35 T 32 T 32 H×nh 3.9: Mạng phân tán chép 36 T 32 T 32 H×nh 3.10: Tính đối ngẫu tập trung nhiều-một chép một-nhiều 36 T 32 T 32 Hình 3.12: Mạng tầng đa điểm 38 T 32 T 32 H×nh 4.1: Dò tìm độ sâu để truy lùng kênh 40 T 32 T 32 Hình 4.2: Một kết nối đa khe 42 T 32 T 32 Hình 4.3: Nhầm khe thời gian cạnh mạng43 T 32 Hình 4.4: Chuyển mạch gói nhanh 44 T 32 T 32 Hình 4.5: Thông l ợng nối thông ¶o cđa mét nót chun m¹ch 45 T 32 T 32 Hình 4.6: Một nút chuyển mạch có đệm đầu 45 T 32 T 32 Hình 4.7: Các ph ơng pháp thay đổi hình dạng mạng 46 T 32 T 32 Hình 4.8: Tự định tun m¹ng chun m¹ch gãi 47 T 32 T 32 H×nh 5.1: NghÏn ngâ ®èi víi chun m¹ch 48 T 32 T 32 Hình 5.2: Nghẽn HOL đối víi chun m¹ch gãi 49 T 32 T 32 Hình 5.3: Chuyển mạch tự định tuyến không nghẽn nội 50 T 32 T 32 Hình 5.4: Các điều kiện không nghẽn mạng Banyan 51 T 32 T 32 Hình 5.5: Kết hợp danh sách ®· s¾p xÕp 52 T 32 T 32 Hình 5.6: Danh sách bitonic víi sù nèi chÐo nhÊt 53 T 32 T 32 H×nh 5.7: CÊu tróc ®Ư quy cđa bé s¾p xÕp Bitonic 2x2 54 T 32 T 32 H×nh 5.8: Mạng xếp Batcher 55 T 32 T 32 H×nh 5.9: Sư dụng xếp để phát tranh chấp đầu 56 T 32 T 32 H×nh 5.10: Sắp xếpthanh lọctập trung cho giải phóng đóng gói 57 T 32 T 32 Hình 5.11: Vào lại gói bị lọc để thử lại 58 T 32 T 32 H×nh 5.12: Lan trun ng ỵc sù nhËn biÕt 59 T 32 T 32 Hình 5.13: Quá trình thăm dò chấp nhận biết – göi 60 T 32 T 32 Hình 6.1: Các mô hình trạng thái điện tho¹i 65 T 32 T 32 Hình 6.2: Các trạng thái đa lớp đầu cuèi 66 T 32 T 32 Hình 6.3: Các trạng thái im lặng khác điện thoại 66 T 32 T 32 Hình 6.4: Thông tin truyền hình với hai trạng thái cử động 67 T 32 T 32 Hình 6.5: Tạo trình điểm Poisson trình Markov 74 T 32 T 32 Hình 6.6: Các hàm đo 76 T 32 T 32 Hình 6.7: Hoán vị hàm không thay đổi sè ®o 77 T 32 T 32 Hình 7.1: Quá trình sinh-tử cho K đầu cuối 85 T 32 T 32 Hình 7.2: Không gian trạng thái đến Poisson 86 T 32 T 32 Hình 7.3: Quá trình sinh-tử Markov hai thø nguyªn 88 T 32 T 32 Hình 7.4: Chuổi ghi dịch m« pháng trĨ 91 T 32 T 32 Hình 7.5: Mô nghẽn trình bán Markov 92 T 32 T 32 Hình 7.6: Các trạng thái Markov hai thứ nguyên l u l ợng có tràn 96 T 32 T 32 Hình 7.7: Sử dụng ph ơng tiện truyền dẫn thứ cấp cho tràn 97 T 32 T 32 H×nh 7.8: Vùng R(PB).98 T 32 R R Hình 8.1: Các mạng chuổi song song chuổi song song 107 T 32 T 32 Hình 8.2: Các xác suất chiếm dụng mạng đa tầng 109 T 32 T 32 Hình 8.3: Phân bó chiếm hữu đầu 111 T 32 T 32 Hình 8.4: So khớp tuyến rổi mạng Clos tầng 113 T 32 T 32 Hình 8.5: Biểu đồ Lee mạng phân tách đệ quy 116 T 32 T 32 H×nh 8.6: Phép tính đệ quy khả dụng 117 T 32 T 32 H×nh 9.1: Cấu trúc mạng viễn thông ATM 125 T 32 T 32 lêi nói đầu Ngày nay, tr ớc bùng nổ ngành công nghệ thông tin, nh tiến v ợt bậc mặt công nghệ cho phép chế tạo vi xử lý tốc độ cao, truyền dẫn thông tin nhanh chóng Chính nhờ tiến khoa học này, mà ngày xuất nhiều loại dịch vơ míi nh»m tháa m·n nhu cÇu cđa ng êi sử dụng với chất l ợng cao Chính điều đòi hỏi phải có mạng thông tin tích hợp, đáp ứng dịch vụ với yêu cầu mặt chất l ợng khác Vì vậy, việc nghiên cứu lý thuyết chuyển mạch l u l ợng cho mạng tích hợp băng rộng không nằm lý Hiện giới có nhiều công nghệ chuyển mạch, nh ng phổ biến rộng rÃi chuyển mạch kênh chuyển mạch gói công nghệ khác chuyển mạch đa tốc độ (multirate), chuyển mạch nhanh chuyển mạch cụm (burst) gói (packet) nhanh Trong năm gần đây, chuyển mạch thông tin đà trở nên quan trọng phát triển gia tăng loại hình điện thoại Ngày nay, ng ời thực gọi mạng rộng với khả v ợt trội điểm chuyển mạch khả truyền dẫn đạt tới 500 triệu máy điện thoại Chuyển mạch điện thoại đà thay đổi vài năm gần nhằm đáp ứng yêu cầu ngày tăng khách hàng với nhiều loại hình dịch vụ khác nhau, không điện thoại tích hợp nhiều dịch vụ chất l ợng cao khác nh : CATV, Video telephone, Để làm đ ợc điều bảng chuyển mạch phải hoạt động thông qua nhiều hệ thống điện tử tích hợp, với ch ơng trình sử lý nhằm nâng cao tốc độ nh giá chất l ợng dịch vụ Bắt đầu từ hệ thống số đ ợc phòng thí nghiệm Bell sáng tạo từ năm 1959 cho đện hệ thống chuyển mạch ®iƯn tư No.4 (4ESS: No.4 Electronic Switching System) lµ mét hệ thống song song có tính c ớc lần đ ợc sử dụng Chicago vào năm 1976 Hệ thống chuyển mạch gói đ ợc cài đặt thử lần d ới quan nghiên cứu dự án tiên tiến (ARPA: Advanced Research Project Agency) vào năm 1966 Nghiên cứu chuyển mạch không đồng (ATM) chuyển mạch gói nhanh đà thực đ a ứng dụng rộng rÃi vài năm gần Chuyển mạch l ợng tử hay gọi cách khác chuyển mạch quang đ ợc nghiên cứu đem ứng dụng t ơng lai Việc tìm hiểu lý thuyết chuyển mạch nói chung chuyển mạch dùng mạng tích hợp băng rộng nói riêng vô quan trọng nay, nhằm tạo tiền đề vững việc lựa chọn công nghệ tối u nhằm đại hóa ngành viễn thông n ớc nhà đề đón đầu theo kịp phát triển chung giới, đồng thời phải thích hợp với điều kiện Việt Nam Trong khuôn khổ luận văn, cố gắng trình bày tảng lý thuyết chuyển mạch l u l ợng mạng tích hợp băng rộng Từ tạo tiền đề cho việc nghiên cứu, áp dụng vào thực tế, xây dựng, quản lý, đầu t mạng thông tin ngày hoàn chỉnh nh ng đáp ứng đ ợc nhu cầu đáng ng ời sử dụng Bài luận văn đ ợc chia làm phần: ã Phần I: Tổng quan lý thuyết chuyển mạch mạng tích hợp băng rộng, bao gåm ch ¬ng: - Ch ¬ng 1: Truy nhËp ghép kênh tích hợp băng rộng - Ch ơng 2: Chuyển mạch kênh đa tầng điểm-điểm - Ch ơng 3: Chuyển mạch kênh đa điểm suy rộng - Ch ơng 4: Từ chuyển mạch kênh đa tốc độ đến chuyển mạch gói nhanh - Ch ơng 5: ứng dụng xếp cho chuyển mạch không nghẽn tự định tuyến ã Phần II: Tổng quan lý thuyết l u l ợng mạng tích hợp băng rộng, gåm ch ¬ng - Ch ¬ng 6: L u l ợng đầu cuối kết hợp - Ch ơng 7: Nghẽn chia tài nguyên đơn tầng - Ch ơng 8: Nghẽn chia tài nguyên đa tầng ã Ch ơng 9: Vấn đề xây dựng mạng tích hợp băng rộng Việt Nam nói chung tỉnh Đắklắk nói riêng Do lý thuyết chuyển mạch l u l ợng mạng tích hợp băng rộng hai vấn đề rộng Mặt khác, vấn đề liên quan tới nhiều công nghệ khác nh : truyền dẫn, ATM, Vì vậy, luận văn chắn không tránh khỏi thiếu sót Do đó, mong muốn ý kiến đóng góp thầy cô nh bạn đồng nghiệp Qua đây, xin chân thành cảm ơn thầy giáo h ớng dẫn: P.G.S, T.S Vũ Quý Điềm, ng ời đà tận tình giúp đỡ dẫn hoàn thành luận văn Ch ơng 1: Truy nhập ghép kênh tích hợp băng rộng Trong ch ơng này, tr ớc tiên nghiên cứu làm cách dịch vụ chia sẻ ph ơng tiện truyền dẫn băng rộng đơn lẻ Chúng ta từ kỹ thuật ghép kênh thời gian dịch vụ đơn tốc độ bít đến kỹ thuật ghép kênh dịch vụ đa tốc độ dịch vụ cụm Sau đó, mô tả vài kỹ thuật chuyển mạch miền không gian thời gian, sử dụng đồng thòi hai kỷ thuật 1.1 Ghép kênh theo thời gian cho dịch vụ đa tốc độ Bài toán ghép kênh truyền dẫn đ ợc nói nh sau: giả sử có m đầu cuối thông tin T , T2 , Ti , Tm chia sẻ đ ờng trun dÉn Gi¶ sư R R R R R R R R băng thông đ ợc chia sẻ cho đầu cuối truyền dẫn thời điểm khác Chế độ ghép kênh loại đ ợc gọi chế ®é ghÐp kªnh ®ång bé (STM: Synchronous Transfer Mode) 1.1.1 Chế độ truyền tải đồng (STM) Giả sử đ êng trun dÉn cã dung l ỵng C bÝt/s Chóng ta sử dụng định dạng ghép kênh theo thời gian (TDM: Time Division Multiplexing) để chia băng thông nh sau: ã TDM đơn khe: tức đầu cuối có tốc độ b bít phát đ ợc bd bít khung độ dài d Các bít đ ợc đặt vào khe đ ợc lựa chọn tr ớc khung Đầu cuối sử dụng khe khung liên tiếp Khi đầu cuối Ti đ ợc gán khe, ta nói sở hữu kênh R R ã TDM đa cửa sổ: chia dung l ợng kênh C thành K cửa sổ, có dạng TDM đa cửa sổ Mỗi khung d đ ợc chia thành K cửa sổ cửa sổ cók Nkhe có độ R R dài ek Mỗi đầu cuối có tốc độ bítkb, kK Trong khung, kiểu đầu cuối k R R R R ph¸t n k = b k d bít Các bit đ ợc khe vËn chun cưa sỉ thø k, nªn cì R R R R cña khe Ýt nhÊt kn= Cek R R R R xuống đầu nút chuyển mạch Ví dụ: tuyến từ nút đ ợc đánh số 01 tầng đ ợc định đ ợc đánh số 010 011 t ơng ứng Nói cách khác, đ ợc nối thêm vào số nút tuyến số đ ợc nối thêm vào số nút đối víi tuyÕn d íi Mét tuyÕn kÕt nèi nút tầng liên kết k k+1 Nút tầng k có nút đ ợc đánh số số tuyến bít bên phải nhất, nút tầng k+1 cho đánh số đ ợc cung cấp số tuyến bít bên trái VÝ dơ: tun 011 kÕt nèi nót 01 víi nót 11 tầng Mạng Banyan Mạng Baseline Mạng trao đổi trộn lẫn (hay mạng Omega) Mạnh FLIP Trao đổi trộn lẫn Trao đổi trộn lẫn đảo Hình C.5: Vài mạng định tuyến có độ phức tạp NlogN U U 000 001 010 011 100 101 110 111 00 00 00 01 01 10 10 10 11 11 11 01 trªn d íi 000 001 010 011 100 101 110 111 C¹nh 011 kÕt nèi nót 01 (bá bit LSB cđa c¹nh) víi nót 11 (bá bit MSB cạnh) Hình C.6: Biểu diển nút tuyến mạng trao đổi trộn lẫn tự định tuyến U U Dựa vào biểu diễn này, l ợc đồ tự định tuyến mạng trao đổi trộn lẩn đơn giản Giả sử, ta có gói đầu vào1 aa2a n đ ợc định cho đầu b1b2 b n Chúng ta sử dụng chuỗi b b2 bn nh địa tự định tuyến sử dung tuyến d ới tầng k theo kb= bk =1 Với cách này, gói kết thúc đầu mong muốn mạng trao đổi trộn lẩn Đặc biệt hơn, gói ghé qua nút a2 an tầng đầu tiên; sử dụng cạnh a2a nb1 để duyệt nút a3 a nb1 tầng 2;.; sử dụng cạnh a k+1 anb1. bk để duyệt nút k+2 a .a nb1 bk tầng k+1;; cuối đến cạnh đầu ra1 b.b n-1 tầng n Chúng ta sử dụng kiểu đánh số từ xuống cho nút tuyến mạng khác (hình C.5) Sự đánh số tạo chứng minh đơn giản cho tính chất sau mà đ ợc sử dụng ch ơng Xét mạng trao đổi trộn lẩn Giả sử địa tự định tuyến gói từ đầu vào thỏa mÃn điều kiện sau: Một địa hoàn toàn đơn điệu theo kiểu địa đích hoàn toàn tăng xét xuống đầu vào; Hai là, gói đ ợc nén theo kiểu đầu vào rỗi hai đầu vào với gói Kế đến, đ ờng tự định tuyến đ ợc sử dụng gói không chia sẻ tuyến bên mạng trao đổi trộn lẩn Vì tuyến đ ợc chia sẻ, nên không cần đặt đệm đầu vào nút bên Do đó, loại bỏ đệm bên mạng Banyan có đệm điều kiện đơn điệu nén thu đ ợc cách Đầu vào 000 Nguồn 001 Đầu Cạnh 001 010 011 100 00 00 00 01 01 01 10 10 10 101 110 111 C¹nh 011 000 001 010 011 C¹nh C¹nh 11 110 11 110 11 Nguån 100 101 111 §Ých 1 Cạnh Cạnh Cạnh Cạnh Hình C.7: Tự định tuyến mạng trao đổi trộn lẫn U U C.3 Các giới hạn tổ hợp mạng Banyan N 1/2 Một mạng Banyan nhận biết exp phép hoán vị 2(1/2Nlog N) = (N ) đầu vào-ra đối số sau Có 1/2N2log N nút chuyển mạch x2, nút chuyển mạch 2x2 trạng thái nối chép nối ngang Do có exp 2(1/2Nlog N) trạng thái mạng khác nhau, trạng thái toàn trạng thái nhận biết kiểu kết nối riêng biệt, trạng thái định nghĩa N đ ờng liên kết-tách rời (link disjoint path) khác đ ờng định nghĩa kết nối đầu vào tính chất đ ờng mạng Banyan Từ đó, số hoán vị đà nhận biết thoả mÃn biên hoán vị đ ợc phép theo tổng số nút Tuy nhiên, mạng banyan nhận biết tất N! exp (Nlog2N) hoán vị đầu vào-ra riêng biệt Thực tế, mạng Banyan có tổng số nút theo biên tổ hợp Chúng ta đà ch ơng mạng Benes gồm mạng Baseline thuận mạng Beseline đảo (cả hai t ơng ứng ®ång d¹ng víi m¹ng Banyan), ®đ ®Ĩ kÕt nèi tÊt N! hoán vị Do đó, phân số hoán vị đ ợc nhận biết mạng Banyan tiến tới nh / N! Nên mạng banyan nghẽn đ ợc dùng nh mạng chuyển mạch kênh Công suất kết hợp mạng banyan tăng đáng kể ph ơng pháp chuyển mạch nhân tuyến nối đuôi nhân đà đề nghị, đ ợc trình bày hình 4.7 (Chuyển mạch nối đuôi gấp đôi tổng số nút, hệ mạng Benes nhận biết hoán vị) Để thu đ ợc số hoán vị xác nhận biết th ờng khó Vì hầu hết hoán vị đ ợc nhận biÕt b»ng m¹ng Banyan, chun m¹ch gãi nhanh sư dơng đệm tuyến bên để làm dịu nghẽn nội bộ, nh ng lại đ a trễ ngẫu nhiên phụ thuộc vào tính ngẫu nhiên địa gói nút bên mạng Banyan Trong tr êng hỵp lý t ëng, ta cã thể giả sử gói đầu vào mạng Banyan đ ợc địa độc lập ngẫu nhiên đầu Tuy nhiên, mạng Banyan có đệm bị nghẽn nghiêm trọng địa đích không ngẫu nhiên Ví dụ: đầu vào đ ợc đặc ân hơn, nh tạo gọi điểm nóng đầu Một vấn đề khác phát sinh gói đến đầu vào tới đầu Xét ví dụ mà đầu vào gửi gói cách lặp lại đến đầu riêng biệt Phần kết nối lặp lại hoán vị làm cho mạng Banyan nghẽn Trong tr ờng hợp tệ nhất, tuyến đ ợc sử dụng N kết nối đầu vàora nh đà ®èi sè sau: Mét ®Çu cđa mét nót chun mạch tầng kn/2 mạng Banyan tới đ ợc 2k đầu vào mạng Tại tầng k=n/2, n/2 nút đến đ ợc 2= N đầu vào, nh vậy, gây tr ờng hợp tƯ nhÊt, nhiỊu kÕt nèi sư dơng cïng mét tun Tuy nhiên, số kết nối v ợt n/2 tuyến tr ớc tầng thứ n/2, tuyến tiến tới nhỏ đầu Giả sử hoán vị chắn nh nhau, xác suất xảy tải yêu cầu tr ờng hợp tệ tải nhỏ N lớn Một ph ơng tiện để giải tải phụ cách tăng tốc độ truyền dẫn mạng chuyển mạch khoảng từ ữ8 đủ (xem ch ơng 10) Bên cạnh việc tăng tốc, sử dụng bội tuyến mạng nh đà hình 4.7 mà gần nh có ảnh h ởng nh t ơng ứng ghép kênh thời gian không gian Nh việc tăng tốc thế, sử dụng mặt phẳng chuyển mạch nhân đôi, gửi gói cách ngẫu nhiên vào mặt phẳng chuyển mạch Giống nh rẻ nhánh mạng ngẫu nhiên hóa Mạng nối đuôi Phân bố gói nh Mạng ngẫu nhiên hóa Mạng định tuyến đích Hình C.8: Định tuyến ngẫu nhiên tải bất th ờng nội U U Hiệu hơn, sử dụng chuyển mạch nối đuôi với định tuyến ngẫu nhiên nửa đầu mạng chuyển mạch nh đ ợc hình C.8 Tại nút nửa đầu chuyển mạch nối đuôi, gói đ ợc định tuyến ngẫu nhiên tới hai ngõ Do đó, gói từ đầu vào đ ợc định tuyến đến tuyến ngẫu nhiên chuyển mạch nối đuôi Sau ®ã, gãi theo mét ® êng nhÊt ®Õn ®Çu mong mn nưa thø cđa m¹ng TÝnh ngẫu nhiên định tuyến làm giảm tải tuyến t ơng quan địa gói từ đầu vào Nh đà đề cập tr ớc đó, sử dụng ph ơng pháp dẫn đến gói đ ợc giải phóng Hơn nữa, dùng đệm bên tạo trễ ngẫu nhiên không mong muốn Trong ch ơng kế tiếp, giới thiệu mạng chuyển mạch gói luân phiên không sử dụng đệm bên trong, loại bỏ đ ợc vài ảnh h ởng xấu Các mạng sử dụng mạng xếp để tạo kiểu đầu đơn điệu nén đầu vào mạng Banyan Phụ lục D: Xấp xỉ độ lệch lớn đà cải thiện Tr íc hÕt, chóng ta sÏ chøng minh xÊp xØ độ lệch lớn trình Poisson bị lọc Nhớ lại N i số cụm kiểu i, có biên độ đến khoảng chu kỳ khứ b i Giả sử cụm Poisson tới với tốc độ i, ta có mật độ xác suất nh p Ni (ni ) = (γ i bi ) ni e ibi ni ! sau: (D.1) Vì cụm biên độ lớn đóng góp đáng kể cho P(Wy), mà đề nghị làm đối xứng lệch mật độ p Hay định nghĩa s,iNlà sè sù kiƯn ®Õn N i theo cđa cơm kiĨu i, với biên độ tốc độ đến Poisson i esa i thay cho γi ThÕ γi →γ i esa i vào ph ơng trình (D.1), ta có mËt ®é lƯch ®èi xøng PN s, i (n ) = (γ e b ) n ! i s, i sai n s, i i e− γ i e sa i bi (D.2) s ,i ( ) sai = p Ni (n i )esn i a i −γ ibi e Ph ơng trình biểu diễn mối quan hệ phân bố N Ni Xét mật độ xác s,i suÊt W = ∑ Ni vµWs = ∑ N s ,i Sử dụng ph ơng trình (D.2), thu đ ợc i i mối qun hệ phân bố W sW pW (w ) = Π ni :∑ ni =w p N i (ni ) (D.3) i Π = ni :∑ ni =w p N s,i ( n s,i )e −sni a i +γ ibi ( e sai −1) i Π = n i :∑ n i = w pN (n ) s,i s, i ( sw ∑ γ b e sai −1 e− + i i i ) i = pW (ws = w)e − sw+ µ w (s ) s Hơn nữa, đ ợc thẩm định dễ dàng nhờ sử dụng ph ơng trình (6.6.10) r»ng E(Ws ) = µW (s) vµ V(W s ) = "W (s ) Phân bố đuôi mong muèn lµ: P( W > y) = ∞ ∫ p (w)dw (D.4) W y ∞ = − sw +µ ∫ p s (ws )e s W W (s ) dw s y =e ∞ −sy + µ W (s ) − s (w − y ) ∫ p s (ws )e s dws W y Chóng ta chän s=s* tho¶ mÃn ph ơng trình ẩn (6.8.2) biên Chernoff L u ý tích phân àyW= (s*) trung bình W s * Để tính tích phân, ta dùng định lý giới hạn trung tâm để xấp xỉ p W * phân bố Gaussian, s với trị trung bìnhà W(s) khoảng biến thiênàW(s) Do P(W>y) xấp xỉ bằng: e sy + µ W (s *) =e ∞ ∫ 2πµ" W (s *) y − sy+ µW ( s*) u2 / e ∞ ∫ u 2π × exp − ( ws − y)2 2µ "W ( s ) e v / 2dv với Tích phân mà đ ợc biết nh thêm thừa số phô − s* ( ws − y) dws (D.5) u = s * µ "W ( s ∗) e u / Do đó, u hàm lổi, bị giới hạn để cải thiện tính toán đ ợc cho biên u Chernoff Chóng ta võa chøng minh xÊp xØ ®é lƯch lớn trình Poisson bị lọc Cùng thừa số giữ cho W tổng nhiều biến ngẫu nhiên hữu hạn phân bố giống độc lập Sự chứng minh t ơng tự ngoại trừ điểm Đối với trình Poisson bị lọc, ta làm lƯch tèc ®é ®Õn b»ng mét thõa esèsai ®èi víi kiên đến xung Poisson với biên độ a i Để tổng biến ngẫu nhiên X, làm lệch đối xứng phân bố xác suất X thành dạngsX cho: PX s ( x) = PX (x) e sx ∑ P (x) e sx X x (D.6) Phần lại chứng minh hầu nh giống với chứng minh trình Poisson bị lọc, đ ợc bỏ qua Bây giờ, tập trung vào ph ơng pháp số để tính phân bố đuôi W sếp chồng trình Poisson bị lọc số l ợng trình luân phiên làm trạng thái Ta vừa kiểu l u l ợng cụm đ ợc mô hình hoá trình Poisson có lọc, hàm sinh moment logalit tổng l u l ợng đ îc cho bëi: ( ) µW ( s) = ∑ γ i bi esa i − (D.7) i ng ợc lại l u l ợng tốc độ biến đổi đ ợc biểu diển xác suất dựa vào biểu đồ tốc độ {(a j,p j)} Hàm sinh moment loglit gọi riêng lẽ thông th ờng lµ: µ k (s ) = log e ∑ p j e sa j (D.8) j Víi l u l ợng tốc độ biến đổi Poisson đ ợc tổ hợp lại, tổng hàm sinh moment logalit Phân bố đuôi W đ ợc xấp xỉ gần bằng: P(W > y) = s * 2πµ ' 'W (s *) − s y− s e ( * µ W ( *)) (D.9) Víi µW(s*)=y §Ĩ tÝnh (D.9), chóng ta sÏ më réngµk(s) (D.8) trình riêng rẽ chuỗi Taylor mà đ ợc tính tr ớc Chuỗi mở rộng biểu thức (D.7) tổng số mũ, không phức tạp Chúng ta đạt đ ợc chuỗi mở rộng biểu thức (D.7) nh chuỗi Cho ( sau: Đầu tiên, mở rộng đối số logalit thành k (s ) = log e a + a1s + a s + ) (D.10) = c1 s + c2 s2 + c 3s3+…… Chóng ta cã thĨ tÝnhi cnhê thđ tơc ®Ư quy sau: i −1 ci = qi − ja i − j c j i∑ j =1 Nh (D.11) vËy víi hƯ sè tÝnh tr íc này, ta dễ dàng thu đ ợc biểu thức mở rộng àk(s) nh hai đạo hàm thời gian thực Ph ơng trình (D.9) liên quan đến việc giải ph ơng trình ẩn cho s*, đặt đạo hàm củaà W(s) y Do đó, ph ơng pháp Newton ứng, nhờ sử dụng đạo hàm thứ hai củaàW(s) Vì àW(s) hàm lồi d ơng theo s, nên nghiệm ph ơng pháp Newton hiệu Thực tế, giữ lại giá trị tr ớc s* nh àW(s) đạo hàm Khi àW (s) bị thay đổi cách sếp chồng biến ngẫu nhiên khác trình Poisson, tìm đ ợc đảo lộn cho s* qua ph ơng pháp Newton dùng đạo hàm tr ớc Kinh nghiệm ớc đoán đủ xác đạt đ ợc với vòng lặp Các giá trị àW(s) phát sinh sau đ ợc cập nhật Phân bố đuôi (D.9) hàm đơn giản giá trị đ ợc tính Tài liƯu tham kh¶o Chris Dhas, Vijaya K Konangi and M Sreetharan (1996), Broadband Switching Architectures, Protocols, Design and Analysis, Mc Graw-Hill, United Kingdom Ed Taylor (1995), The Mcgraw-Hill Internetworking Handbook, Mc Graw-Hill, United Kingdom Joseph Y Hui (1990), Switching and Traffic theory for Integrated Broadband Networks, Rutgers University, New Jersey, USA Jonh Wiley & Sons (1994), Fundamentals of Telecommunication Networks, A Wiley-Interscience Publication John Wiley and Sons (1998), Switching theory architectures and performance in broadband ATM network, Achille Patytavina, Italy Mischa Schawarts (1993), Telecommunication Networks Protocols, Modeling and Analysis, Mc Graw-Hill, United Kingdom Xue Dao Gu (1997), Control and Performance in Packet, Circuit and ATM Networks, Mc Graw-Hill, United Kingdom B u điện tỉnh Đắklắk (2004), Báo cáo tổng kết công tác điều hành quản lý mạng Viễn thông tỉnh Đắklắk Nguyễn Thúc Hải (1991), Mạng máy tính kỹ thuật ứng dụng, Đại học Bách Khoa Hà Nội 10 Nguyễn Hữu Thanh (1997), Tổng quan kỷ thuật mạng B-ISDN, Nhà xuất khoa học kỹ thuật 11 Tạp chí PC World năm 1999, 2000, 2001, 2002, 2003 Mục lục Các thuật ngữ viết tắt T 32 T 32 Danh mục hình vẽ T 32 T 32 lời nói đầu T 32 T 32 PhÇn I: Lý thuyết chuyển mạch mạng tích hợp băng T 32 rộng Ch ơng 1: Truy nhập ghép kênh tích hợp băng rộng T 32 T 32 1.1 GhÐp kªnh theo thêi gian cho dịch vụ đa tốc độ T 32 T 32 1.1.1 ChÕ ®é trun tải đồng (STM) T 32 T 32 1.1.2 ChÕ ®é trun tải không đồng (ATM) T 32 T 32 1.2 Kü thuËt ghÐp kênh theo thời gian cho dịch vụ cụm (bursty) 10 T 32 T 32 1.3 C¸c cấu chuyển mạch theo không gian thời gian 11 T 32 T 32 1.4 Chuyển mạch theo không gian ghép theo thời gian 11 T 32 T 32 1.4.1 Chuyển mạch kênh cho tuyến STM 11 T 32 T 32 1.4.2 Chuyển mạch gói cho tuyến ATM 13 T 32 T 32 Ch ¬ng 2: Chuyển mạch kênh đa tầng điểm - điểm 15 T 32 T 32 2.1 Chuyển mạch kênh điểm - điểm 15 T 32 T 32 2.2 Mạng chuyển mạch đa tầng 16 T 32 T 32 2.3 BiĨu diƠn c¸c kÕt nèi b»ng ma trËn Paul 17 T 32 T 32 2.4 Mạng Clos không nghẽn theo nghĩa 19 T 32 T 32 2.5 Các mạng xếp lại đ ợc 20 T 32 T 32 2.6 Cấu trúc đệ quy mạng chun m¹ch 20 T 32 T 32 2.7 M¹ng Cantor 22 T 32 T 32 2.8 Giải thuật điều khiển 23 T 32 T 32 Ch ơng 3: Chuyển mạch kênh đa điểm suy rộng 26 T 32 T 32 3.1 Chun m¹ch kªnh suy réng (Generalized Circuit Switching) 26 T 32 T 32 3.2 Các giới hạn tổ hợp ®é phøc t¹p ®iĨm nèi 27 T 32 T 32 3.2.1 C¸c kÕt nèi ®iÓm - ®iÓm 28 T 32 T 32 3.2.2 Chun m¹ch ®a ®iĨm……….……………………………………… 28 T 32 3.2.3 C¸c bé tËp trung 29 T 32 T 32 3.2.4 Bé siªu tËp trung 29 T 32 T 32 3.2.5 Các mạng chÐp 30 T 32 T 32 3.3 Phân tách tầng siêu tập trung nén 30 T 32 T 32 3.4 TÝnh hai mặt (Dual) - Các siêu tập trung mạng phân tán 34 T 32 T 32 3.5 Xây dựng mạng chép 34 T 32 T 32 3.6.Xây dựng mạng đa điểm 37 T 32 T 32 Ch ơng 4: Từ chuyển mạch kênh đa tốc độ ®Õn chun m¹ch gãi nhanh 39 T 32 T 32 4.1.Truy lùng kênh theo độ sâu tìm kiếm 39 T 32 T 32 4.2.Liên kết điểm - điểm củaTDM đa khe 41 T 32 T 32 4.3.Chun m¹ch gãi nhanh 43 T 32 T 32 4.4 Mạng Banyan tự định tuyến 47 T 32 T 32 Ch ơng 5: ứng dụng xếp cho chuyển mạch không nghẽn tự định T 32 tuyÕn 48 T 32 5.1 Các kiểu nghẽn chuyển mạch gói 48 T 32 T 32 5.1.1 NghÏn néi t¹i: 48 T 32 T 32 5.1.2.Nghẽn đầu ra: 48 T 32 T 32 5.1.3 Nghẽn đầu đ ờng HOL (Head of Line) 49 T 32 T 32 5.2 Các mạng xếp loại bỏ nghẽn nội 50 T 32 T 32 5.3 Giải xung đột đầu đối víi chun m¹ch gãi 55 T 32 T 32 5.3.1 S¾p xÕp–thanh läc–tËp trung víi nhập vào lại gói bị nghẽn 57 T 32 T 32 5.3.2 Thăm dò nhận biêt gửi với đệm đầu vào cho gói bị ứ đọng 58 T 32 T 32 5.4 Làm giảm nghẽn đầu hàng (HOL) 60 T 32 T 32 5.4.1 Cho phÐp c¸c gãi sau gãi HOL tranh chấp đầu 60 T 32 T 32 5.4.2 Cho phÐp gi¶i phãng nhiỊu lần gói HOL xung đột đến đệm T 32 đầu 61 T 32 5.5 Kết luận chuyển mạch gói kênh tÝch hỵp 61 T 32 T 32 PhÇn II: Lý thuyÕt l u l ợng mạng tích hợp băng rộng Mở đầu 64 T 32 T 32 Ch ơng 6: L u l ợng đầu cuối kết hỵp 65 T 32 T 32 6.1.Đầu T 32 cuối với mô hình trạng thái hữu hạn 65 6.2.Mô hình chuyển trạng th¸i 67 T 32 T 32 6.3 Xác suất trạng thái ổn định (Stateady State Probabilities) 69 3T T 32 6.3.1.Quá trình Markov 69 T 32 T 32 6.3.2.Qúa trình bán Markov 70 T 32 T 32 6.3.3 Quá trình luân phiên làm trạng thái 70 T 32 T 32 6.4 XÕp chång l u l ỵng 71 T 32 T 32 6.4.1 Xếp chồng trình luân phiên làm trạng thái đồng dạng 72 T 32 T 32 6.4.2 Phân bố poisson hội tụ phân bố nhị thức 72 T 32 6.4.3 Các trình Poisson 73 T 32 T 32 6.4.4 Sự hội tụ trình làm luân phiên xếp chồng tới trình T 32 Poisson 74 6.5 Ph©n bè l u l ợng qúa trình luân phiên trạng th¸i 75 T 32 T 32 T 32 6.6 Phân bố l u l ợng trình Poisson 76 T 32 T 32 6.7 Các giới hạn băng rộng vµ lt sè lín 79 T 32 T 32 6.8 Ước l ợng phân bố đuôi l u l ợng 81 T 32 T 32 Ch ơng 7: Nghẽn chia tài nguyên đơn tầng 82 T 32 T 32 7.1 Chia sẻ tài nguyên hữu hạn 82 T 32 T 32 7.2.Chuỗi Markov bị xén xác suất ứ ®äng 84 T 32 T 32 7.3 Tính không nhạy xác suất ø ®äng (Insensivity of Bloking Probabilities) 89 T 32 T 32 7.4 Ph ơng pháp ngẫu nhiên t ơng đ ¬ng 94 T 32 T 32 7.4.1 L u l ợng đa tèc ®é víi sù ®Õn Poisson 95 T 32 T 32 7.4.2 Quá trình l u l ỵng 96 T 32 T 32 7.5 Kỹ thuật l u l ợng cho đầu cuối ®a tèc ®é 97 T 32 T 32 7.6 Phân phối băng thông c¸c cc gäi cơm 101 T 32 T 32 Ch ¬ng 8: nghÏn chia sẻ tài nguyên đa tầng 103 T 32 T 32 8.1.Bài toán chia sẻ tài nguyên đa tiện nghi 103 T 32 T 32 8.2.NghÏn ®èi víi ®Þnh h íng ® êng nhÊt 104 T 32 T 32 8.3 Định h ớng đ ờng luân phiên ph ơng ph¸p Lee 105 T 32 T 32 8.3.1 Các mạng chuổi song song 107 T 32 T 32 8.3.2 Các mạng chuổi song song 109 T 32 T 32 8.4 Các giả thuyết để xấp xỉ xác suất nghÏn 110 T 32 T 32 8.4.1 Giả thuyết đối xứng đầu cuối 110 T 32 T 32 8.4.2 T 32 Giả thuyết đối xứng mạng.110 8.4.3 Giả thuyết đ ờng độc lập 111 T 32 T 32 8.4.4 Giả thuyết tuyến độc lập 112 T 32 T 32 8.5 Định tuyến đ ờng luân phiên -Ph ơng pháp Jacobaeus 112 T 32 T 32 8.5.1.NhÞ thức if nhị thức gi 113 T 32 T 32 8.5.2 fi phân bố nhị thức vàj gphân bố erlang 114 T 32 T 32 8.5.3 fi Phân bố erlang igphân bố nhị thøc 114 T 32 T 32 8.5.4 Cả fi lẫn gi phân bố Erlang 114 T 32 T 32 8.6 Độ phức tạp mạng không nghẽn bất đối xứng 115 T 32 T 32 Ch ơng 9: Vấn đề xây dựng mạng tích hợp băng rộng Việt Nam nói T 32 chung tỉnh Đắklắk nãi riªng 119 T 32 9.1 Khái niệm chung mạng b»ng réng (B-ISDN) 119 T 32 T 32 9.2.Sự phát triển thị tr ờng viễn thông Việt Nam đầu kỷ 21 121 T 32 T 32 9.3 Sù ph¸t triĨn mạng viễn thông tỉnh Đăklăk 122 T 32 T 32 9.3.1 Giíi thiƯu chung Đắklắk 122 T 32 T 32 9.3.2 HƯ thèng trun dÉn 123 T 32 T 32 9.3.3.HƯ thèng chun m¹ch 123 T 32 T 32 9.3.4 Hệ thống mạng di động 124 T 32 T 32 9.3.5 HƯ thèng m¹ng trun sè liƯu tØnh 124 T 32 T 32 9.4 Thết lập mạng viễn thông B-ISDN 125 T 32 T 32 9.4.1.Cấu trúc mạng viễn thông ATM (hình 9.1) 126 T 32 T 32 9.4.2.Các giao diện mạng viến thông ATM 127 T 32 T 32 9.4.3.ThiÕt lËp m¹ng B-ISDN 127 T 32 T 32 KÕt luËn 129 T 32 T 32 Phô lôc A: Néi dung nh·n 130 T 32 T 32 Phô lục B: Điều kiện không nghẽn mạng Banyan 132 T 32 T 32 Phô lục C: mạng tự định tuyến giới hạn tổ hợp mạng banyan 133 T 32 T 32 Phơ lơc D: XÊp xØ ®é lƯch lín ®· c¶i thiƯn 144 T 32 T 32 Tài liệu tham khảo 148 T 32 T 32 ... đầu vào mạng Cantor đ ợc kết nối đến đầu vào t ơng ứng m mạng Benes (hình 2.9) thông qua ghép kênh giải ghép kênh Nói cách khác, đầu vào thứ i mạng Cantor đ ợc kết nối đến đầu vào thứ i mạng. .. thay trục thời gian trục không gian Các khe đầu đ ợc ánh xạ vào Khung đầu vào m khe Tuần tự đọc tõ bé ®Ưm Đầu vào Đọc vào Một kết nối đầu vào- đầu Khung đầu n khe Đầu Đọc ngẫu nhiên Chuyển mạch không... vào xếp đ ợc sử dụng nh để giải chúng Nhớ lại ch ơng 4, ta đà yêu cầu kết nối đầu vào mạng Banyan gắn bó theo thứ tự hoàn toàn tăng, đ ờng đầu vào? ?ầu tuyến rời rạc (link disjoint) khiến cho mạng