Chương 1 và điểm qua các các phương pháp có thẻ sử dụng đề giải bài toán. DANH MUC CAC TU VIET TAT “Thuật ngữ tiếng anh Đề xuất tiếng việt Viết tắt Open Shortest-path fist Mở đường ngắn nhất đâu tiên OSPF Galled equal.costriult-pali | Tương đường chỉ phí đã đường ECMP Interme-diate system to Hệ thông trung gian này den hệ ISIS Interme-diate system thống trung gian khác Internet Protocol Giao thie internet IP Transmission Control Protocol | Giao thức điều khiển truyền dần TCP Demand volume units Đơn vị khối lượng yêu câu DVU Link capacity units Đơn vị công suất liên kết LCU Packets per second Số gỏi tin trên giây. PPS Linear programming Lập trình tuyển tỉnh LP Branch-and-cut Nhanh va cat BC Branch-and-bound Nhanh va can BB Mixed integer propa Lập¬rtrình sốx nguyêneehỗn hợp MIP Sintlated annealing NiSpHôtg Thiện Khi SAN Lagrangian relaxation Noi long Lagrang LR DANH MỤC CÁC HÌNH Hình 1.1 Minh họa của quy tắc tách luông ECMP.2 So sánh chức năng Fortz-Thorup và Chức năng Ä⁄/A// 1 chỉ phí liên kết (hiển thị cho e e =1).3 Bốn-nút của mạng "kim cương" với ví dụ để minh họa "nghịch lý" hành vi trong gói các gói mạng. LOI CAM DOAN Tôi - Vũ Thị Thúy, học viên lớp cao học Công nghệ thông tin khóa 2012A Trưởng Đại học Bách Khoa Hà Nội - cam kết luận vẫn tốt nghiệp là quá trình nghiên cứu của bản thân tôi đưởi sự hướng dân cửa PGS.T5 Nguyễn Đức Nghĩa - Viện Công, Nghệ Thông Tin và Truyền Thông , Dai hoc Bach Khoa 11a Noi.
Các kết quả nêu trong luận văn tốt nghiệp là trung thực, không sao chép hiện văn của bất kỳ công trinh nảo khác. Hà Nội, ngày 18 tháng 9 năm 2014 Học viên: Vũ Thị Thúy Lớp: Cao học CNTT - 2012A. LÒI CẢM ƠN Tdi xin bay 16 long biết ơn sâu sắc tới PGS.TS Nguyễn Đức Nghĩa - Bộ môn Khoa học máy tính - Viện Công Nghệ Thông Tin vả Truyền Thông - Trường Đại hoc Bach Khoa IIA Nội đã hướng dẫn rất tận tỉnh cho tôi trong suốt quả trình thực hiện luận văn. Những quan tâm chỉ bão, ý kiến đóng góp quý bán của Thấy, tôi mới có thể hoàn thánh luận văn này.
Tôi xin chân thành cảm en các Thầy, Cỏ giáo Trang Bai hoc Bach Khoa nổi chung, Viện Công Nghệ Thông Tân và Truyền Thông nói riêngđã tận tình giảng dạy truyền dạt cho tỏi những kiến thúc, kinh nghiệm quý bảu trong suốt những năm. học vừa qua Tôi xin chân thành cẩm ơn gia đình, người thôn đã hết lòng hỗ trợ về vật chất lẫn tính thần giúp tôi yêu tâm học và nghiên cứu trong quá trình học tập va thục hiện luận văn. DANH MỤC CÁC HÌNH Hình 1.1 Minh họa của quy tắc tách luông ECMP.2 So sánh chức năng Fortz-Thorup và Chức năng Ä⁄/A// 1 chỉ phí liên kết (hiển thị cho e e =1).3 Bốn-nút của mạng "kim cương" với ví dụ để minh họa "nghịch lý" hành vi trong gói các gói mạng. DANH MỤC CÁC HÌNH Hình 1.1 Minh họa của quy tắc tách luông ECMP.2 So sánh chức năng Fortz-Thorup và Chức năng Ä⁄/A// 1 chỉ phí liên kết (hiển thị cho e e =1).3 Bốn-nút của mạng "kim cương" với ví dụ để minh họa "nghịch lý" hành vi trong gói các gói mạng.
LÒI CẢM ƠN Tdi xin bay 16 long biết ơn sâu sắc tới PGS.TS Nguyễn Đức Nghĩa - Bộ môn Khoa học máy tính - Viện Công Nghệ Thông Tin vả Truyền Thông - Trường Đại hoc Bach Khoa IIA Nội đã hướng dẫn rất tận tỉnh cho tôi trong suốt quả trình thực hiện luận văn. Những quan tâm chỉ bão, ý kiến đóng góp quý bán của Thấy, tôi mới có thể hoàn thánh luận văn này. Tôi xin chân thành cảm en các Thầy, Cỏ giáo Trang Bai hoc Bach Khoa nổi chung, Viện Công Nghệ Thông Tân và Truyền Thông nói riêngđã tận tình giảng dạy truyền dạt cho tỏi những kiến thúc, kinh nghiệm quý bảu trong suốt những năm. học vừa qua Tôi xin chân thành cẩm ơn gia đình, người thôn đã hết lòng hỗ trợ về vật chất lẫn tính thần giúp tôi yêu tâm học và nghiên cứu trong quá trình học tập va thục hiện luận văn.
CHUONG I: BAI TOAN THIET KE MANG VOI DUONG TRUYEN NGAN NHAT Nguyên tắc của định tuyển ngắn nhất trong các mang gói là tính khả thi vỉ nó giải quyết sự ôn định trong việc hoán đổi giữa việc thực hiện định tuyển phức tạp và tính hiệu quả của đường truyền. Ưu điểm chính của việc định tuyến bằng đường đi ngắn nhất là nó có thể được thực hiện bằng cách phân phổi, không mất quả nhiều tính hiệu quả của đường truyền có thẻ đạt được với các chiên lược định tuyển phức tạp hơn. Ý tưởng là đề chỉ định một số đo chỉ phí (lưu lượng) cho môi liên kết trong. mạng, và định tuyến các gói đang đến tới một mut bang cách sử dụng định tuyển ngắn nhất dần đền gói đích, trong đỏ chỉ phí đường đi (độ dài) được tính bằng số đo.
Nút là số đo hiện tại được sử dụng cho các liên kết, và sử dụng đường định tuyển ngắn nhất tới các điểm đến khác, việc lưu trữ trong bảng định tuyến của hop tiếp theo cho mỗi điểm đến. Khi vỉ một lý do các số đo trong hệ thông được thay đồi (ví dụ, khi một liên kết thất bại, sau đó nó được gán một trọng lượng vô hạn), các nút được thông bảo về những thay đôi một cách phân phỏi thông qua một cơ chẻ giao thức nơi người khởi tạo (vi dụ, nút mả một liên kết không được kết nói) tạo ra các số đo liên kết (một thông tin khác vẻ thử liên kếU, được gọi là trạng thái kết nói trong, trường hợp OSPF, và nỏ tràn ngập tới tất cả các định tuyên trên liên mạng tràn toàn mạng này thường được goi là trang thái kết nỏi trong một giao thức định tuyển trạng thải liên kết. Khi một nút nhận được trạng thái của liên kết cụ thể được cập nhật nó tại địa phương có thể tái tỉnh toán và cập nhật các đường dẫn ngắn nhất. Ca giao thie OSPF va IS-IS déu str dung một số phiên bản của Dijkstra về thuật toán định tuyển đường đi ngắn nhất cho việc tỉnh sơ bộ đường đi tại định tuyên tại các nút, dựa trên các metrie được biết đến cho môi liên kết trong mạng.
Một cách chọn lọc là tập hợp các các liên kết metric chí phí cho tắt cả các liên kết được gọi là hệ thông liên kết metric hoặc hệ thông trọng lượng liên kết. Một thực tế phỏ biến là sử dụng định tuyển trung gian cô định (tất cả trọng lượng liên kết bằng 1), hoặc nghịch đảo của tốc độ liên kết như các các liên kết metric LOI NOI DAU Các thuật toán về đường truyền ngắn nhất đã được giới thiệu trong các công trình của Bellnan, Ford và Dijkstra từ những năm 1950. Sự khác biệt giữa hai thuật toán Belhnan-Ford và Dijkstra là cách sử dụng đường đi ngắn nhất đề chuyên thông. tin cân thiết đến máy tính.
Trong bồi cảnh mạng chuyên mạch gói và Internet định tuyến, đặc biệt là thuật toản của Bellnan-Ford đã thúc đây sự phát triển của giao thức định tuyển theo vector khoảng cách, trong khi đỏ thuật toán của Dijkstra đã mở đường cho sự ra đời của giao thức định tuyên thông bao trang thái liên kết của [Hui00]. Luận văn nảy tập trung vảo các bài toán thiết kế mạng (NDP) liên quan đến các giao thức định tuyển sau khi chúng được sử dụng phô biến như sự triển khai giao thức mở đường ngắn nhất đầu tiên (OSPF) vả hệ thống trung gian này đến hệ thống trung gian khác (IS-IS) - là những giao thức Internet trong nội bộ miễn giao thức định tuyển phô biến nhất. Đường đi định tuyển đối ứng ngắn nhất của công suất lưu lượng đa - hàng hóa cổ điền bao gồm việc thêm băng thông cho các liên kết mạng với việc đồng thời tái tôi tu hỏa các hệ thông trọng lượng liên kết. Cả hai loại bài toán nảy khác nhau bởi đổi tác cô điện trong trong trường hợp đường đi định tuyên ngắn nhất là các trọng liên kết (xác định nhu cầu dòng chảy) mả là các biến quyết định, chứ không phải là dòng yêu cầu.
Bài toán nảy đã nhận được sự chú ý đáng kế cho việc nghiên cửu định tuyên Internet trong những năm gần đây. Trong luận văn nảy em xin đẻ cập chủ yêu vẻ việc xây dựng và giải quyết các bài toán thiết kế (liên quan đền tối ưu hóa hệ thông trọng lượng) đường truyền ngắn nhật của bộ định tuyên OSPF /IS-IS. Luận văn bao gồm 4 chương: Chương 1 “Bải toản. thiết kế mạng với đường truyền ngăn nhật” giới thiệu những bài toán liên quan đến tìm đường định tuyển ngắn nhất, xem xét các mục tiêu tối ưu hóa khác nhau và trình bảy một ví dụ minh họa.
Chương 2 khảo sát mô hình quy hoạch nguyên hỗn hợp (MIP) cho bài toán định tuyên đường truyền ngắn nhất với ràng buộc độ trễ của liên kết được để cập trong Chương 1 và điểm qua các các phương pháp có thẻ sử dụng đề giải bài toán. CHUONG I: BAI TOAN THIET KE MANG VOI DUONG TRUYEN NGAN NHAT Nguyên tắc của định tuyển ngắn nhất trong các mang gói là tính khả thi vỉ nó giải quyết sự ôn định trong việc hoán đổi giữa việc thực hiện định tuyển phức tạp và tính hiệu quả của đường truyền. Ưu điểm chính của việc định tuyến bằng đường đi ngắn nhất là nó có thể được thực hiện bằng cách phân phổi, không mất quả nhiều tính hiệu quả của đường truyền có thẻ đạt được với các chiên lược định tuyển phức tạp hơn. Ý tưởng là đề chỉ định một số đo chỉ phí (lưu lượng) cho môi liên kết trong.
mạng, và định tuyến các gói đang đến tới một mut bang cách sử dụng định tuyển ngắn nhất dần đền gói đích, trong đỏ chỉ phí đường đi (độ dài) được tính bằng số đo. Nút là số đo hiện tại được sử dụng cho các liên kết, và sử dụng đường định tuyển ngắn nhất tới các điểm đến khác, việc lưu trữ trong bảng định tuyến của hop tiếp theo cho mỗi điểm đến. Khi vỉ một lý do các số đo trong hệ thông được thay đồi (ví dụ, khi một liên kết thất bại, sau đó nó được gán một trọng lượng vô hạn), các nút được thông bảo về những thay đôi một cách phân phỏi thông qua một cơ chẻ giao thức nơi người khởi tạo (vi dụ, nút mả một liên kết không được kết nói) tạo ra các số đo liên kết (một thông tin khác vẻ thử liên kếU, được gọi là trạng thái kết nói trong, trường hợp OSPF, và nỏ tràn ngập tới tất cả các định tuyên trên liên mạng tràn toàn mạng này thường được goi là trang thái kết nỏi trong một giao thức định tuyển trạng thải liên kết.