Tài liệu Giải bài toán tối ưu mạng hỗ trợ kỹ thuật định tuyến đường đi ngắn nhất

1 LỜI NÓI ĐẦU Một mạng truyền thông cần truyền lưu lượng trên các tuyến truyền dẫn với băng thông khác nhau. Lưu lượng này có thể được định tuyến qua các đường khác nhau để đến đích. Bài toán đặt ra là làm thế nào để thiết kế mạng một cách hiệu quả dựa trên việc xem xét các tính chất của mạng, hay nói cách khác là làm thế nào để thiết kế mạng một cách tối ưu. Rất nhiều vấn đề trong thiết kế mạng có thể được giải quyết bằng cách xây dựng các mô hình toán học và dựa trên các giải thuật tối ưu. Trong luận văn này sẽ trình bày về một số phương pháp và giải thuật có thể ứng dụng để thiết kế mạng, sau đó đi sâu vào giải bài toán tối ưu mạng để hỗ trợ cho kĩ thuật định tuyến đường đi ngắn nhất (shortest-path routing). Nội dung của luận văn được chia thành 3 chương với các nội dung như sau. Chương 1 giới thiệu tổng quan về mạng viễn thông và vấn đề tối ưu hóa mạng, đặt ra bài toán cũng như là giới thiệu những khái niệm mang tính tiền đề và cơ sở cho các nghiên cứu tiếp theo. Chương 2 trình bày về những vấn đề kĩ thuật cơ bản trong tối ưu hóa mạng viễn thông. Với mỗi vấn đề sẽ đưa ra ra mô tả các yêu cầu tối ưu, các bước xây dựng bài toán và thảo luận về phương pháp giải bài toán. Chương 3 đi sâu vào giải quyết một số vấn đề cụ thể của bài toán tối ưu mạng xét từ góc độ kĩ thuật định tuyến đường đi ngắn nhất, xây dựng các phát biểu bài toán phù hợp và nghiên cứu các phương pháp cũng như giải thuật để giải quyết từng vấn đề. Do những lí do hạn chế, bản luận văn không tránh khỏi còn nhiều thiếu sót. Em rất mong nhận được những ý kiến đóng góp của các thầy cô và các đồng nghiệp để bản luận văn được hoàn thiện hơn. Cuối cùng, em xin chân thành cảm ơn thầy giáo, TS. Nguyễn Tiến Ban đã tận tình hướng dẫn em hoàn thành bản luận văn này. 2 MỤC LỤC LỜI NÓI ĐẦU 1 MỤC LỤC 2 THUẬT NGỮ VIẾT TẮT 4 DANH MỤC HÌNH VẼ 6 CHƯƠNG 1. TỔNG QUAN VỀ MẠNG VIỄN THÔNG VÀ YÊU CẦU TỐI ƯU MẠNG7 1.1 Đặt vấn đề 7 1.2 Mạng truyền thông và các miền quản trị 1.3 Khái niệm về lưu lượng và nhu cầu lưu lượng 9 13 1.3.1 Lưu lượng trong mạng Internet 14 1.3.2 Lưu lượng trong mạng điện thoại 1.3.3 Nhu cầu lưu lượng trong mạng truyền tải 16 1.3.4 Đơn vị đo dung lượng và nhu cầu lưu lượng 17 1.4 Khái niệm về định tuyến và luồng 18 1.5 Thiết kế mạng với kiến trúc đa lớp 19 1.6 Kết luận 16 21 CHƯƠNG 2. CÁC VẤN ĐỀ KĨ THUẬT TRONG TỐI ƯU HÓA MẠNG23 2.1 Bài toán luồng trên mạng 2.1.1 Mô tả vấn đề 2.1.2 Xây dựng bài toán 2.2 Vấn đề định cỡ 23 23 27 29 2.2.1 Mô tả vấn đề 29 2.2.2 Xây dựng bài toán 32 3 2.2.3 Giải bài toán bằng nguyên tắc phân luồng theo đường ngắn nhất 35 2.3 Nguyên lí định tuyến đường đi ngắn nhất 36 2.4 Nguyên lí cân bằng trong tối ưu mạng 39 2.5 Kết luận 41 CHƯƠNG 3. GIẢI BÀI TOÁN TỐI ƯU MẠNG HỖ TRỢ KĨ THUẬT ĐỊNH TUYẾN ĐƯỜNG ĐI NGẮN NHẤT 43 3.1 Bài toán định tuyến đường đi ngắn nhất 3.1.1 Phát biểu bài toán 43 3.1.2 Hiệu chỉnh bài toán 48 43 3.2 Định tuyến đường đi ngắn nhất và thời gian trễ mạng 50 3.3 Giải bài toán định tuyến đường ngắn nhất bằng qui hoạch nguyên hỗn hợp 53 3.4 Giải bài toán định tuyến đường ngắn nhất bằng phương pháp đối ngẫu 56 3.5 Giải thuật tối ưu hóa hệ thống metric liên kết dựa trên phương pháp Lagrangian nới lỏng 60 3.6 Kết luận KẾT LUẬN 64 66 TÀI LIỆU THAM KHẢO 67 4 THUẬT NGỮ VIẾT TẮT Từ viết tắt Tiếng Anh đầy đủ Tiếng Việt CPLA Candidate Path List Danh sách đường đi thích hợp DAR DCR Augmentation Dynamic Alternate Routing Dynamically Controlled Định tuyến thay thế động Định tuyến điều khiển động DCS Routing Digital Cross-connect Hệ thống kết nối chéo số DNHR Systems Dynamic Non-hierarchical Định tuyến không phân cấp DP DS-n DVU DXC Routing Dynamic Programming Digital Signal-n Demand Volume Unit Digital Cross-Connect động Quy hoạch động Tín hiệu số - n Đơn vị khối lượng nhu cầu Các hệ thống kết nối chéo số EA ECMP FD Gbps GoS GSPAR Systems Evolutionary Algorithm Equal Cost Multi-Path Flow Deviation Gigabits per Second Grade-of-Service Generalized Shortest Path Thuật toán tiến hoá Đẳng giá - đa đường Độ lệch luồng Gigabit trên giây Cấp độ dịch vụ Qui tắc cấp xác định đường đi IP IP IS-IS Allocation Rule Internet Protocol Integer Programming Intermediate System-to- ngắn nhất tổng quát Giao thức Internet Quy hoạch nguyên Giao thức định tuyến IS-IS ISP LCU LP LP LR LR LSP Intermediate System Internet Service Provider Link Capacity Unit Linear Programming Link Protection Lagrangian Relaxation Link Restoration Label Switched Path Nhà cung cấp dịch vụ Internet Đơn vị dung lượng liên kết Quy hoạch tuyến tính Bảo vệ liên kết Lagrangian nới lỏng Khôi phục liên kết Đường chuyển mạch nhãn 5 LSR Label Switch Router Bộ định tuyến chuyển mạch Mbps MIP Megabits per Second Mixed-Integer nhãn Megabit trên giây Quy hoạch nguyên hỗn hợp MMF NDP OSPF Programming Max-Min Fairness Network Design Problem Open Shortest Path First Cân bằng Max-Min Bài toán thiết kế mạng Giao thức chọn đường đi ngắn PG PP PR QoS RTNR nhất Path Generation Tạo luồng Path Protection Bảo về đường Path Restoration Khôi phục đường Qualiy-of-Service Chất lượng dịch vụ Real-Time Network Routing Định tuyến mạng theo thời gian SDH Synchronous Digital thực Phân cấp số đồng bộ SONET Hierarchy Synchronous Optical Mạng quang đồng bộ SPR TCP Network Shortest-Path Routing Transmission Control Định tuyến đường ngắn nhất Giao thức điều khiển truyền dẫn Protocol 6 DANH MỤC HÌNH VẼ Hình 1.1: Cấu trúc mạng điện thoại...........................................................................7 Hình 1.2: Cấu trúc mạng Internet..............................................................................8 Hình 1.3: Kết nối mạng của các nhà cung cấp.........................................................10 Hình 1.4: Miền quản trị mạng (đối tượng của bài toán thiết kế mạng)....................10 Hình 1.5: Nhiều miền quản trị khác nhau cùng sử dụng một nhà cung cấp mạng truyền tải.................................................................................................................. 12 Hình 1.6: Một miền quản trị sử dụng nhiều nhà cung cấp mạng truyền tải.............12 Hình 1.7: Nhiều mạng dịch vụ trên cùng một mạng truyền tải................................13 Hình 1.8: Mạng lưu lượng và mạng truyền tải.........................................................20 Hình 2.1: Ví dụ mạng 3 nút.....................................................................................23 Hình 2.2: Các đường (tuyến) có thể đối với mạng ba nút........................................24 Hình 2.3: Ví dụ mạng 4 nút.....................................................................................30 Hình 2.4: Ví dụ mạng 4 nút: khối lượng nhu cầu và giá của liên kết.......................32 Hình 2.5: Qui tắc phân chia đều ECMP...................................................................38 Hình 3.1: Minh họa ảnh hưởng của bài toán định tuyến đến thời gian trễ mạng.....50 7 CHƯƠNG 1. TỔNG QUAN VỀ MẠNG VIỄN THÔNG VÀ YÊU CẦU TỐI ƯU MẠNG 1.1 Đặt vấn đề Trong điện thoại cũng như Internet, topology hay cấu trúc kết nối các nút mạng có ảnh hưởng lớn đến hoạt động của mạng. Cấu trúc điển hình của mạng điện thoại và Internet thể hiện trên Hình 1.1 và Hình 1.2. Hình 1.1: Cấu trúc mạng điện thoại Trong khuôn khổ luận văn này chỉ đề cập đến phần giữa là mạng lõi hay còn gọi là mạng xương sống, bao gồm các bộ định tuyến hay thiết bị chuyển mạch kết nối với nhau. Lưu lượng đến (ingress traffic) được coi là lưu lượng đi vào mạng lõi, còn lưu lượng đi (egress traffic) là lưu lượng ra khỏi mạng lõi này. 8 Hình 1.2: Cấu trúc mạng Internet Một mạng truyền thông cần truyền lưu lượng trên các tuyến truyền dẫn với dung lượng (băng thông) khác nhau. Lưu lượng này có thể được định tuyến qua các đường khác nhau để đến đích. Chúng ta cần có đủ băng thông trên mạng để truyền lưu lượng, đồng thời giảm tỷ lệ từ chối cuộc gọi hoặc giảm độ trễ trung bình truyền gói dữ liệu trên mạng. Để làm được điều này, ta cần trả lời các câu hỏi sau: 1. Có thể tìm được tuyến tốt hơn không? 2. Có thể bổ sung thêm băng thông ở đâu? 3. Ở đâu và khi nào cần thêm các nút (và liên kết) cho mạng? 4. Tính chất đặc thù của kiến trúc mạng hay giao thức có thể ảnh hưởng đến việc ra quyết định như thế nào? 5. Mức độ trừu tượng hóa nào là thích hợp cho việc mô hình hóa từng mạng cụ thể để có thể nhận được những kết quả mong muốn? Bài toán đặt ra là làm thế nào để thiết kế các mạng lõi (sương sống) một cách hiệu quả dựa trên việc xem xét các tính chất của mạng, hay nói cách khác là làm thế nào để thiết kế mạng một cách tối ưu. Rất nhiều vấn đề có thể được giải quyết bằng cách xây dựng các mô hình toán học và dựa trên các giải thuật tối ưu. Trong luận văn này sẽ trình bày về một số phương pháp và giải thuật có thể ứng dụng để thiết 9 kế mạng, sau đó đi sâu vào giải bài toán tối ưu mạng để hỗ trợ cho kĩ thuật định tuyến đường đi ngắn nhất (shortest-path routing). 1.2 Mạng truyền thông và các miền quản trị Trên Hình 1.1 đã chỉ ra mô hình kiến trúc tổng quan của mạng điện thoại. Điểm quan trọng cần chú ý ở đây là một cuộc gọi có thể được hỗ trợ bởi nhiều nhà cung cấp mạng (hay còn gọi là nhà khai thác mạng) trên những phân đoạn khác nhau của cuộc gọi. Việc xử lý kết nối cuộc gọi trong mạng điện thoại sử dụng phương thức chuyển mạch kênh, trong đó một kênh riêng biệt được thiết lập cho mỗi cuộc gọi. Đối với mạng Internet toàn cầu (Hình 1.2), khi có yêu cầu trao đổi thông tin (ví dụ dịch vụ web) từ người sử dụng này đến người sử dụng khác, thì thông tin sẽ được truyền đi bởi nhiều nhà cung cấp mạng khác nhau (thông thường thì là các nhà cung cấp dịch vụ Internet – ISP). Về mặt kỹ thuật thì mạng của mỗi nhà cung cấp dịch vụ là một hệ thống tự trị riêng (Autonomous System – AS). Tương tự như trường hợp chuyển tiếp cuộc gọi điện thoại, các nhà cung cấp ở các phân đoạn mạng khác nhau cũng thực hiện việc truyền lưu lượng dữ liệu để hoàn thành việc chuyển yêu cầu web qua mạng. Các gói dữ liệu được tạo ra để đáp ứng yêu cầu này sẽ đi theo một hành trình ngược lại để đến nơi đã gửi đi yêu cầu. Trong cả hai hướng, hình thức chuyển mạch gói được sử dụng để định tuyến các gói dữ liệu qua mạng. Có thể thấy rằng, đối với cả hai trường hợp điện thoại và Internet, một yêu cầu (cuộc gọi hay giao dịch web) đi qua một loạt các mạng được duy trì bởi những nhà cung cấp khác nhau. Điều này có thể được minh họa trên Hình 1.3, trong đó mỗi mạng được mô tả như một đám mây. Hình 1.3: Kết nối mạng của các nhà cung cấp 10 Các nhà cung cấp cần phải có sự thỏa thuận với nhau để thực hiện việc truyền tải lưu lượng theo yêu cầu. Sự thỏa thuận giữa các nhà cung cấp láng giềng thường được xem như là thỏa thuận ngang hàng. Mỗi mạng có một số thiết bị định tuyến hay chuyển mạch của riêng mình, và các thiết bị tại biên mạng hay cổng giao tiếp (gateway) sẽ thực hiện nhiệm vụ truyền dữ liệu từ mạng này sang mạng khác. Như vậy, mỗi mạng sẽ tự phải biết làm thế nào để truyền dữ liệu bên trong mạng cũng như cần sử dụng bao nhiêu thiết bị định tuyến hay chuyển mạch để hoàn thành công việc này. Từ thực tế này thấy rằng vấn đề thiết kế mạng có thể được hạn chế bởi phạm vi bên trong mỗi mạng, hay miền quản trị (administrative domain) của nó như chỉ ra trên Hình 1.4. Hình 1.4: Miền quản trị mạng (đối tượng của bài toán thiết kế mạng) Mỗi miền quản trị sẽ tự tối ưu hoá các tuyến truyền dẫn của mình mà không quan tâm đến việc các miền khác kết nối với nó làm như thế nào để truyền dữ liệu. Trong mỗi mạng ta có một tập hợp các nút được kết nối với nhau bởi các liên kết (link). Trong trường hợp mạng điện thoại, các nút là tổng đài chuyển mạch thoại, còn liên kết thường được biết đến như là các đường trung kế hay nhóm trung kế. Trong trường hợp Internet, nút mạng là các bộ định tuyến, còn thuật ngữ liên kết đôi khi có thể được sử dụng để chỉ các giao diện hay các đường trung kế. Mạng toàn cầu được xem như bao gồm một loạt các mạng thành phần, được quản trị bởi 11 các nhà cung cấp khác nhau, trong đó mỗi nhà cung cấp sẽ đưa ra thiết kế phù hợp cho mạng của họ. Bên cạnh mạng điện thoại và Internet, trên thực tế còn có những cơ sở hạ tầng và mạng truyền thông khác nữa. Để phân biệt ta thường coi mạng điện thoại và Internet như là các mạng dịch vụ ứng dụng hay mạng lưu lượng. Một số mạng truyền thông riêng (khác với mạng công cộng như điện thoại hay Internet) được thiết lập cho các công ty lớn để truyền các luồng dữ liệu, thoại hay video của riêng họ. Mặc dù các công ty có thể duy trì các thiết bị chuyển mạch/định tuyến của riêng mình, trên thực tế họ thường thuê các phương tiện truyền dẫn vật lý của các nhà cung cấp khác. Nói cách khác, những công ty này là khách hàng của nhà cung cấp phương tiện mạng vật lí. Nhà cung cấp mạng vật lý để vận chuyển lưu lượng ứng dụng cho các mạng khách hàng khác nhau thường là các nhà khai thác viễn thông lớn. Để tăng tính hiệu quả về kinh tế, nhà khai thác viễn thông lớn có thể kết hợp nhiều luồng lưu lượng từ những đường riêng khác nhau vào trong một mạng. Thông thường, các mạng phương tiện vật lý này được biết đến như là mạng truyền tải (transport) hay truyền dẫn (transmission), có thể sử dụng nhiều công nghệ khác nhau như mạng quang đồng bộ (SONET), phân cấp số đồng bộ (SDH), công nghệ ghép kênh phân chia theo bước sóng (WDM), … Các mạng truyền tải cũng có thiết bị chuyển mạch, thường được biết đến như là các bộ nối chéo, được sử dụng để thiết lập các đường kênh riêng cố định hoặc bán cố định. 12 Hình 1.5: Nhiều miền quản trị khác nhau cùng sử dụng một nhà cung cấp mạng truyền tải Như vậy, có thể thấy rằng nhà cung cấp mạng truyền tải có miền riêng để đón nhận các yêu cầu lưu lượng qua thiết bị nút hay các liên kết truyền tải. Một lưu ý quan trọng ở đây là nhiều nhà cung cấp dịch vụ Internet (ISP) khác nhau có thể cùng sử dụng một nhà cung cấp mạng truyền tải như trên Hình 1.5, hay ngược lại, một ISP có thể sử dụng nhiều nhà cung cấp mạng truyền tải như chỉ ra trên Hình 1.6. Hình 1.6: Một miền quản trị sử dụng nhiều nhà cung cấp mạng truyền tải 13 Ngoài ra, nhà cung cấp mạng truyền tải có thể đáp ứng nhiều yêu cầu khác nhau của khách hàng như mạng Internet, mạng điện thoại, hay mạng khách hàng kênh thuê riêng như chỉ ra trên Hình 1.7. Hình 1.7: Nhiều mạng dịch vụ trên cùng một mạng truyền tải Bài toán thiết kế mạng là trách nhiệm của nhà cung cấp, dù đó là nhà cung cấp dịch vụ Internet, nhà cung cấp dịch vụ điện thoại, nhà cung cấp mạng kênh thuê riêng, hay nhà cung cấp mạng truyền tải. Để đơn giản, chúng ta sẽ sử dụng một thuật ngữ chung là nhà cung cấp mạng thay cho tất cả các nhà cung cấp nói trên. Sự tổ hợp của rất nhiều loại mạng khác nhau dẫn đến một môi trường mạng đa lớp mà ở đó mỗi lớp có các định nghĩa riêng của nó về lưu lượng, dung lượng liên kết và các chức năng thực hiện của thiết bị ở nút mạng. Trong phần tiếp theo chúng ta sẽ đề cập chi tiết hơn về những khía cạnh này. 1.3 Khái niệm về lưu lượng và nhu cầu lưu lượng Một nhà cung cấp mạng phải kiểm soát được việc thiết kế và quản lý mạng trong miền quản trị của mình, và để làm được điều đó, vấn đề quan trọng đối với mỗi nhà cung cấp là phải xác định được nhu cầu lưu lượng trong mạng. Xem xét tất cả các nút trong mạng, chúng ta phải xác định được khối lượng lưu lượng giữa hai nút bất kì hình thành nên ma trận lưu lượng. Ở đây sẽ sử dụng các thuật ngữ rút gọn 14 là ma trận lưu lượng (traffic matrix) và ma trận nhu cầu (demand matrix) để thay cho các thuật ngữ đầy đủ là ma trận khối lượng lưu lượng (traffic volume matrix) và ma trận khối lượng nhu cầu (demand volume matrix). Để thuận tiện cho việc thảo luận, ta xem xét một mạng đơn liên kết mà ở đó mỗi điểm kết thúc đều có lưu lượng. Khái niệm về lưu lượng sẽ được xem xét cho từng trường hợp: Internet, mạng điện thoại và mạng truyền tải. 1.3.1 Lưu lượng trong mạng Internet Khi một khách hàng sử dụng các ứng dụng chẳng hạn như thư điện tử, các bản tin phát đi được chia thành các gói dữ liệu nhỏ hơn để truyền tải qua mạng Internet. Phần lớn các ứng dụng trên mạng Internet sử dụng chồng giao thức truyền thông TCP/IP. Máy tính kết cuối tại đầu phát chịu trách nhiệm chia nhỏ các bản tin ứng dụng thành các gói dữ liệu nhỏ hơn sau đó truyền chúng đi. Tại đầu thu, một kết cuối khác sắp xếp các gói tin nhận được theo thứ tự trước khi chuyển cho ứng dụng. Trong quá trình xử lý, hai máy tính kết cuối cần được thông báo cho nhau nếu một gói dữ liệu bị mất ở đâu đó, và chúng phải phối hợp với nhau để truyền lại gói dữ liệu bị mất nhằm đảm bảo cho nội dung bản tin được chuyển chính xác tới ứng dụng. Công việc của mạng là định tuyến các gói dữ liệu từ một kết cuối này đến một kết cuối khác. Các gói dữ liệu truyền trên mạng thường được biết đến như là các gói tin IP (IP datagrams). Có nhiều nguyên nhân làm cho một gói tin IP không thể truyền đến đích. Ví dụ, lỗi đường truyền vật lý có thể thay đổi nội dung gói dữ liệu và làm cho nó trở thành vô nghĩa, hoặc khi có tắc nghẽn, bộ định tuyến chuyển tiếp không đủ không gian bộ đệm tại thời điểm gói dữ liệu đến. Khác với trường hợp tắc nghẽn giao thông, khi mọi người có thể xếp hàng và đi qua sau một thời gian trễ nào đó, trong mạng Internet việc xếp hàng này chỉ có ý nghĩa khi dung lượng bộ đệm vẫn còn đáp ứng được các gói tin đến. 15 Nguyên lý cơ bản của chồng giao thức TCP/IP dựa trên vấn đề định tuyến. Công việc của một bộ định tuyến là chuyển tiếp các gói dữ liệu đến đích mà không quan tâm đến việc bộ đệm tại bộ định tuyến mà nó chuyển gói tin đến có còn chỗ trống hay không. Điều này có thể chấp nhận được vì quy tắc của giao thức cho phép các máy tính kết cuối phát lại bất cứ gói dữ liệu nào bị mất. Khi giao thức cho phép tốc độ điều chỉnh được để ứng phó với tắc nghẽn, bất kỳ gói dữ liệu đang chuyển tiếp nào cũng có thể bị loại bỏ. Việc tắc nghẽn lưu lượng có thể xảy ra trong một mạng (hoặc trong các phần của mạng), vấn đề trễ có thể xảy ra, và các gói dữ liệu cũng có thể bị loại bỏ. Vì vậy, công việc của người thiết kế mạng là phải thiết kế một mạng sao cho giữ được độ trễ ở mức độ nhỏ nhất có thể chấp nhận, và đảm bảo việc mất gói dữ liệu ở các bộ định tuyến là tối thiểu. Trong thực tế thì việc tắc nghẽn là không tránh khỏi vì lưu lượng có thể không dự báo trước được. Tuy nhiên, có thể thiết kế một mạng sao cho việc tắc nghẽn xảy ra không thường xuyên. Các đường truyền trên mạng cần phải có đủ băng thông để hạn chế tắc nghẽn và giảm thiểu thời gian trễ. Ngoài ra, các bộ định tuyến cần có bộ đệm đủ lớn để đối phó với sự bùng nổ lưu lượng, đặc biệt là lưu lượng thời gian thực nhằm tối thiểu hóa số lượng các gói tin bị mất. Nhìn tổng thể thì vấn đề trở nên phức tạp hơn. Để minh họa điều này cần xem xét các khái niệm lưu lượng và nhu cầu lưu lượng. Trước tiên, ta không biết trước được khi nào thì một người sử dụng sẽ gửi đi một yêu cầu sử dụng trang web từ một địa chỉ nào đó hay một bức thư điện tử (email). Tiếp theo, từ quan điểm mạng, ta phải chấp nhận một thực tế là các yêu cầu hay nhu cầu lưu lượng đến một cách hoàn toàn ngẫu nhiên, và khi số lượng người sử dụng càng lớn thì tính ngẫu nhiên càng trở nên phức tạp. Vì vậy, cách tiếp cận hợp lí ở đây là sử dụng các phương pháp thống kê và xem xét các tính chất ngẫu nhiên trên mạng thông qua các mô hình phân bố thống kê. 16 1.3.2 Lưu lượng trong mạng điện thoại Tương tự như Internet, mạng điện thoại cũng phải đối diện với vấn đề những đối tượng đến ngẫu nhiên. Trong trường hợp này thì đối tượng khảo sát là cuộc gọi. Rõ ràng ta không thể biết khi nào một người sử dụng muốn thực hiện một cuộc gọi và gọi đi đâu. Tương tự như việc khảo sát tốc độ đến trung bình của các gói tin trong mạng Internet, ở đây ta cũng có thể tiến hành đo tốc độ đến trung bình của các cuộc gọi để xác định khối lượng nhu cầu. Song có một số điểm khác cần lưu ý đối với việc nghiên cứu lưu lượng mạng điên thoại. Điều quan trọng đầu tiên cần lưu ý đối với mạng điện thoại là khi một cuộc gọi được kết nối qua mạng thì sẽ có một kênh thoại (ví dụ, tốc độ 64 Kb/s) được cung cấp dành riêng cho cuộc gọi này cho đến khi việc đàm thoại kết thúc. Như vậy, các kênh thoại được duy trì trong suốt thời gian đàm thoại và không được giải phóng để cho cuộc gọi khác. Từ đây có thể thấy rõ những điểm khác của hình thức chuyển mạch kênh so với chuyển mạch gói. Trong chuyển mạch kênh, nếu một liên kết mạng không còn đủ dung lượng thì nhu cầu cuộc gọi đến sẽ bị khoá (từ chối) và người dùng cần phải quay số lại. Không có khái niệm xếp hàng và lưu trễ khi thiết lập cuộc gọi. Trong chuyển mạch gói, các gói dữ liệu từ những ứng dụng khác nhau (như web, thư điện tử) được trộn lẫn trên đường truyền và mọi gói dữ liệu đều được phép đi vào mạng. Tuy nhiên, độ trễ có thể xảy ra đối với các gói dữ liệu trên mạng nếu như một liên kết nào đó trong tuyến truyền dẫn không đủ dung lượng để xử lý tất cả các gói dữ liệu cùng có nhu cầu sử dụng liên kết đó tại một thời điểm. Đôi khi một bộ định tuyến cũng có thể loại bỏ gói dữ liệu nếu như nó không còn đủ dung lượng bộ đệm để xử lý các gói đến trễ. 1.3.3 Nhu cầu lưu lượng trong mạng truyền tải Ta đã xem xét nhu cầu lưu lượng từ góc độ tính chất ngẫu nhiên của lưu lượng cuộc gọi thoại và các gói dữ liệu. Ngoài ra, còn có một nhóm nhu cầu lưu lượng khác có thể xuất hiện trên mạng viễn thông. Đó là khi một vài nhóm khách 17 hàng muốn thuê các kênh hay dung lượng đường truyền để phục vụ cho mạng riêng của họ. Nhu cầu lưu lượng trong trường hợp này có thể xem xét dựa trên quan điểm kiến trúc phân cấp tài nguyên mạng. Có thể thấy rằng các dịch vụ chuyển mạch như điện thoại chỉ làm phát sinh yêu cầu lưu lượng trong một thời gian ngắn. Trong khi đó các nhà cung cấp mạng truyền tải thường làm việc với hệ thống truyền dẫn dung lượng cao để đáp ứng nhu cầu truyền tải nhiều loại hình lưu lượng khác nhau. Vì vậy, cần phải phân biệt một cách rõ ràng hai khái niệm mạng lưu lượng và mạng truyền tải. Mạng lưu lượng (traffic network) là mạng mà trong đó nhu cầu lưu lượng mang tính chất ngẫu nhiên không phụ thuộc vào tốc độ dữ liệu của dịch vụ (truyền gói, thoại 64 Kb/s, …) và có khả năng chuyển mạch/định tuyến để xử lý các yêu cầu phục vụ trong thời gian ngắn. Mạng truyền tải (transport network) cung cấp các dịch vụ tốc độ dữ liệu cao trên cơ sở thiết lập các đường truyền cố định hay bán cố định, và thường là theo chu kỳ có thời hạn dài. 1.3.4 Đơn vị đo dung lượng và nhu cầu lưu lượng Sau khi xem xét những khái niệm lưu lượng và nhu cầu lưu lượng trong các mạng khác nhau, phần này giới thiệu về những khái niệm liên quan đến đơn vị đo dung lượng và nhu cầu lưu lượng. Hai thuật ngữ được sử dụng ở đây là: đơn vị khối lượng nhu cầu (DVU – Demand Volume Unit) và đơn vị dung lượng liên kết (LCU – Link Capacity Unit). Ví dụ, DVU có thể được tính theo pps, Erl, hoặc tốc độ dữ liệu điều chế tùy thuộc vào mạng thiết kế. LCU là đơn vị dung lượng của liên kết, có dạng khác nhau phụ thuộc vào lớp của mạng truyền tải. Ví dụ, nó có thể là E1 hay STM-1, … phụ thuộc vào lớp mạng mà chúng ta thiết kế và giá trị dung lượng liên kết có thể áp dụng được. Bây giờ, nếu xem xét bản chất phân cấp nguồn tài nguyên giữa các mạng lưu lượng và truyền tải, chúng ta có thể thấy rằng nhu cầu lưu lượng tính theo DVU 18 được chuyển thành LCU thông qua việc thiết kế mạng lưu lượng, hay ngược lại, LCU chuyển thành DVU trong trường hợp mạng truyền tải. Ưu điểm của việc sử dụng các thuật ngữ mang tính tổng quát nói trên là trong nhiều trường hợp ta sẽ thấy việc biểu diễn toán học các mô hình thiết kế là hoàn toàn tương tự như nhau từ một kiểu mạng này sang kiểu mạng khác. Điểm khác ở đây chỉ là dùng đơn vị nào (DVU hay LCU) cho phù hợp. 1.4 Khái niệm về định tuyến và luồng Khi có lưu lượng từ một điểm này đến một điểm khác trong mạng, chúng ta có thể nghĩ đến khả năng thiết lập một liên kết trực tiếp với độ dài mang tính kinh tế và đảm bảo khả khi về truyền tải lưu lượng. Trong mạng truyền thông, thuật ngữ định tuyến (routing) có thể được sử dụng theo hai cách khác nhau: - Chỉ điều xảy ra khi chuyển tiếp một gói dữ liệu hay cuộc gọi cụ thể nào đó. - Chỉ trường hợp, khi một khối lượng nhất định của lưu lượng (cuộc gọi hay gói) có thể được chuyển tiếp theo một con đường xác định nào đó. Điều quan trọng cần lưu ý là trong luận văn này khái niệm tuyến được hiểu theo cách thứ hai, nghĩa là để chỉ lưu lượng sẽ được chuyển tiếp qua một con đường cụ thể như thế nào. Điều này là dễ hiểu vì trong bài toán thiết kế mạng thì việc một gói tin hay cuộc gọi cụ thể nào đó được chuyển tiếp ra sao không có ý nghĩa quan trọng lắm. Chúng ta sẽ sử dụng khái niệm danh sách đường ứng cử (candidate path list) để chỉ những tuyến đường có thể được sử dụng để truyền tải khối lượng nhu cầu lưu lượng giữa hai điểm. Nếu một đường (path) nào đó được chọn như là một đường đi phù hợp với yêu cầu thiết kế mạng, thì ta sẽ chỉ định nó như là một tuyến (route). Một vấn đề khác cần quan tâm là có bao nhiêu trong tổng số nhu cầu lưu lượng giữa hai điểm được chuyển tiếp trên tuyến này. Phần lưu lượng kết hợp với một tuyến thường được xem như là luồng (flow). 19 Thuật ngữ định tuyến (routing) cũng có thể được sử dụng trong một trường hợp khác nữa. Nó xuất phát từ các mạng truyền tải chứ không phải là mạng lưu lượng. Trong mạng truyền tải, chúng ta thường được yêu cầu phải chuyển tiếp một khối lượng nhu cầu lưu lượng trên một đường vật lí nào đó theo hình thức cố định hoặc bán cố định. Việc định tuyến này thường được biến đến như là định tuyến mạch (circuit routing), để tránh nhầm lẫn với định tuyến gói tin hay cuộc gọi. Định tuyến mạch cũng được xem như là định tuyến mạng truyền tải. Hình thức định tuyến này đặc biệt quan trọng khi chúng ta thảo luận về các mô hình phục vụ cho việc định tuyến và thiết kế mạng truyền tải, và thường coi đó như là bài toán định luồng (flow allocation). 1.5 Thiết kế mạng với kiến trúc đa lớp Ở trên đã xem xét các khái niệm về lưu lượng/nhu cầu và phân biệt chúng khác nhau như thế nào đối với các mạng lưu lượng và truyền tải. Ngoài ra, chúng ta cũng đã rõ vấn đề định tuyến có thể ảnh hưởng tới bài toán thiết kế mạng như thế nào. Với quan điểm rằng các mạng lưu lượng và truyền tải là khác nhau với những tính chất khác nhau, trong phần này sẽ đề cập đến khía cạnh kiến trúc mạng và mối quan hệ phức tạp giữa các phần tử khác nhau trong mạng dưới góc độ phân lớp. Kiến trúc của các mạng truyền thông có thể khá phức tạp, điều này không chỉ là do số lượng lớn các nút hình thành nên mạng, mà còn do quan điểm phân biệt mạng lưu lượng và mạng truyền tải đã giới thiệu ở trên. Có thể nói một cách đơn giản rằng một mạng (hay lớp) này chạy trên một mạng (hay lớp) khác. Mạng lưu lượng cần có một mạng truyền tải để kết nối các liên kết cần thiết cho mạng lưu lượng. Tiếp đến, trong mạng truyền tải cũng có thể có nhiều lớp ứng với các tốc độ dữ liệu khác nhau. Trên quan điểm dịch vụ, người sử dụng mạng lưu lượng không nhìn thấy sự phụ thuộc vào mạng truyền tải. Kiến trúc mạng đa lớp và mối liên quan giữa các lớp có thể được minh họa thông qua một ví dụ đơn giản như sau. Xét một môi trường mạng IP có 4 nút ở bên 20 trong một miền quản trị. Với mạng này, chúng ta có 4 bộ định tuyến được kết nối như trên Hình 1.8 (phần trên). Hình 1.8: Mạng lưu lượng và mạng truyền tải Các liên kết (hay trung kế) có khả năng truyền lưu lượng với nhiều loại dung lượng liên kết khác nhau như là E1, STM-1, … Chú ý rằng các liên kết trong mạng lưu lượng (trong trường hợp này là mạng IP) hoàn toàn chỉ mang tính logic. Bây giờ chúng ta cần sự trợ giúp của một mạng truyền tải để định tuyến các liên kết logic này (Hình 1.8, phần dưới). Ví dụ, đơn vị dung lượng liên kết f của liên kết logic giữa nút 1 và nút 3 trong mạng IP được kết nối bằng cách sử dụng tuyến 1-