PHÂN TÍCH ĐÁP ỨNG ĐỘNG LỰC HỌC NGẪU NHIÊN CỦA KẾT CẤU NHÀ CAO TẦNG CHỊU TẢI TRỌNG GIÓ
Trong giai đoạn với sự phát triển nhanh chóng của lưu lượng dữ liệu trên mạng, tốc độ xử lý điện tử có thể không còn phù hợp trong tương lai nữa, đồng thời dữ liệu quang thường bị chậm lại do xử lý điện tử tại các node, do đó việc tìm kiếm một phương pháp chuyển tải các gói IP trực tiếp trên lớp quang mà không cần qua chuyển đổi O/E/O cho mạng thông tin thế hệ sau (NGN) là một tất yếu. Nhằm để xây dựng một mạng toàn quang tại đó dữ liệu được duy trì trong miền quang ở tất cả các node trung gian, cần phải thiết kế các giao thức mới dành cho các hệ thống chuyển mạch quang. Một trong các vấn đề cần thiết là làm thế nào để hỗ trợ việc cung cấp tài nguyên nhanh chóng, truyền dẫn đồng bộ (của các gói kích thước biến đổi như các gói IP) cũng như hỗ trợ mức độ cao việc chia sẻ tài nguyên theo thống kê để xử lý hiệu quả lưu lượng có tính bùng nổ mà không cần có đệm ở lớp WDM (do chưa có các bộ nhớ truy cập ngẫu nhiên RAM). Do đó các phương pháp chuyển tải toàn quang cần phải tránh đệm quang càng nhiều càng tốt.
Một vấn đề khác là làm thế nào hỗ trợ chất lượng dịch vụ (QoS) trong mạng Internet quang thế hệ sau. Mạng IP ban đầu cung cấp các các dịch vụ best-effort, tuy nhiên hiện nay các ứng dụng thời gian thực (ví dụ điện thoại và hội nghị truyền hình qua Internet) yêu cầu QoS cao hơn các ứng dụng không phải thời gian thực (như Email hay trình duyệt Web thông thường) và do vậy vấn đề đặt ra đối với lớp WDM là làm thế nào hỗ trợ QoS cho Internet quang. Một số công nghệ khác nhau đang được phát triển, như định tuyến bước sóng (chuyển mạch kênh quang OCS), chuyển mạch gói quang OPS và chuyển mạch chùm quang OBS. Các mạng quang định tuyến bước sóng đã được triển khai và đạt được một số hiệu quả nhất định tuy nhiên các mạng quang định tuyến bước sóng lại lại sử dụng chuyển mạch kênh có thể không phải là công nghệ thích hợp nhất cho các ứng dụng khác nhau sử dụng Internet quang. Kỹ thuật chuyển mạch gói quang là một giải pháp công nghệ khác và có lẽ là tối ưu hơn cho các ứng dụng mới. Tuy nhiên trong điều kiện một số công nghệ hiện đại như bộ đệm quang, logic quang vẫn chưa thực hiện được thì chuyển mạch gói quang vẫn chưa thể áp dụng vào thực tế. Chuyển mạch chùm quang là công nghệ trung gian giữa chuyển mạch kênh quang và chuyển mạch gói quang đáp ứng được yêu cầu vận chuyển một lượng lớn dữ liệu qua mạng với tốc độ cao và cung cấp các tính năng mới trong giai đoạn tới.
Các vấn đề cần nghiên cứu trong OBS là các giao thức dự trữ và giải phóng tài nguyên, phương pháp thiết lập burst, các thuật toán lập lịch trên các liên kết đầu ra của mạng OBS. Nội dung đồ án này trình bày tổng quan về mạng OBS trong đó đi sâu tìm hiểu và mô phỏng các thuật toán lập lịch kênh mục đích để tìm ra được thuật toán tối ưu nhất cho lượng dữ liệu truyền qua mạng cao nhất để nâng cao chất lượng của mạng OBS.
Nội dung luận văn gồm 3 chương:
- Chương 1: Tổng quan về mạng chuyển mạch chùm quang OBS.
- Chương 2: Một số thuật toán lập lịch kênh trên mạng OBS
- Chương 3: Cài đặt mô phỏng và phân tích kết quả
Phương pháp nghiên cứu của đồ án là mô phỏng các thuật toán lập lịch kênhtrên các liên kết đầu ra của mạng OBS, so sánh kết quả của các thuật toán để từ đó tìm ra thuật toán tối ưu.
Trong quá trình làm luận văn mặc dù đã cố gắng nhiều nhưng không thể trách khói những sai sót, mong các thầy cô thông cảm và hướng dẫn cho em. Để hoàn thành luận văn này em đã được sự hướng dẫn tận tình của PGS.TS Lê Văn Sơn, em xin gởi lời cảm ơn chân thành đến thầy.
Đà Nẵng tháng 6/2017
Học viên thực hiện
Nguyễn Quốc Vinh
TỔNG QUAN VỀ MẠNG CHUYỂN MẠCH CHÙM QUANG OBS
. TỔNG QUAN VỀ MẠNG THÔNG TIN QUANG
Nhu cầu thông tin của con người ngày càng phát triển mạnh mẽ với nhiều loại hình dịch vụ đa dạng. Điều này đặt ra những thách thức đối với hệ thống truyền thông vốn có, vốn được xây dựng chủ yếu phục vụ cho nhu cầu thoại và truyền thông tin không đòi hỏi tốc độ cao.
Một yêu cầu đặt ra là phải xây dựng một hệ thống có khả năng cung cấp băng thông lớn, truyền được một lượng lớn dữ liệu với tốc độ cao. Sợi quang với những tính chất ưu việt cùng việc ứng dụng ghép kênh phân chia theo bước sóng (WDM : Wavelength Division Multiplexing) là một giải pháp hứa hẹn cho mạng Internet thế hệ mới [8].
Một mạng toàn quang là mục tiêu hướng tới nhưng trong tương lai gần chúng ta có thể xây dựng một mạng quang trong suốt ít nhất đối với dữ liệu trong đó dữ liệu được chuyển hoàn toàn trong miền quang còn gói tin điều khiển được chuyển trong miền điện. Các công nghệ chuyển mạch quang được đề xuất như chuyển mạch kênh quang, chuyển mạch gói quang và chuyển mạch chùm quang, mỗi công nghệ có các ưu và nhược điểm riêng trong đó chuyển mạch chùm quang dung hòa được những ưu và nhược điểm của hai loại chuyển mạch kia và là công nghệ hứa hẹn trong tương lai. Các thế hệ mạng quang đã được đề xuất gồm:
Thế hệ đầu tiên là kiến trúc mạng point to point WDM (WDM điểm- điểm). Một mạng như vậy gồm nhiều liên kết điểm điểm, ở đó tất cả các lưu lượng đi vào một node từ một sợi quang được chuyển đổi từ quang sang điện và tất cả các lưu lượng đi ra một node được chuyển đổi từ điện sang quang trước khi đưa vào sợi quang. Việc tách ghép luồng quang bằng cách chuyển đổi quang điện tại mỗi node có thể làm tăng độ trễ và tăng chi phí mạng, do đó, để giảm được độ trễ và giảm đi chi phí mạng ta nên xây dựng một mạng toàn quang nghĩa là việc chuyển tiếp gói hoàn toàn trong miền quang.
Kiến trúc mạng quang thứ hai dựa trên các bộ xen rớt ghép kênh theo bước sóng Wavelength Add-Drop Multiplexer (WADM), trong đó việc tách ghép lưu lượng được thực hiện tại nơi có WADM . WADM có thể tách ra một bước sóng được chọn và cho phép các bước sóng đi qua. Nói chung, lưu lượng đi qua một node thì nhiều hơn lưu lượng cần rẽ tại một node. Do đó bằng việc sử dụng WADM chúng ta có thể giảm được chi phí toàn mạng bằng cách chỉ tách những bước sóng mà đích đến của nó là tại node này còn tất cả các bước sóng khác đi đến node tiếp theo.
Kiến trúc mạng quang thế hệ thứ ba dựa trên việc kết nối các thiết bị toàn quang. Những thiết bị này thường được phân loại thành passive star, passive router và active switch. Tín hiệu được đưa vào một bước sóng tại ngõ vào sao đó công suất tín hiệu này sẽ được chia đều cho tất cả các ngõ ra (sử dụng cùng bước sóng). Một passive router có thể định tuyến một cách riêng rẽ một trong số nhiều bước sóng ở sợi quang ngõ vào đến một bước sóng giống như vậy ở ngõ ra. Active switch cho phép sử dụng lại bước sóng và có thể hỗ trợ những kết nối liên tục qua nó. Passive star được sử dụng để xây dựng một mạng WDM nôi bộ. Trong khi active switch dùng để xây dựng mạng diện rộng định tuyến bước sóng, Passive router dùng như là một thiết bị mux và demux.
. CÁC CÔNG NGHỆ CHUYỂN MẠCH QUANG
Chuyển mạch kênh quang hay còn gọi là giao thức định tuyến bước sóng quang Wavelength Routed Networking (WRN) trong đó một đường dẫn quang được thiết lập giữa đích và nguồn trước khi truyền dữ liệu. Trong khi truyền dữ liệu không cần node trung gian thực hiện những công việc phức tạp như xử lý header hay đệm tải trọng. Một đường dẫn quang (light path) được sử dụng để cung cấp một kết nối trong mạng WDM định tuyến bước sóng và có thể trải dài trên nhiều liên kết sợi quang. Các bộ chuyển đổi bước sóng tạo ra các bước sóng khác nhau trên các liên kết quang. Trong mạng WRN băng thông được cấp phát tĩnh hay cố định nên không thể thích ứng với lưu lượng dồn dập và thay đổi cao của Internet một cách hiệu quả. Với một số bước sóng giới hạn cho trước chỉ một số lượng đường dẫn quang hạn chế được thiết lập tại cùng một thời điểm. Nếu lưu lượng thay đổi động, lưu lựong truyền qua các đường dẫn tĩnh sẽ làm cho sự tận dụng băng thông kém hiệu quả. Để có thể đáp ứng được yêu cầu về băng thông lớn trong mạng đô thị và mạng diện rộng, những phương thức truyền tải phải hỗ trợ việc dự trữ tài nguyên và có khả năng truyền được lưu lượng đột biến. Nhưng nếu ta cố gắng thiết lập các đường dẫn quang một cách thức động, thông tin trạng thái của mạng sẽ thay đổi liên tục gây khó khăn trong việc cập nhật trạng thái của mạng. Hơn nữa, dự trữ trong WRN là dự trữ hai chiều trong đó khi có nhu cầu nguồn gửi yêu cầu thiết lập đường dẫn quang và nhận về một xác nhận từ đích tương ứng là kết nối đã được thiết lập cho dù kết nối này có dung lượng bao nhiêu, do vậy việc sử dụng băng thông không hiệu quả về mặt kinh tế.
Chuyển mạch gói quang có thể cung cấp băng thông động nên thích hợp với lưu lượng thay đổi của internet vì nó cho phép chia sẻ thống kê các bước sóng thuộc về các đích và nguồn khác nhau. Trong mạng chuyển mạch gói OPS phần header của mỗi gói được tách ra và xử lý trong miền điện còn dữ liệu phải đệm trong miền quang để chờ header được xử lý xong mới được truyền đi. Vì vậy yêu cầu phải có bộ đệm quang nhưng đây là công nghệ vẫn chưa thực hiện được. Hơn nữa việc xử lý header trong miền quang không thể thực hiện được trong tương lai gần do chưa có logic quang hoàn toàn nên mặc dù OPS là một công nghệ có nhiều tính năng vượt trội như tốc độ chuyển mạch cao, thích hợp với bản chất của lưu lượng internet nhưng không thực tế trong tương lai gần.
Chuyển mạch chùm quang cũng dựa trên ý tưởng tách gói tin điều khiển như OPS nhưng giữa gói tin điều khiển (BHP) và burst dữ liệu có sự gắn kết chặt chẽ về thời gian hơn trong OPS. Các gói tin được tích hợp thành các burst có chiều dài khác nhau và được gửi đi sau gói tin điều khiển một thời gian offset. Thời gian offset được tính toán sao cho gói tin điều khiển đựợc xử lý xong và hoàn thành việc dự trữ tài nguyên tại các node trung gian. Vì vậy công nghệ bộ đệm quang không bắt buộc. Việc xử lý một BHP cho nhiều gói tin cùng một lúc làm giảm thời gian xử lý header cho từng gói trong OPS.
Khác với OCS, OBS sử dụng phương thức dự trữ tài nguyên một chiều truyền dẫn tức thời, nghĩa là burst dữ liệu theo sau một gói tin điều khiển mà không cần chờ chấp thuận của node kế tiếp trên đường đi đến đích nên chiếm dụng tài nguyên hiệu quả hơn OCS. Nó cũng tỏ ra thích hợp với lưu lượng thay đổi đột biến của internet và theo các kết quả nghiên cứu cho thấy lưu lượng của internet nhất là các trang web có bản chất burst [2].
Do có sự thay đổi về độ dài burst mà mạng OBS được coi là ở giữa mạng OPS và WRN. Khi các burst có chiều dài rất nhỏ, gần với các gói thông tin quang thì mạng OBS được coi là mạng OPS nhưng khi các burst có chiều dài khá lớn thì nó có thể coi là mạng WRN. Hơn nữa chuyển mạch chùm quang được thiết kế để khắc phục các nhược điểm của OCS và OPS. Nếu OCS chỉ thích hợp với các dịch vụ tốc độ cố định như thoại hay truyền hình và chiếm dụng tài nguyên lớn, OPS thì tốc độ cao nhưng đòi hỏi các công nghệ chưa thưc hiện được như bộ đệm quang hay logic quang thì OBS lại đáp ứng được yêu cầu tốc độ thay đổi của các dịch vụ truyền số liệu và do burst dữ liệu được truyền đi sau các gói tin điều khiển một thời gian offset nên không bắt buộc có bộ đệm quang. Vì vậy OBS được xem như công nghệ chuyển mạch quang hứa hẹn nhất trong tương lai cho một lượng lớn dữ liệu với tốc độ cao.
Khái niệm chuyển mạch chùm đã được đề xuất vào năm 1980. Tuy nhiên, kỹ thuật này không thành công trong mạng chuyển mạch điện tử do nhu cầu và tính phức tạp so với kỹ thuật chuyển mạch gói. Trong mạng quang có sự khác biệt lớn giữa khả năng truyền dẫn quang và khả năng xử lý điện tử; thêm vào đó khả năng sử dụng các bộ nhớ truy cập ngẫu nhiên trong miền quang là không khả dụng, vì vậy không thể giữ được dữ liệu đợi xử lý trong miền quang. Mạng chuyển mạch chùm quang được đề xuất vào cuối năm 1990 và nó trở thành một công nghệ hứa hẹn có thể tận dụng được những ưu điểm của mạng chuyển mạch kênh quang và mạng chuyển mạch gói quang để tránh được những bất lợi về kỹ thuật trong thời gian này.
Mạng chuyển mạch chùm quang được xem như là một công nghệ hứa hẹn cho mạng Internet toàn quang thế hệ kế tiếp. Nó có nhiều chức năng riêng và nhiều ưu điểm hơn so với các kỹ thuật chuyển mạch khác. Mạng chuyển mạch chùm quang là một giải pháp cho phép truyền tải lưu lượng trực tiếp qua mạng WDM mà không cần bộ đệm quang. Mạng chuyển mạch chùm quang sử dụng các sơ đồ định trước một hướng với quá trình truyền tức thời, chùm dữ liệu truyền đi sau gói điều khiển tương ứng mà không đợi phản hồi (báo nhận) từ nút đích.
Thực chất, mạng chuyển mạch chùm quang xem xét lớp quang đơn thuần như một phương tiện truyền thông trong suốt cho các ứng dụng. Tuy nhiên cho đến hiện nay chưa có định nghĩa chung nào cho chuyển mạch chùm quang.
Một số đặc trưng chung của mạng chuyển mạch chùm quang như sau:
– Tách biệt giữa kênh truyền gói điều khiển BCP (Burst Control Packet) và kênh truyền chùm dữ liệu DB (Data Burst): gói điều khiển được truyền trên một kênh riêng biệt.
– Sự dành riêng một chiều: tài nguyên được cấp phát theo kiêu dành riêng một chiều, nghĩa là nút nguồn không cần đợi thông tin phản hồi từ nút đích trước khi nó bắt đầu truyền chùm.
– Độ dài chùm thay đổi được: kích thước của chùm có thể thay đổi được theo yêu cầu.
– Không cần bộ đệm quang: nút trung gian trong mạng quang không yêu cầu phải có bộ đệm quang. Các chùm đi qua các nút trung gian mà không chịu bất kì sự trễ nào.
Kiến trúc của mạng OBS bao gồm các nút chuyển mạch chùm quang (nút OBS) kết nối với nhau thông qua các sợi cáp quang. Mỗi sợi cáp quang có khả năng hỗ trợ nhiều bước sóng khác nhau, các nút OBS có thể là các nút biên hoặc các nút lõi. Kiến trúc này được thể hiện như trong Hình 1.1.
Hình 1.1. Kiến trúc của mạng chuyển mạch chùm quang
Nút biên được xem như là giao diện giữa miền điện tử và miền quang. Nút biên có thể là nút biên vào hoặc nút biên ra. Nút biên vào thực hiện tập hợp các gói điện tử (chẳng hạn các gói IP) có cùng đích đến thành một đơn vị truyền dẫn lớn gọi là chùm quang (burst), nút biên có thể tập hợp các gói tin đến từ nhiều nguồn khác nhau miến sao có cùng đích đến, sau đó thực hiện định tuyến, ấn định bước sóng và lập lịch cho chùm trên một kênh dữ liệu ở cổng ra, sau đó được truyền qua mang OBS và cuối cung được tách gói tại nút biên ra. Nút lõi được xem như là nột ma trận chuyển mạch trong đó mỗi đơn vị chuyển mạch có trách nhiệm chuyển tiếp các chùm dữ liệu đến nút khác.
Một nút lõi bao gồm cả hai phần: Quang và điện. Phần quang là các bộ ghép/tách bước sóng (multiplexer/demultiplexer) và ma trận chuyển mạch quang. Phần điện có đơn vị vào/ra, điều khiển định tuyến và lập lịch. Ma trận chuyển mạch quang chuyển mạch các chùm dữ liệu đến từ một cổng vào và một cổng ra tưng ứng với đích đến của chúng.
Khi một nút biên chuyển bị truyền một chùm dữ liệu, nó sẽ gửi một gói điều khiển đi trên một bước sóng dành riêng tới nút lõi. Gói điều khiển thực hiện việc báo hiệu, cấu hình các chuyển mạch tại nút lõi để chuyển chùm từ cổng và giải quyết xung đột nếu xảy ra.
Tập hợp chùm là quá trình tập hợp các gói tin điện tử và đóng gói thành chùm tại nút biên vào của mạng OBS [4]. Tất cả gói đến sẽ được kiểm tra đích đến và được chuyển đến hàng đợi tương ứng. Việc tập hợp chùm được dựa vào một giá trị ngưỡng (có thể là thời gian hoặc độ dài) để quyết định khi nào một chùm được gửi vào trong mạng.
Ngược lại với tập hợp chùm, tách chùm được thực hiện ở nút biên ra, mà ở đó các gói tin sẽ được tách và được chuyển đến đích của chúng [4] . Hình 1.2 mô tả việc tập hợp và tách chùm trong mạng OBS.
Hình 1.2. Tập hợp và tách chùm
Có nhiều kỹ thuật tập hợp chùm đã được đề xuất trong [3, 4], nhưng kỹ thuật tập hợp chùm dựa vào ngưỡng thời gian (timer-based) và dựa trên ngưỡng độ dài chùm (threshold-based) hiện được quan tâm nhất.
Trong phương pháp tập hợp chùm dựa trên ngưỡng thời gian, một chùm được tạo ra và gởi vào trong mạng theo chu kỳ thời gian, đúng bằng thời gian đã được định sẵn vì vậy kích thước chùm dài hay ngắn tùy thuộc vào tần suất gói đến trong ngưỡng thời gian đó. Hình 1.3 thể hiện kỹ thuật tập hợp chùm dựa trên ngưỡng thời gian.
Hình 1.3. Tập hợp burst theo ngưỡng thời gian
Đối với phương pháp tâp hợp chùm dựa trên giá trị ngưỡng độ dài, chùm được xây dựng dựa trên số lượng tối đa gói tn chứa trong mỗi chùm. Vì vậy những chùm được tạo ra có kích thước cố định. Hình 1.4 thể hiện kỹ thuật tập hợp chùm dựa trên độ dài.
Hình 1.4.Tập hợp burst theo ngưỡng kích thước (số gói tối đa)
Để đem lại hiệu quả tốt nhất đối với các phương pháp trên, thì vấn đế chọn ngưỡng phù hợp là rất quan trọng.
Như trong phương pháp dựa trên ngưỡng thời gian, nếu thời gian dài thì kích thước của chùm lớn, nên số lượng chùm lưu thông trong mạng ít. Tuy nhiên khi xảy ra mất chùm vì kích thước lớn nên số lượng gói tin rơi cũng sẽ lớn. Trong trường hợp nếu chọn ngưỡng thời gian ngắn, kích thước chùm sẽ nhỏ, nên lưu lượng chùm lưu thông trong mạng sẽ nhiều và dễ dẫn đến tranh chấp, nhưng khi chùm rơi thì số lượng gói tin rơi lại thấp. Tương tự với phương pháp ngưỡng thời gian, khi chọn ngưỡng trong phương pháp độ dài cũng ảnh hưởng lướn hiệu quả của hệ thống mạng quang.
t
Hình 1.5.Tập hợp burst theo ngưỡng thời gian và ngưỡng độ dài burst
Từ đó, ta có thể thấy rắng hai phương pháp này có ưu nhược điểm khác nhau với lưu lượng tải trong mạng khác nhau. Trong quá trình nghiên cứu người ta thấy rằng lưu lượng mạng luôn không cố định nên việc kết hợp giữa hai phương pháp này có thể mang lại hiệu suất cao hơn. Hình 1.5 mô tả ảnh hưởng của kỹ thuật tập hợp chùm dựa trên ngưỡng thời gian và ngưỡng độ dài chùm đối với chùm sinh ra.
Báo hiệu là một tiến trình đặt trước tài nguyên và cấu hình bộ chuyển mạch tại mỗi nút sao cho phù hợp với yêu cầu của một chùm đến [11]. Tiến trình báo hiệu trong mạng OBS được thực hiện bởi các gói điều khiển và các gói này đươc truyền độc lập với các chùm dữ liệu.
Có nhiều phương thức báo hiệu trong mạng OBS:
- Theo hướng: Đặt trước tài nguyên một chiều, hai chiều hoặc kết hợp cả một chiều và hai chiều.
Đối với sơ đồ báo hiệu một chiều, nút nguồn gửi đi một gói điều khiển yêu cầu mỗi nút trên cùng một tuyến cấp phát tài nguyên cần thiết cho burst dữ liệu và cấu hình chuyển mạch quang tương ứng. Sau đó nguồn sẽ gửi burst dữ liệu đi mà không cần chờ tín hiệu ACK từ nút trung gian hay nút đích trả lời về. Vì không cần tín hiệu ACK nên burst dữ liệu có thể gửi đi sớm hơn và giảm độ trễ truyền dẫn đầu – cuối (end-to-end).
Sơ đồ báo hiệu hai chiều cũng tương tự như báo hiệu một chiều tuy nhiên nút nguồn chờ nhận được tín hiệu ACK phản hồi sau đó mới quyết định có truyền burst đi hay không. Như vậy, nếu việc đặt trước tài nguyên và cấu hình chuyển mạch quang thành công, burst dữ liệu được gửi đi; Ngược lại, nếu bất kỳ nút trung gian nào đó không thể điều tiết được tài nguyên thì tại nút trung gian này sẽ có một thông báo tắc nghẽn được gửi trở lại nguồn để báo rằng việc đặt trước thất bại và nút nguồn sẽ hủy bỏ các liên kết đã đặt trước được thiết lập trước đó trên đường đi tương ứng. Báo hiệu hai chiều tăng độ trễ truyền dẫn đầu – cuối.
Phương pháp báo hiệu kết hợp đưa ra giải pháp cân bằng giữa báo hiệu một chiều và hai chiều, đây là phương pháp dự phòng bộ phận. Trong phương pháp báo hiệu kết hợp, việc đặt trước từ nút nguồn tới các nút trung gian trên tuyến được xác nhận bằng tín hiệu ACK, trong khi việc dành riêng từ nút trung gian tới đích sẽ không được xác nhận. Vị trí của nút được chỉ định làm nút trung gian sẽ quyết định khả năng mất hay độ trễ của burst dữ liệu. Nếu nút trung gian được chọn gần với nguồn thì hoạt động của mạng sẽ giống như việc báo hiệu một chiều, và nếu nút trung gian gần về phía đích thì hoạt động giống như việc báo hiệu hai chiều.
- Theo vị trí: Đặt trước tài nguyên bắt đầu từ nguồn, từ đích hoặc từ nút trung gian.
Đặt trước từ nguồn (source initiated reservation – SIR): Tài nguyên được cấp phát cùng hướng báo hiệu khi gói điều khiển đi từ nguồn về đích. Nếu quá trình đặt trước thành công từ nguồn đến đích, một tín hiệu ACK được gửi ngược từ đích về nguồn chỉ định bước sóng dành riêng mà burst dữ liệu sẽ được truyền đi.
Đặt trước từ đích (destination initiated reservation – DIR): Nguồn gửi một yêu cầu đặt trước tài nguyên đến nút đích, yêu cầu này sẽ lựa chọn các bước sóng phù hợp với thông tin trên mỗi liên kết cùng hướng, Dựa trên sự lựa chọn thông tin, nút đích sẽ chọn một bước sóng phù hợp (nếu như nó tồn tại) tương ứng với khoảng thời gian và gửi yêu cầu dành riêng trở về nút nguồn, yêu cầu dành riêng sẽ được chuyển qua các nút trung gian, dành riêng này sẽ được chọn một bước sóng để giữ cho hết thời gian quy định.
Nguyên nhân chính gây ra tắc nghẽn (hoặc mất dữ liệu) trong SIR vì thiếu tài nguyên rỗi, trong khi đó đối với DIR việc mất dữ liệu vì thông tin hết hạn.
Dành riêng tại nút trung gian (intermediate node initiated reservation- INI): đặc trưng dành riêng tài nguyên của nó giống như DIR từ nguồn đến một vài nút trung gian, và giống như SIR từ nút trung gian đến nút đích.
Nhìn chung, để giảm sự mất dữ liệu tại các nút trong hướng thuận, SIR dựa trên sự dành riêng nhiều hơn một bước sóng cho đến khi tới đích và giải phóng những dành riêng không cần thiết đối với hướng ngược lại. Cách tiếp cận này có thể dẫn đến việc là làm giảm hiệu năng vì đã phong tỏa hết hướng thuận và thiếu hụt ở nguồn. Ngược lại, DIR dựa trên kỹ thuật chỉ lựa chọn những thông tin sẵn sàng của tất cả các nút trung gian và dựa trên những thông tin đó mà lựa chọn bước sóng.
- Khi tài nguyên không sẵn sàng: Đặt trước bền vững hoặc đặt trước không bền vững.
Việc đặt trước tài nguyên tại một nút có thể bị tắc nghẽn tạm thời; kỹ thuật báo hiệu do đó có thể hoặc chờ đợi cho đến khi hết tắc nghẽn (Persistent) hoặc thông báo tắc nghẽn ngay lập tức (Non-persistent). Trong cách tiếp cận bền vững, gói điều khiển chờ cho đến khi tài nguyên rỗi và chọn bước sóng sao cho việc mất dữ liệu nhỏ nhất. Trong trường hợp này, giả định mỗi nút biên và lõi đều có bộ đệm (buffer) dành riêng để “lưu” tạm thời burst đến. Trong cách tiếp cận không bền vững, ràng buộc là độ trễ (thời gian trễ đầu-cuối nhỏ nhất); vì vậy yêu cầu tài nguyên là thất bại nếu không có giải pháp giải quyết tranh chấp phù hợp.
- Theo thời gian: Đặt trước tài nguyên tức thười hoặc sau một khoảng thời gian trễ nhất định.
Hình 1.6. Quá trình đặt trước tức thời và sau một thời gian trễ
Như mô tả ở Hình 1.6, dựa trên khoảng cách giữa gói điều khiển và burst đến, kỹ thuật báo hiệu có thể thực hiện đặt trước tài nguyên tức thời hoặc sau một khoảng thời gian trễ. Trong kỹ thuật đặt trước tức thời, kênh (tài nguyên) sẽ được dành riêng ngay lập tức khi gói điều khiển đến các nút. Ngược lại đối với kỹ thuật đặt trước sau khoảng thời gian trễ, các kênh được đặt chổ dựa trên thời gian thực tế của burst dữ liệu đến tại nút đó.
Để sử dụng kỹ thuật đặt trước sau khoảng thời gian trễ, gói điều khiển phải được gửi đi trước burst dữ liệu một khoảng thời gian offset. Ví dụ của đặt trước tức thời là giao thức JIT (Just-In-Time), trong khi giao thức JET (Just-Enough-Time) dùng kỹ thuật đặt trước sau khoảng thời gian trễ. Nhìn chung đặt trước tức thời đơn giản và có thể thực hiện ngay lập tức nhưng dễ tạo ra tắc nghẽn lớn, ảnh hưởng đến hiệu quả sử dụng băng thông trên toàn mạng. Ngược lại đặt trước sau khoảng thời gian trễ giải quyết được tình trạng trên một cách hiệu quả.
- Giải phóng tài nguyên: Tường minh hoặc ngầm định.
Giải phóng tài nguyên có thể thực hiện bằng hai cách đó là giải phóng ngầm định và giải phóng tường minh. Trong đó kỹ thuật giải phóng tường minh, một gói điều khiển riêng biệt theo sau burst dữ liệu từ nguồn đến đích để giải phóng hoặc kết thúc việc sử dụng tài nguyên đã được đặt trước. Ngược lại kỹ thuật giải phóng ngầm định thì gói điều khiển (BHP: Burst Header Packet) phải mang thêm thông tin như là độ dài khối dữ liệu và độ lệch thời gian giữa gói điều khiển và burst dữ liệu để tại nút đó biết được thời gian để giải phóng tài nguyên dành trước. Đối với hai cách giải phóng tài nguyên đặt trước trên thì giải phóng tài nguyên tường minh phức tạp, chiếm dụng băng thông và làm tăng số lượng gói thông báo ở trong mạng.
- Theo cách tính toán: Tập trung hoặc phân tán.
Trong kỹ thuật báo hiệu tập trung một máy chủ chuyên dụng chịu trách nhiệm thiết lập các thông số như định tuyến, cấp phát bước sóng cho burst dữ liệu đối với tất cả các cặp nút trên mạng. Trong kỹ thuật báo hiệu phân tán, mỗi nút mạng có một bộ lập lịch gán một kênh ra cho mỗi gói tin điều khiển đến theo kiểu phân tán. Kỹ thuật phân tán thích hợp cho những mạng quang lớn và dữ liệu dưới dạng chùm, ngược lại kỹ thuật tập trung chỉ thích hợp những mạng nhỏ có lưu lượng ít.
Trong mạng OBS cũng như các mạng chuyển mạch gói khác, tồn tại khả năng một chùm có thể tranh chấp với một chùm khác tại một nút. Sự tranh chấp có thể xảy ra nếu nhiều chùm đến từ nhiều cổng vào khác nhau được định trước cho cùng một cổng ra tại cùng thời điểm. Điển hình của việc giải quyết tranh chấp trong các mạng chuyển mạch gói điện tử truyền thống được quản lý thông qua bộ đệm. Tuy nhiên tron lĩnh vực quang, việc sử dụng bộ đệm tại các nút đang gặp khó khăn. Để giải quyết tình trạng tranh chấp và việc mất chùm một số phương pháp cơ bản sau có thể sử dụng: Thay đổi thời gian đến của chùm dữ liệu bằng cách sử dụng các đường dây trễ (Fiber Delay Line – FDL), thay đổi bước sóng ra của chùm bằng cách sử dụng bộ chuyển đổi bước sóng hay thay đổi cổng ra của chùm bằng cách định tuyến lệch hướng (DR: Deflection Routing).
Lập lịch chùm trong mạng OBS là vấn đề rất quan trọng [1]. Khi một gói điều khiển đến một nút, dựa trên thông tin của gói điều khiển, một thuật toán lập lịch được gọi ra để gán chùm chưa được lập lịch với một kênh dữ liệu trên kênh ra. Mỗi chùm đến tương ứng một bước sóng λ và việc sắp xếp các chùm đến phải xét đến các kênh phù hợp có cùng bước sóng hoặc phải được chuyển đổi sang kênh bước sóng khác. Do đó, các thuật toán lập lịch cũng phải xem xét đến yếu tố có sử dụng bộ chuyển đổi bước sóng hay không để có thể tiến hành lập lịch cho các chùn đến, với mục đích sắp xếp các chùm lên các kênh có bước sóng phù hợp một cách có hiệu quả nhất.
Có hai loại chuyển đổi bước sóng: Chuyển đổi một phần (limited-range) và chuyển đổi đầy đủ (full). Với loại chuyển đổi bước sóng một phần thì mỗi bước sóng chỉ có thể chuyển đổi sáng một số bước sóng nhất định nào đó; trong khi đối với chuyển đổi đầy đủ thì mỗi chùm đến có thể được chuyển đổi sang bước sóng bất kỳ. Trong trường họp sử dụng bộ chuyển đổi đầy đủ thì các thuật toán không cần xét đến việc bước sóng sẽ phù hợp cho kênh nào.
Các thuật toán lập lịch cho kênh dữ liệu có thể được phân thành 2 loại: lấp đầy khoảng trống và không lấp đầy khoảng trống.
Có hai thuật toán lập lịch không xét đến lấp đầy khoảng trống: FFUC (First Fit Unscheduled Channel) [7] và LAUC (Lastest Available Unused Channel) [7].
Hình 1.7.Minh họa các thuật toán lập lịch không xét đến lấp đầy khoảng trống
Đối với loại thuật toán này, chúng ta cần lưu ý đến 2 tham số: thời điểm đến của chùm so với thời điểm kết thúc của chùm sau cùng nhất (Latest Available Unscheduled Time) trên kênh dữ liệu thứ . Nếu , kênh thứ mới được xem xét cho việc lập lịch chùm đến. Như mô tả ở Hình 1.7 rõ ràng chỉ có kênh và là được xem xét vì thỏa mãn điều kiện và .
Trong cả hai thuật toán lập lịch FFUC và LAUC, các khoảng trống giữa hai chùm trên mỗi kênh dữ liệu chưa được tận dụng để lập lịch cho một chùm mới đến.
Trên cở sở 2 thuật toán không xét đến lấp đầy khoảng trống, 2 thuật toán tương tự có xét đến lấp đầy khoảng trống (Void-Filling) đã được đề nghị: FFUC-VF và LAUC-VF. Đối với loại thuật toán này, bộ lập lịch duy trì thời điểm bắt đầu và kết thúc của các chùm đã lập lịch trên tất cả các kênh.
| Hình 1.8.Minh họa các thuật toán lập lịch có xét đến lấp đầy khoảng trống |
Thuật toán FFUC-VF [7] duy trì thời điểm bắt đầu và kết thúc cho mỗi chùm dữ liệu đã được lập lịch trên mỗi kênh dữ liệu nhằm tận dụng các khoảng trống có thể lập lịch được cho chùm đến. Khi có chùm đến, thuật toán FFUV-VF sẽ chọn khoảng trống đầu tiên phù hợp với chùm đến. Như trong Hình 1.8 kênh D0 được lựa chọn.
Thuật toán LAUC-VF [10] tương tự như thuật toán LAUC, ngoại trừ việc xét đến các khoảng trống có thể được lập lịch bằng các chùm mới đến. Thuật toán LAUC-VF duy trì thời điểm bắt đầu và kết thuc cho mỗi chùm dữ liệu đã được lập lịch trên mỗi kênh dữ liệu. Mục đích của thuật toán này là tận dụng hiệu quả các khoảng trống giữa hai chùm đã được lập lịch. Trong tất cả các khoảng trống có thể lập lịch cho chùm đến, thuật toán LAUC-VF sẽ ưu tiên khoảng trống có thời gian kết thúc của chùm đã lập lịch gần nhất với nhằm tạo điều kiện cho các chùm tới sau đó. Như trong Hình 1.8 dựa vào thời gian đến và thời gian kết thúc của chùm thí tất cả các kênh D0, D1, D2, D3 đều khả dụng để lập lịch cho chùm đến. Nhưng ta thấy kênh D3 có là nhỏ nhất vì vậy kênh D3 sẽ được chọn để lập lịch cho chùm đến.
Ta dễ thấy rằng thuật toán LAUC-VF tận dụng băng thông của bước sóng tốt hơn và tỷ lệ mất chùm thấp hơn thuật toán LAUC. Tuy nhiên, độ phức tạp của thuật toán LAUC-VF lướn hơn so với thuật toán LAUC, đặc biết khi số khoảng trống lớn hơn đáng kể so với số kênh dữ lệu. Độ phức tạp của thuật toán LAUC-VF là , trong đó w là số kênh dữ liệu, N là số khoảng trống trên mỗi bước sóng. Các loại thuật toán trên sẽ được trình bày và phân tích rõ hơn trong chương 2 của luận văn.
Trong chương này, luận văn đã giới thệu được tổng quan về mạng truyền dẫn quang và làm rõ được các ưu điểm của mạng OBS cũng như là các hoạt động bên trong nó. Một trong những vấn đề quan trọng của mạng OBS là vấn đề lập lịch chùm tại các nút, việc lập lịch sao cho hiệu suất sử dụng mạng đạt cao nhất vẫn đang là vấn đề cần được quan tâm. Lập lịch kênh là một trong số các giải pháp đáng được quan tâm hiện nay bở những hiệu quả mà nó mang lại. Trong chương 2 của luận văn sẽ làm rõ hơn các thuật toán lập lịch kênh trên mạng OBS.
MỘT SỐ THUẬT TOÁN LẬP LỊCH KÊNH TRÊN MẠNG OBS
Khi một burst tới một node, nó cần được cấp cho một kênh bước sóng ở ngõ ra, vì vậy tất cả các node trong hệ thống mạng đều phải có bộ wavelength converter. Ngoài ra, nhằm làm giảm thiểu khoảng thời gian trống giữa 2 burst truyền đi trên cùng một kênh bước sóng, người ta dùng thêm bộ sắp xếp các burst tại tất cả các node tham gia trong mạng, bộ đó được gọi là bộ xếp lịch (channel scheduling).
Khi header của burst dữ liệu tới được nút lõi, các thông số về burst dữ liệu sẽ được nhận biết ở nút lõi như chiều dài burst (burst duration), thời gian burst đó tới nút (arrival time)… Dựa vào những thông số này, nút lõi sẽ xác định được kênh bước sóng thích hợp nhất dành cho burst dữ liệu nhờ thuật toán sắp xếp của bộ channel scheduling.
Thuật toán sắp xếp kênh bước sóng cho các kênh dữ liệu được chia làm hai phần chính như sau: có hoặc không có sử dụng void filling (lấp đầy khoảng trống).
2.2. PHÂN LOẠI CÁC THUẬT TOÁN LẬP LỊCH KÊNH
2.2.1. Thuật toán Horizon (without Void filling)
Thuật toán FFUC (First Fit Unschedule Channel) [4,6,9,12] không sử dụng void filling có thể được trình bày cơ bản như sau: Khi một burst dữ liệu đến một nút. Nút đó sẽ so sánh thông số tub và LAUTi , nếu thông số này lớn hơn 0 thì kênh đó sẽ thích hợp để cấp cho burst đó. Trong trường hợp có nhiều hơn 1 kênh thích hợp, thuật toán sẽ chọn kênh có hệ số i thấp nhất.
Hình 2.1. Mô hình thuật toán FFUC không sử dụng void filling
Trong ví dụ trên, ta thấy khi burst dữ liệu đến nút lõi thì có 2 kênh không thỏa mãn yêu cầu của thuật toán là kênh 0 và kênh 3 do hệ số LAUT lớn, trong khi đó kênh 1 và kênh 2 là 2 kênh thỏa điều kiện của giải thuật. Trong trường hợp này, thuật toán sẽ chọn lựa kênh 1 (1 < 2) để là kênh ngõ ra cho burst dữ liệu.
Các tham số sử dụng cho giải thuật:
tub : Thời gian tới của burst chưa được lập lịch.
W: Số kênh dữ liệu ngõ ra.
i : kênh dữ liệu thứ i, i = 0 … W-1.
LAUTi : Thời gian rỗi sớm nhất của kênh thứ i
Gapi : gap là sự chênh lệch giữa thời gian đến của burst và các thông số LAUTi .
Thuật toán:
Bước 1: Khởi tạo i = 0;
Bước 2: Nếu i ≥ W, thông báo không thể lập lịch được và kết thúc;
Bước 3: Nếu Gapi = tub – LAUTi > 0 thì :
Lập lịch cho burst trên kênh thứ i và kết thúc;
Nếu không, quay lại bước 2 với kênh i = i+1;
Hình 2.2. Lưu đồ thuật toán FFUC
b. Thuật toán LAUC
Thuật toán LAUC (Latest Available Unschedule Channel) [5,10] không sử dụng void filling có thể được trình bày cơ bản như sau: Khi một burst dữ liệu đến một nút. Nút đó sẽ so sánh thông số Gapi = tub – LAUTi , nếu thông số này lớn hơn 0 thì kênh đó sẽ thích hợp để cấp cho burst đó. Trong trường hợp có nhiều hơn 1 kênh thích hợp, thuật toán sẽ chọn kênh có hệ số gap nhỏ nhất.
Hình 2.3. Mô hình thuật toán LAUC không sử dụng void filling
Trong trường hợp trên, cũng chỉ có 2 kênh thỏa mãn yêu cầu của giải thuật, nhưng thuật toán sẽ chọn kênh thứ 2 do có hệ số gap nhỏ hơn kênh thứ 1.
Hình 2.4. Lưu đồ thuật toán LAUC
Các tham số sử dụng cho thuật toán :
tub : Thời gian tới của burst chưa được lập lịch.
W: Số kênh dữ liệu ngõ ra.
LAUTi : Thời gian rỗi sớm nhất của kênh thứ i.
sc: chỉ số kênh được chọn (sc = -1 khi chưa có kênh nào được chọn).
i : kênh dữ liệu thứ i, i = 0 … W-1.
Gapi : gap là sự chênh lệch giữa thời gian đến của burst và các thông số LAUTi .
Gapmin: khoảng cách tối thiểu giữa burst đến và burst đã được lập lịch sau cùng nhất.
Thuật toán:
Bước 1: Khởi tạo i = 0; sc = -1; gap min = <giá trị lớn>;
Bước 2: Nếu i ≥ W: Chuyển sang bước 4;
Bước 3: Nếu LAUT i ≤ tub thì:
gapi = tub -LAUTi
Nếu gap i < gap min thì:
gap min = gap i ; sc = i;
i = i+1; quay lại bước 2
Bước 4: Nếu sc ≠ -1 thì:
Lập lịch cho burst đến trên kênh sc;
Bước 5: Kết thúc;
2.2.2. Thuật toán Void filling (with Void filling)
Thuật toán FFUC và LAUC có mức sử dụng tài nguyên thấp do nó không quan tâm đến các khoảng trống do đó người ta đưa ra một thuật toán khác sửa đổi từ thuật toán FFUC và LAUC ban đầu gọi là FFUC có sử dụng void filling (FFUC-VF) và thuật toán LAUC có sử dụng void filling (LAUC-VF). Trong các thuật toán có sử dụng void filling, khoảng trống giữa các burst và khoảng trống tính từ thời điểm sử dụng sau cùng của kênh dữ liệu hay thời gian kết thúc cuối cùng của burst cuối cùng được sắp xếp trên kênh dữ liệu đến vô cùng được tận dụng để sắp xếp các burst.
a. Thuật toán FFUC-VF
Các thuật toán sử dụng void filling thì bộ channel scheduling sẽ phải ghi nhận thông số bắt đầu và kết thúc của từng burst dữ liệu trên kênh truyền. Khi một burst dữ liệu đến, nếu thời điểm bắt đầu burst dữ liệu lớn hơn thời điểm kết thúc của burst trước đó và thời điểm kết thúc của burst dữ liệu nhỏ hơn thời điểm bắt đầu của burst liền sau nó (nếu sau nó không còn burst nào khác thì thời gian bắt đầu đó xem như là ∞) thì kênh truyền đó được chọn làm ngõ ra cho burst dữ liệu. Tương tự như trên, FFUC-VF sẽ chọn kênh có hệ số i nhỏ nhất làm kênh ngõ ra.
Hình 2.5. Mô hình thuật toán FFUC có sử dụng void filling
Trong trường hợp trên thì cả 4 kênh đều thỏa mãn điều kiện của giải thuật, nhưng thuật toán FFUC-VF [6,12] sẽ chọn kênh đầu tiên (kênh 0) làm kênh ngõ ra cho burst dữ liệu.
Các tham số sử dụng cho thuật toán :
Lb: Chiều dài burst chưa được lập lịch.
: Thời gian tới của burst chưa được lập lịch.
W: Số kênh dữ liệu ngõ ra.
i : kênh dữ liệu thứ i, i = 0 … W-1.
: Thời điểm bắt đầu và kết thúc của mỗi burst thứ j đã được sắp xếp trên kênh thứ i.
Giải thuật:
Bước 1: Khởi tạo i = 0;
Bước 2: Nếu i ≥ W: Chuyển sang bước 5;
Bước 3: Tìm khoảng trống khả dụng trên kênh i sao cho tub ≥ và ≥ tub+Lb;
– Nếu tìm thấy: Lập lịch cho burst đó trên kênh i và chuyển sang bước 5
Bước 4: Gán i = i+1 và quay lại bước 2;
Bước 5: Kết thúc;
Cũng tương tự như thuật toán FFUC-VF, thuật toán LAUC có sử dụng void filling [6,9] cũng thực hiện việc xác định kênh ngõ ra cho burst dữ liệu dựa vào các thông số là thời điểm bắt đầu và kết thúc của từng burst dữ liệu được truyền trên kênh truyền. Nhưng chỉ khác ở chỗ nếu có nhiều hơn 1 kênh đủ điều kiện, thì LAUC-VF sẽ chọn kênh rỗi gần nhất thay vì là kênh rỗi đầu tiên.
Hình 2.6. Mô hình thuật toán LAUC có sử dụng void filling.
Trong trường hợp này cả 4 kênh đều đủ điều kiện nhưng LAUC-VF sẽ chọn kênh số 3 do có thời gian rỗi gần với burst dữ liệu nhất.
Hình 2.7. Lưu đồ thuật toán LAUC-VF
Các tham số sử dụng cho thuật toán :
Lb: Chiều dài burst chưa được lập lịch.
tub: Thời gian tới của burst chưa được lập lịch.
W: Số kênh dữ liệu ngõ ra.
sc: chỉ số kênh được chọn (sc = -1 khi chưa có kênh nào được chọn).
i : kênh dữ liệu thứ i, i = 0 … W-1.
s_gapmin: khoảng cách tối thiểu giữa burst đến và burst đã được lập lịch trước đó.
: Thời điểm bắt đầu và kết thúc của mỗi burst thứ j đã được sắp xếp trên kênh thứ i.
Giải thuật:
Bước 1: Khởi tạo i = 0; sc = -1; s_gapmin = <giá trị lớn>;
Bước 2: Nếu i ≥ W chuyển sang bước 5;
Bước 3: Tìm khoảng trống trên kênh i sao cho: tub ≥ và ≥ tub +Lb ;
Nếu tìm thấy:
– Nếu: tub – < s_gapmin thì s_gapmin = tub – và sc = i;
Bước 4: Gán i = i+1 và quay lại bước 2;
Bước 5: Nếu sc ≠ -1 thì lập lịch cho burst trên kênh sc;
Bước 6: Kết thúc.
2.2.2.3. Thuật toán tối ưu BFUC-VF
Thuật toán BFUC-VF (Best Fit Unscheduled Channel – Void Filling) đề xuất một hướng tiếp cận khác khi chọn kênh tối ưu nhất cho một burst đến. Nó cố gắng sử dụng kênh tối đa và tối thiểu khả năng mất burst, nó lựa chọn tất cả các kênh khoảng trống khả dụng, trên đó burst dữ liệu có thể được lập lịch.
Theo Nandi M., và nhóm nghiên cứu (2009) [6] đã định nghĩa một tham số “hiệu quả (tỉ lệ) sử dụng băng thông khoảng trống” (utilization) khi một chùm được lập lịch vào một khoảng trống trên một kênh:
utilization = Lb *100/ (), i, i = 0…W-1.
Hình 2.8. Mô hình thuật toán BFUC-VF.
Kênh nào có gi trị hiệu quả s dụng băng thông khoảng trống lớn nhất s được chọn. Theo Hình 2.5 thì ở đây có 4 khoảng trống khả dụng để lập lịch cho burst đến nhưng đối với điều kiện chọn kênh của thuật toán BFUC-VF là tham số untization là lớn nhất vì vậy kênh D1 sẽ được chọn để lập lịch cho burst đến.
Các tham số sử dụng cho giải thuật:
Lb: Chiều dài burst chưa được lập lịch.
tub: Thời gian tới của burst chưa được lập lịch.
W: Số kênh dữ liệu ngõ ra.
sc: chỉ số kênh được chọn (sc = -1 khi chưa có kênh nào được chọn).
i : kênh dữ liệu thứ i, i = 0 … W-1.
Utilization: hiệu quả (tỉ lệ) sử dụng băng thông khoảng trống.
Giải thuật:
Bước 1: Chọn tất cả c c khoảng trống khả dụng trên c c kênh dữ liệu ra;
(Một khoảng trống trên một kênh được gọi là khả dụng để lập lịch cho chùm đến nếu tub ≥ và tub + Lb ≤ ). Nếu không có khoảng trống khả dụng trên một kênh nào đó thì chuyển sang bước 4;
Bước 2: Tính toán tham số utilization cho tất cả các khoảng trống khả dụng trên các kênh dữ liệu được tìm thấy ở bước 1;
Bước 3: Tìm kênh i có giá trị của tham số utilization lớn nhất và lập lịch cho chùm đó trên kênh i và kết thúc;
Bước 4: Lập lịch cho chùm theo thuật toán LAUC và kết thúc;
Trong chương này đã trình bày các thuật toán lập lịch trong mạng OBS. Các thuật toán cơ bản là FFUC và LAUC với các trường hợp có hay không sử dụng void filling và giải tuật BFUC-VF. Yêu cầu đặt ra là ta phải chọn được thuật toán tốt nhất đáp ứng yêu cầu tối ưu số lượng burst tại đầu vào được sắp xếp trên các kênh dữ liệu để đảm bảo các burst được di chuyển nhanh nhất, đầy đủ nhất đến đầu ra. Trong phần mô phỏng của đồ án sẽ trình bày cụ thể về vấn đề mô phỏng các thuật toán xếp lịch trong mạng OBS, qua đó ta sẽ thấy được tính chất, ưu nhược điểm của từng thuật toán để chon được thuật toán tốt nhất đáp ứng nhu cầu vận chuyển một lượng dữ liệu lớn qua mạng với tốc độ cao.
CHƯƠNG 3
CÀI ĐẶT MÔ PHỎNG VÀ PHÂN TÍCH KẾT QUẢ
Trong chương trước đã trình bày cụ thể về một số thuật toán lập lịch trong mạng OBS, để hiểu rõ hơn về các thuật toán này cũng như cách hoạt động và sắp xếp burst trên các kênh dữ liệu sao cho giảm thiểu khả năng mất burst. Em sẽ sử dụng phần mềm NS2 (Network simulation version 2) và gói hỗ trợ nOBS v2.0 để mô phỏng hoạt động của các thuật toán này. Chương này sẽ đưa ra kết quả mô phỏng ứng với từng thuật toán và so sánh kết quả để xem xét thuật toán nào tối ưu nhất trong năm thuật toán đã trình bày cho quá trình sắp xếp burst vào các kênh dữ liệu. Tuy nhiên kết quả mô phỏng chỉ có giá trị cho việc nghiên cứu và phân tích sơ bộ tính hiệu quả của các giải thuật, gói hỗ trợ nOBS v2.0 vẫn còn nhiều điểm hạn chế về khả năng hỗ trợ cho các thuật toán cũng như việc phân tích kết quả lập lịch khá khó khăn.
3.2. GIỚI THIỆU CHƯƠNG TRÌNH MÔ PHỎNG
Network Simulator Version 2, còn được biết đến với tên viết tắt là NS2, là một công cụ mô phỏng sự kiện rất hữu ích trong lĩnh vực nghiên cứu và học tập mạng truyền thông. NS2 có thể mô phỏng cả mạng có dây, mạng không dây và các giao thức (TCP, UDP) cũng như các thuật toán định tuyến… Nhìn chung NS2 cung cấp cho người dùng một cách để xác định các giao thức mạng và hành vi tương ứng của chúng. Do tính linh hoạt và tính mô dun của nó, NS2 đã trở nên phổ biến không ngừng trong cộng đồng nghiên cứu mạng kể từ khi nó ra đời vào năm 1989.
Hình 3.1 dưới đây mô tả kiến trúc cơ bản của NS2, NS2 cung cấp cho người dùng một câu lệnh thực thi ‘ns’ với đầu vào là một file Tcl. File Tcl này do người dùng tạo ra để mô phỏng các kịch bản mạng truyền thông. Sau đó NS2 sẽ tạo ra kết quả mô phỏng.
E:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\HE THONG THONG TIN\NGUYEN QUOC VINH
