Luận án Cơ chế khắc phục lỗi kênh khi kết nối MultiCast trong mạng MPLS

BỘ GIÁO DỤC VÀ ĐÀO TẠO TỔNG CÔNG TY BƯU CHÍNH VIỄN THÔNG VIỆT NAM HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ------------------------------------------------- NGUYỄN VIỆT CƯỜNG CƠ CHẾ KHẮC PHỤC LỖI KÊNH KHI KẾT NỐI MULTICAST TRONG MẠNG MPLS Chuyên ngành:...................... Mã số:................................... LUẬN ÁN THẠC SỸ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. NGUYỄN KIM LAN Hà nội 07-2003 --ii-- TÓM TẮT Lỗi kênh là một trong những nguyên nhân chủ yếu gây ra hiện tượng gián đoạn dịch vụ trong mạng viễn thông. Khi một kênh trong mạng bị lỗi thì tất cả các dịch vụ truyền thông sử dụng kênh lỗi đó sẽ bị gián đoạn tạm thời. Phương pháp thường được sử dụng để hạn chế hậu quả của lỗi phần cứng trong mạng là định tuyến lại lưu lượng đang truyền trên kênh lỗi sang kênh khác. Khi được thực hiện tại các lớp thấp thì việc định tuyến lại diễn ra nhanh tuy nhiên nó đòi hỏi phải đầu tư bổ sung phần cứng dự phòng. Việc định tuyến lại cũng có thể được thực hiện tại các lớp cao hơn dựa trên cơ chế điều khiển phần mềm, tuy nhiên giải pháp này chậm. Hơn nữa hầu hết các cơ chế định tuyến lại không được tối ưu cho các ứng dụng kết nối Multicast chẳng hạn như hội nghị từ xa trong đó một phía gửi phải gửi thông tin cho nhiều phía nhận. Internet là mạng chuyển mạch gói Datagram trong đó dữ liệu được tải trong các gói tin IP. Gần đây chuyển mạch nhãn đa giao thức (MPLS) được đưa vào sử dụng để tải các gói IP trên các kênh ảo, MPLS đã kết hợp được các ưu điểm của chuyển mạch gói Datagram và chuyển mạch kênh ảo. Trong luận văn này, chúng tôi đi vào nghiên cứu giải pháp bảo vệ các kết nối Multicast trong mạng MPLS khi xảy ra hiện tượng lỗi kênh. Luận văn cũng đưa ra thuật toán lựa chọn kênh dự phòng trong một cây định tuyến Multicast đang tải lưu lượng Multicast. Tuyến dự phòng phải chọn sao cho số lượng nút nhận bị tách rời khỏi một kết nối Multicast là nhỏ nhất khi một kênh trong cây bị lỗi. Luận văn cũng đưa ra thuật toán định tuyến lại nhanh đối với kết nối Multicast trong mạng MPLS, đây là một cơ chế mạng MPLS sử dụng để định tuyến lại luồng lưu lượng sang tuyến dự phòng khi có lỗi một kênh trong kết nối Multicast. --iii-- MỤC LỤC DANH SÁCH HÌNH VẼ ................................................................................................................................ V DANH SÁCH BẢNG................................................................................................................................... VII TỪ VIẾT TẮT ............................................................................................................................................VIII CHƯƠNG I. GIỚI THIỆU ..................................................................................................................... 1 I.1. Các công nghệ chuyển mạch............................................................................................................ 2 I.1.1. Chuyển mạch kênh ................................................................................................................... 2 I.1.2. Chuyển mạch gói Datagram .................................................................................................... 4 I.1.3. Chuyển mạch gói kênh ảo ........................................................................................................ 5 I.1.4. MPLS ....................................................................................................................................... 8 I.2. Multicast .......................................................................................................................................... 13 I.2.1. Cấu trúc cây định tuyến Multicast ......................................................................................... 14 I.2.2. Multicast trong mạng IP ........................................................................................................ 16 I.2.3. Multicast trên nền ATM ......................................................................................................... 18 I.2.4. Multicast trên nền MPLS ....................................................................................................... 19 I.3. Đóng góp của luận văn................................................................................................................... 20 CHƯƠNG II. TÍNH “ĐÀN HồI” VÀ BẢO VỆ TRONG MẠNG ....................................................... 23 II.1. Tổng quan về định tuyến lại ..................................................................................................... 24 II.2. Bảo vệ tại lớp MAC và lớp vật lý - vòng Ring tự hồi phục .................................................... 26 II.3. Bảo vệ tại lớp mạng................................................................................................................... 29 II.4. Định tuyến lại nhanh kết nối Unicast trong mạng MPLS...................................................... 30 II.5. Hồi phục khi lỗi kết nối Multicast ............................................................................................ 32 CHƯƠNG III. THUẬT TOÁN SỬA LỖI CÂY ĐỊNH TUYẾN MULTICAST................................... 35 III.1. Mô hình hoá vấn đề................................................................................................................... 36 III.2. Cực đại độ “đàn hồi” của cây với một đường dự phòng........................................................ 44 III.2.1. Thuật toán chính ............................................................................................................... 44 III.2.2. Phiên bản mở rộng............................................................................................................ 48 III.3. Tính toán các đại lượng ............................................................................................................ 51 CHƯƠNG IV. ĐỊINH TUYẾN LẠI NHANH MPLS MULTICAST .................................................... 54 IV.1. Tổng quan .................................................................................................................................. 54 IV.2. Phát hiện lỗi kênh và hồi phục ................................................................................................. 58 --iv-- IV.3. Thông báo lỗi và hồi phục......................................................................................................... 62 IV.4. Switchover và Switchback.......................................................................................................... 64 CHƯƠNG V. TRIỂN KHAI ĐỊNH TUYẾN MULTICAST TRONG MPLS..................................... 69 V.1. Multicast MPLS-Linux.............................................................................................................. 69 V.1.1. Triển khai MPLS-Linux Unicast ............................................................................................ 69 V.1.2. Triển khai MPLS-Linux Multicast.......................................................................................... 74 V.1.3. Giao diện lập trình ứng dụng (API) quản lý FIB................................................................... 77 V.2. Giao thức MulTreeLDP............................................................................................................ 79 V.2.1. Định tuyến hiện Multicast ...................................................................................................... 81 V.2.2. Phát hiện kênh lỗi và kênh phục hồi ...................................................................................... 87 V.2.3. Thông báo kênh lỗi và kênh hồi phục..................................................................................... 87 V.2.4. Switchover và switchback ...................................................................................................... 90 CHƯƠNG VI. THỬ NGHIỆM ............................................................................................................... 92 CHƯƠNG VII. KẾT LUẬN...................................................................................................................... 93 VII.1. Các đóng góp của luận văn....................................................................................................... 94 VII.2. Định hướng nghiên cứu trong tương lai.................................................................................. 95 --v-- DANH SÁCH HÌNH VẼ Hình I-1. Đặc điểm chuyển mạch kênh.............................................................................................................. 2 Hình I-2. Đặc điểm chuyển mạch gói Datagram ............................................................................................... 5 Hình I-3. Đặc điểm chuyển mạch gói kênh ảo................................................................................................... 6 Hình I-4. Vị trí của ngăn xếp mào đầu MPLS ................................................................................................... 8 Hình I-5. Chuyển tiếp các gói tin MPLS ........................................................................................................... 9 Hình I-6. Xếp chồng các miền MPLS.............................................................................................................. 11 Hình I-7. Các chế độ phân phối nhãn trên Downstream .................................................................................. 12 Hình I-8. Thực hiện kết nối Multicast thông qua các kết nối Unicast ............................................................. 13 Hình I-9. Cây đường ngắn nhất. ...................................................................................................................... 15 Hình I-10. Cây nút cơ sở.................................................................................................................................. 16 Hình I-11. Đường dự phòng định trước trong cây định tuyến Multicast ......................................................... 16 Hình I-12. Cây định tuyến MPLS Multicast .................................................................................................... 22 Hình II-1. Khái niệm định tuyến lại................................................................................................................. 25 Hình II-2. Vòng Ring chuyển mạch một hướng (UPSR)................................................................................. 27 Hình II-3. Vòng Ring chuyển mạch hai hướng (BLSR) .................................................................................. 28 Hình II-4. Chuyển mạch bảo vệ thông minh trong RPR.................................................................................. 29 Hình II-5. Cơ chế định tuyến lại nhanh MPLS Unicast................................................................................... 32 Hình III-1. Mạng và mô hình nhóm Multicast................................................................................................. 35 Hình III-2. Trọng số tốc độ lỗi kênh ................................................................................................................ 38 Hình III-3. Bảo vệ cây định tuyến bằng một đường dự phòng khi lỗi một kênh ............................................. 41 Hình III-4 Giá trị w, tdrop và adrop của các kênh của một cây....................................................................... 42 Hình III-5. Chứng minh thuật toán .................................................................................................................. 47 Hình III-6. Sự thay đổi cấu trúc cây khi một nút “lá” rời bỏ hoặc gia nhập nhóm ......................................... 48 Hình III-7. Tính đại lượng Rd(A;B).................................................................................................................. 52 Hình IV-1. Ví dụ đường chuyển mạch nhãn (LSP) Multicast. ........................................................................ 56 Hình IV-2. Định tuyến lại nhanh MPLS Multicast .......................................................................................... 57 Hình IV-3. Cơ chế phát hiện lỗi kênh .............................................................................................................. 60 Hình IV-4. Hám mật độ xác suất của thời gian phát hiện kênh lỗi .................................................................. 60 --vi-- Hình IV-5. Cơ chế phát hiện kênh được sửa.................................................................................................... 61 Hình IV-6. Hàm mật độ xác suất của thời gian phát hiện kênh được sửa........................................................ 62 Hình IV-7. Cơ chế thông báo kênh lỗi............................................................................................................. 63 Hình IV-8. “ánh xạ” nhãn dự phòng............................................................................................................... 65 Hình IV-9. Đường truyền gói do J gửi đi sau khi Switchover ......................................................................... 66 Hình IV-10. Nhận lặp lại gói tin trong quá trình Switchback .......................................................................... 68 Hình V-1. Xử lý gói tin tại lớp MPLS trong MPLS-Linux Unicast................................................................. 71 Hình V-2. Xử lý gói tin tại lớp MPLS trong MPLS-Linux Multicast.............................................................. 72 Hình V-3. Chuyển tiếp hỗn hợp L2/L3............................................................................................................ 77 Hình V-4. Định dạng bản tin MulTreeLDP. .................................................................................................... 80 Hình V-5. Biểu diễm một cây dạng File và dạng Cây tuyến hiện TLV........................................................... 82 Hình V-6. Thông báo cây định tuyến Multicast............................................................................................... 84 Hình V-7 Định dạng bản tin kiểm tra phát hiện kênh lỗi và kênh hồi phục..................................................... 87 Hình V-8. Thông báo lỗi và hồi phục .............................................................................................................. 90 Hình V-9 Sửa đổi bảng chuyển tiếp tại một PSL trong Switchback và Switchover ......................................... 91 --vii-- DANH SÁCH BẢNG Bảng V-1. Các lệnh của MPLS-Linux Unicast................................................................................................ 70 Bảng V-2. Thực hiện các hoạt động MPLS dựa trên các lệnh của MPLS-Linux. ........................................... 70 Bảng V-3. Tổng quan về hai lệnh MPLS-Linux Multicast .............................................................................. 74 Bảng V-4. Triển khai các hoạt động MPLS Multicast..................................................................................... 75 Bảng V-5. Các File /proc dạng Text có liên quan đến MPLS FIB.................................................................. 77 Bảng V-6. Hàm Netlink và C API tương ứng để tạo luật chuyển tiếp MPLS.................................................. 78 Bảng V-7. Các API thao tác với FIB. .............................................................................................................. 79 --viii-- TỪ VIẾT TẮT Viết tắt Tiếng Anh Tiếng Việt AAL ATM Adaptation Layer Lớp tương thích ATM AAL5 ATM Adaptation Layer Five Lớp tương thích ATM loại 5 APS Automatic Protection Switching Tự động chuyển mạch bảo vệ ARP Address Resolution Protocol Giao thức phân tích địa chỉ ATM Asynchronous Transfer Mode Chế độ chuyển giao không đồng bộ BLSR Bidirectional Link-Switched Ring Vòng Ring chuyển mạch hai hướng bos bottom of stack Cuối ngăn xếp BUS Broadcast and Unknown Server Máy chủ truyền thông quảng bá CBT Core Based Tree Cây nút cơ sở CR-LDP Constraint Routing LDP Định tuyến cưỡng bức LDP DVMRP Distance Vector Multicast Routing Protocol Giao thức định tuyến Multicast vector khoảng cách FDDI Fiber Distributed Data Interface FDM Frequency Division Multiplexing Ghép kênh phân chia theo tần số FEC Forwarding Equivalence Class Lớp chuyển tiếp tương đương FIB Forwarding Information Base Cơ sở dữ liệu chuyển tiếp thông tin FTN FEC-to-NHLFE FEC ứng với NHLFE IGMP Internet Group Management Protocol Giao thức quản lý nhóm Internet ILM Incoming Label Map Chuyển đổi nhãn vào IP Internet Protocol Giao thức Internet IPS Intelligent Protection Switching Chuyển mạch bảo vệ thông minh IPv4 IP version 4 IP phiên bản 4 IPv6 IP version 6 IP phiên bản 6 LAN Local Area Network Mạng cục bộ LDP Label Distribution Protocol Giao thức phân phối nhãn LER Label Edge Router Bộ định tuyến biên nhãn LSP Label Switched Path Đường chuyển mạch nhãn LSR Label Switching Router Bộ định tuyến chuyển mạch nhãn MAC Media Access Control Điều khiển truy nhập môi trường MARS Multicast Address Resolution Server Máy chủ phân tích địa chỉ Multicast MCS Multicast Server model Mô hình máy chủ Multicast mLSP Multicast Label Switched Path Đường chuyển mạch nhãn Multicast MOSPF Multicast extention to OSPF Mở rộng Multicast cho OSPF MPLS Multiprotocol Label Switching Chuyển mạch nhãn đa giao thức MTBF Mean Time Between Failures Thời gian trung bình giữa các lỗi MulTreeLDP MULticast TREe rEpair Label Distribution Protocol Giao thức phân phối nhãn sửa cây định tuyến Multicast --ix-- Viết tắt Tiếng Anh Tiếng Việt NHLFE Next Hop Label Forwarding Entry Nhãn chuyển tiếp tới nút tiếp theo OSPF Open Shortest Path First Đường ngắn nhất PIM-SM Protocol Independent Multicast-Sparse Mode PML Path Merging LSR LSR hợp nhất đường PSL Path Switching LSR LSR chuyển mạch đường QoS Quality of Service Chất lượng dịch vụ RSVP ReSource ReserVation Protocol Giao thức dự trữ tài nguyên TDM Time Division Multiplexing Ghép kênh phân chia theo thời gian TLV Type-Length-Value ToS Type of Service Loại dịch vụ TTL Time To Live Thời gian sống UDP User Data Protocol Giao thức trao đổi dữ liệu đối tượng sử dụng UPSR Unidirectional Path-Switched Ring Vòng Ring chuyển mạch một hướng VC Virtual Circuits Kênh ảo VCI Virtual Circuit Identifier Nhận dạng kênh ảo VPI Virtual Path Identifier Nhận dạng đường ảo --1-- Chương I. Giới thiệu Đặc điểm chính của mạng chuyển mạch là vào phương thức truyền dữ liệu. Trong mạng chuyển mạch ra đời sớm nhất, luồng bit thông tin được truyền liên tục trên kênh vật lý và được gọi là chuyển mạch kênh, nó phù hợp để truyền tín hiệu thoại hoặc dữ liệu thời gian thực kết nối điểm - điểm (truyền thông Unicast). Tuy nhiên nếu có lỗi một kênh vật lý trong mạng chuyển mạch kênh sẽ dẫn đến gián đoạn toàn bộ các dịch vụ truyền thông được tải trên kênh lỗi. Mạng chuyển mạch gói Datagram (ví dụ như mạng Internet) đã khắc phục được hạn chế này bằng cách chia dữ liệu thành các phần nhỏ hơn và truyền đi trong các gói tin. Trong mạng chuyển mạch gói Datagram, hai gói tin liên tục từ một nguồn tin được mạng xử lý độc lập với nhau. Khi một kênh lỗi thì các gói tin trước đó được gửi trên kênh lỗi sẽ được định tuyến lại tránh kênh lỗi và do vậy truyền thông không bị gián đoạn. Mạng chuyển mạch gói Datagram có tính “đàn hồi” (là khả năng duy trì cung cấp dịch vụ trong trường hợp lỗi kênh) đối với lỗi kênh vì các đối tượng sử dụng không nhận biết được hiện tượng lỗi kênh. Tuy nhiên đặc điểm này lại dẫn đến một hạn chế của mạng chuyển mạch gói Datagram đó là rất khó quản lý luồng dữ liệu End-to-End. Cơ chế chuyển mạch gói kênh ảo được sử dụng trong X.25, ATM và g