Tổng quan về mạng OBS,tìm hiểu và mô phỏng các giải thuật xếp lịch và quá trình thiết lập burst

dùng các bản tin điều khiển thiết lập và giải tỏa tường minh. JET là giao thức báo hiệu một chiều không cần thông tin hồi đáp, dùng các gói header của burst – BHP (burst header packet) có tính ước lượng để giải tỏa và thiết lập. Để khỏi phải chuyển đổi quang điện trong lõi, các phương pháp báo hiệu có một offset time giữa BHP và dữ liệu tương ứng của nó. Trong BHP có chứa thông tin về chiều dài của burst, kết hợp với thông tin về offset time, báo cho node biết được thời điểm node này cần cấu hình bộ chuyển mạch cho burst dữ liệu sắp tới. Khoảng thời gian offset time cho phép BHP được xử lý tại node trung gian trước khi burst dữ liệu tới node trung gian đó. Nếu ta đem so sánh giữa TAW và JET, nhược điểm của TAW là trễ do round-trip time, nhưng bù lại rất ít mất dữ liệu, vì vậy TAW phù hợp cho loss-sensitive traffic. Về phía JET, mất dữ liệu dễ xảy ra, nhưng độ trễ khi truyền dữ liệu từ đầu cuối này tới đầu cuối khác ít hơn TAW. Trong TAW phải mất 3 lần độ trễ lan truyền từ nguồn tới đích thì burst mới tới được đích, trong khi đó JET chỉ cần lần trễ lan truyền một chiều và một khoảng offset time. Như ta đã nói, chưa có phương pháp báo hiệu riêng biệt nào cho phép kết hợp uyển chuyển giữa độ trễ và việc mất dữ liệu. Trong mạng IP over OBS, người ta mong muốn cung cấp hỗ trợ chất lượng dịch vụ cho các ứng dụng đòi hỏi nhiều yêu cầu về chất lượng dịch vụ khác nhau, chẳng hạn như voice-over-IP, video-on-demand, hay video conferencing. Nhiều giải pháp được đưa ra để hỗ trợ chất lượng dịch vụ trong mạng lõi OBS. Tuy nhiên, không có phương pháp đơn lẻ (không có sự kết hợp giữa các giao thức lại) nào cho phép hỗ trợ một cách mềm dẻo cả hai yêu cầu về độ trễ và mất dữ liệu trong mạng OBS. Có một số phương pháp cải thiện QoS, ví dụ như JET kết hợp với offset time dành cho các lớp lưu lượng khác nhau, chịu được xác suất nghẽn cao. Trong phương pháp này, node nguồn phải ước lượng trước offset time để có thể hỗ trợ cho các yêu cầu khác nhau của các lớp gói dữ liệu. Để khắc phục các hạn chế của hai phương pháp TAW và JET, phương pháp báo hiệu được khởi tạo ở node trung gian INI được đưa ra. Trong phương pháp INI, một node ở giữa node nguồn và node đích nằm trên đường truyền được chọn làm node khởi tạo (initiating node). Tại node khởi tạo này, một thuật toán dự trữ kênh sẽ được thực hiện nhằm xác định thời gian sớm nhất mà burst có thể được gửi đi ở node nguồn và thời gian sớm nhất tương ứng mà tại đó các node ở giữa node nguồn với node khởi tạo có thể được sắp xếp để nhận burst dữ liệu tới. Việc dự trữ thật sự các kênh ở node khởi tạo bắt đầu theo cả hai hướng: từ node khởi tạo tới node nguồn lẫn từ node khởi tạo về node đích. Việc lựa chọn node khởi tạo được chỉ ra trong giao thức báo hiệu INI. Hình 3.5s minh họa phương pháp báo hiệu INI. Khi một burst dữ liệu được hình thành tại node biên, một bản tin BHP thiết lập (setup BHP) được gửi tới node. BHP sẽ thu thập thông tin chi tiết về các kênh tại mỗi node nó đi qua cho tới khi đến node khởi tạo (initiating node). Tại node khởi tạo, thuật toán cấp phát kênh được thực thi để xác định khoảng thời gian mà kênh cần được dự trữ tại mỗi hop trung gian nằm giữa node nguồn và node khởi tạo. Kế đó, một gói xác nhận (confirm packet) được gửi ngược về node nguồn, gói này tiến hành dự trữ các kênh dọc theo đường đi của nó từ node khởi tạo tới node nguồn. Nếu có kênh bận ở bất kỳ node nào, gói giải tỏa (release packet) sẽ được gửi trở về node khởi tạo để giải tỏa hết cho các tài nguyên trước đó đã dự trữ thành công. Nếu gói xác nhận tới được nguồn thành công thì burst dữ liệu sẽ được gửi đi tại thời điểm đã được sắp xếp trước. Cùng với lúc gửi đi gói xác nhận về node nguồn, node khởi tạo cũng gửi đi một bản tin BHP thiết lập không cần trả lời (unacknowledged setup BHP) về phía node đích nhằm dự trữ trước các kênh truyền giữa node khởi tạo và node đích. Nếu tại bất kì node nào giữa node khởi tạo và node đích mà bản tin BHP không dự trữ được kênh truyền thì burst dữ liệu sẽ bị drop ở node đó. Hình 3.5: Báo hiệu được khởi tạo ở node trung gian INI. Trong giao thức TAW, bản tin ACK được gửi từ phía đích trước khi burst dữ liệu được gửi đi từ nguồn, còn trong JET, không có ack. Ở INI, có ack xuất phát từ node khởi tạo, vì vậy giảm được xác suất nghẽn so với JET. Không những thế, vì khoảng thời gian mà burst dữ liệu phải đợi tại nguồn ít hơn khoảng thời gian trễ do lan truyền từ nguồn tới đích nên INI giảm được trễ truyền từ đầu cuối đến đầu cuối khi so sánh vói TAW. Trong giao thức báo hiệu INI, nếu node khởi tạo là node nguồn thì nó trở thành báo hiệu JET, nếu node khởi tạo là node đích thì trở thành báo hiệu TAW. Trong INI, ta có thể dùng cả hai phương pháp dự trữ thông thường hay dự trữ có trì hoãn đều được. Với các dự trữ có trì hoãn thì hoạt động của giao thức báo hiệu được cải thiện hơn. 3.2.5 Ví dụ minh họa: Xem đường đi 2-4-5-7 trong hình 3.6 có node 2 là node nguồn, node 7 là node đích. Ta có 4 node có thể làm node khởi tạo, bao gồm luôn cả node nguồn và node đích. Nếu ta chọn node nguồn (chính là node 2) làm node khởi tạo thì báo hiệu INI trở thành báo hiệu JET. Nếu chọn node đích làm node khởi tạo (node 7) thì trở thành báo hiệu TAW. Các node có khả năng làm node khởi tạo khác là node 4 và node 5. Ta xét node 5 là node khởi tạo. Hoạt động của INI như sau: node 2 gửi bản tin BHP cho hop kế tiếp là node 4, có kèm theo thông tin về kênh sẵn sàng trên link 2-4. Tại node 4 thêm vào thông tin về kênh sẵn sàng trên link 4-5 sau đó gửi đi bản tin BHP tới node kế là node 5. Khi node 5 là node khởi tạo nhận được bản tin BHP, nó thực hiện một thuật toán dự trữ kênh để xác định thời gian sớm nhất mà lúc đó burst yêu cầu có thể được phục vụ bởi các node trung gian nằm giữa node nguồn với node khởi tạo, bao gồm cả node nguồn và node khởi tạo. Một gói trả lời, sẽ dự trữ kênh truyền tại các node trung gian này vào thời điểm đã được định trước, được gửi ngược về từ node khởi tạo tới node nguồn. Ngay khi gói trả lời tới được node nguồn 2 thì burst dữ liệu sẽ được gửi đi. Có một bản tin BHP được gửi từ node khởi tạo (node 5) đến node đích (node 7) và cấu hình cho node 7 chuẩn bị nhận burst dữ liệu tới vào thời điểm thích hợp. Node 7 không gửi bản tin ack về cho node khởi tạo. Bản tin BHP được gửi đi từ node khởi tạo chỉ có nhiệm vụ dự trữ kênh truyền sẵn sàng và tiếp tục đi theo hướng từ node khởi tạo về phía đích. Hình 3.6: Cấu hình mạng 14 node. 3.3. Các phương pháp giải quyết xung đột trong mạng OBS Trong mạng OBS các burst được truyền từ node nguồn đến node đích sau khi được chuyển mạch qua hết các node trung gian mà không cần bộ đệm quang nên khả năng xảy ra xung đột giữa các burst là rất lớn. Xung đột có thể xảy ra khi nhiều burst muốn rời node lõi trên cùng một tuyến WDM hay burst ở các ngõ vào khác nhau muốn đến một ngõ ra tại cùng một thời điểm. Các phương pháp giải quyết xung đột được đề xuất như sau 3.3.1. Các đường dây trễ quang FDL (Fiber Delay Line) Nếu như trong miền điện tử có các bộ nhớ truy cập ngẫu nhiên như RAM thì trong miền quang ý tưởng bộ đệm quang vẫn chưa thực hiện được. Vì vậy để đệm burst dữ liệu trong một khoảng thời gian người ta chỉ có thể dùng đến các đường dây trễ quang FDL. Các burst dữ liệu được lưu giữ trong miền quang một khoảng thời gian cố định. Bằng cách kết nối các dây trễ FDL theo tầng hay kết nối song song, bộ đệm được đề xuất này có thể giữ các burst dữ liệu trong các thời gian khác nhau. Với phương pháp này, burst đang tham gia tranh chấp sẽ được làm trễ lại cho tới khi nghẽn được giải quyết. Phương pháp này dựa trên ý tưởng là: khi một bước sóng được yêu cầu lại chưa sẵn sàng thì burst dữ liệu sẽ được làm trễ lại trong một FDL cho tới khi kênh bước sóng đó trở về trạng thái sẵn sàng. Burst mới đến D (Delay period using FDL) time Bước sóng ngõ ra l1 Hình 3.7: Giải quyết xung đột bằng phương pháp sử dụng đường dây trễ FDL Ở hình trên kênh bước sóng mong muốn của burst dữ liệu là λ1 nhưng kênh này đã bị chiếm tại thời điểm tới của burst. Trong trường hợp này, burst dữ liệu sẽ được đệm lại trong khoảng thời gian ∆, khi đó kênh này đã trở về trạng thái sẵn sàng tại thời điểm tới của burst dữ liệu sau khi đã được đệm. Do FDL dựa trên trễ truyền của cáp quang và sự truy cập liên tục nên nó có nhiều hạn chế so với RAM. Nếu dung lượng bộ đệm lớn thì số lượng và chiều dài của FDL càng tăng nên dễ gây tổn hao và việc sử dụng bộ đệm cũng không thể hoàn toàn giảm khả năng mất burst 3.3.2. Bộ chuyển đổi bước sóng Sử dụng bộ chuyển đổi bước sóng wavelength converter để chuyển đổi kênh ngõ ra khác cho burst dữ liệu nếu như kênh nó mong muốn đã bị chiếm giữ tại thời điểm burst tới node. Trong WDM, nhiều bước sóng được ghép cùng một lúc trên một liên kết nối hai chuyển mạch chùm quang. Nhiều bước sóng có thể giảm tối đa số lượng xung đột. Giả sử có hai burst cùng đi đến một đích và ra ở cùng ngõ ra tại một thời điểm. Cả hai burst vẫn có thể truyền đi tiếp nếu ở trên hai bước sóng khác nhau. Chuyển đổi bước sóng là quá trình chuyển đổi một bước sóng ở ngõ vào thành một bước sóng khác ở ngõ ra, do vậy làm tăng khả năng sử dụng lại bước sóng nghĩa là tất cả các kênh bước sóng trên cùng một cáp quang có thể được dùng chung bởi tất cả các burst. Có các kiểu chuyển đổi sau: Chuyển đổi toàn bộ (Full conversion): Một bước sóng có thể chuyển thành bất kì bước sóng nào ở đầu ra, do vậy không có một bước sóng nào xuất hiện liên tục trên một kết nối từ đầu cuối đến đầu cuối. Chuyển đổi có giới hạn (Limitted conversion): Việc chuyển đổi bước sóng bị giới hạn để không phải tất cả các kênh ngõ vào đều có thể kết nối đến kênh ngõ ra. Việc giới hạn này sẽ làm giảm chi phí của chuyển mạch trong khi chấp nhận một số lượng xung đột Chuyển đổi cố định (Fixed conversion): Đây cũng là một dạng của chuyển đổi có giới hạn, trong đó một kênh ngõ vào được kết nối với một hay nhiều kênh ngõ ra được chỉ định trước Chuyển đổi một phần (Sparse conversion): Trong mạng có thể bao gồm các node có chuyển đổi toàn bộ có giới hạn, cố định và không có bộ chuyển đổi bước sóng Burst mới tới CH 1 CH 2 Bước sóng ngõ ra l1 l2 Hình 3.8: Giải quyết xung đột bằng phương pháp chuyển đổi bước sóng. 3.3.3. Định tuyến chuyển hướng Trong định tuyến chuyển hướng, xung đột được giải quyết bằng cách định tuyến burst dữ liệu đến một ngõ ra khác thay vì ngõ ra ban đầu, tức là kể từ node đó đi theo con đường khác để đến đích chứ không còn đi theo con đường ngắn nhất ban đầu. Định tuyến chuyển hướng không được quan tâm đối với mạng chuyển mạch gói trong miền điện, tuy nhiên nó lại thực sự cần thiết trong mạng toàn quang khi chưa có bộ đệm quang. Trong định tuyến chuyển hướng, gói hay burst dữ liệu bị chuyển hướng có thể đi trên con đường dài hơn để đến đích làm tăng độ trễ và giảm chất lượng tín hiệu. Hơn nữa, có thể một gói sẽ bị vòng lặp (loop) trong mạng do không tìm được đường đến đích hay bị chuyển hướng quá nhiều và thêm tắc nghẽn trong mạng. Một số vấn đề khác trong định tuyến chuyển hướng là bảo trì thời gian offset giữa gói điều khiển và gói dữ liệu của một burst bị chuyển hướng. Bởi vì burst bi chuyển hướng phải đi trên đường có số node trung gian nhiều hơn khi nó không bị chuyển hướng, do đó thời gian offset trước đây là không đủ để các chuyển mạch kế tiếp xử lý các gói điều khiển trước khi burst dữ liệu đến. Để khắc phục vấn đề này, nhiều xử lý được thêm vào để tính toán lại thời gian offset. Một cách đơn giản hơn là chỉ cần loại bỏ những burst có thời gian offset không hợp lệ. Để biết được số node trung gian mà burst phải đi qua ta có thể dùng các bộ đếm. 3.3.4. Phân đoạn burst Trong phương pháp này burst được phân thành các đoạn để khi có xung đột thì chỉ có một phần burst bị mất, phần còn lại vẫn được truyền qua mạng. Phần burst bị mất có thể là phần trước hay phần sau. Nếu burst bị hủy bỏ phần đầu thì phần burst còn lại cần thông tin của offset giữa gói tin điều khiển của burst và điểm đầu của phần burst còn lại. Nếu burst bị hủy bỏ phần đuôi thì cần phải thêm gói tin điều khiển của burst cho phần đuôi bị hủy bỏ. Nếu như ranh giới giữa các đoạn hoàn toàn trong suốt trong mạng lõi toàn quang thì các node biên phải chịu trách nhiệm định nghĩa và xử lý các đoạn trong miền Hình 3.9: Giải quyết xung đột bằng phương pháp phân đoạn burst điện. Hơn nữa, node nhận phải có khả năng nhận ra điểm bắt đầu của mỗi đoạn và xác định xem thử đoạn đó còn nguyên vẹn hay không, do đó một số header dùng để nhận ra lỗi và sửa lỗi chứa trong một đoạn. Thêm vào đó thông tin về tín hiệu đồng hồ có thể cũng cần phải có trong mỗi header của mỗi đoạn để node nhận ngõ ra có thể xác định và phục hồi dữ liệu trên mỗi đoạn. Khi các đoạn có chiều dài không đổi thì việc đồng bộ ở máy thu trở nên dễ dàng, tuy nhiên những đoạn có chiều dài thay đổi lại có khả năng chứa được những gói có chiều dài khác nhau. Kích thước của mỗi đoạn còn phải cân nhắc giữa mất mát trong một lần xung đột và số lượng header trong một burst. Đoạn dài sẽ dẫn đến mất nhiều dữ liệu cho mỗi lần xung đột, tuy nhiên những đoạn dài cũng dẫn đến overhead và tỉ số giữa chiều dài header sovới chiều dài payload sẽ nhỏ theo. Một số vấn đề khác trong phân đoạn burst là quyết định xem đoạn nào bị rớt khi xung đột xảy ra giữa hai burst. Giả sử gọi burst bị xung đột là contented burst còn burst xung đột là contenting burst. Chú ý rằng burst được xem là contented hay contenting burst phụ thuộc vào thứ tự của nó đến chuyển mạch chứ không phải thứ tự của gói điều khiển đến trước hay đến sau. Có hai cách để xác định xem những đoạn nào nên rớt, được gọi là tail-dropping (rớt phần đuôi) và head-dropping (rớt phần đầu). Trong cách rớt phần đuôi tail-dropping thì các đoạn chồng lấn của contented burst sẽ bị rớt còn trong cách rớt phần đầu heading-dropping thì các đoạn của contenting burst chồng lấn sẽ bị rớt. Ưu điểm của việc tail-dropping so với tail-dropping trong việc thay đổi các gói sai thứ tự ở node đích với giả thuyết rằng các gói rớt được truyền lại sau đó. Việc head-dropping làm cho các gói đến đích sai thứ tự, tuy nhiên, ưu điểm của head-dropping là nó chắc chắn rằng một khi burst đến một node không bắt gặp một xung đột nào và sao đó các burst này tiếp tục đi đến đích mà không phụ thuộc vào các burst đi sau nó có mức ưu tiên nào đi chăng nữa. 3.4 Kết luận chương Vậy là trong chương này em đã trình bày các giao thức báo hiệu cũng như các phương pháp giải quyết xung đột trong mạng OBS. Có nhiều các kỹ thuật dự trữ và giải phóng tài nguyên nhưng kỹ thuật báo hiệu một chiều JET với dự trữ có trì hoãn và giải tỏa không tường minh cho xác suất burst được chấp nhận cao hơn các kỹ thuật khác được đề nghị sử dụng trong mạng OBS. Việc lựa chon giữa các biện pháp giải quyết xung đột cũng là một vấn đề quan trong nhằm giảm tỉ lệ mất burst đến mức thấp nhất có thể. Tùy theo yêu cầu cụ thể của từng mạng và điều kiện cho phép mà ta chọn ra phương pháp thích hợp hay để tận dụng các ưu điểm của mỗi phương pháp ta có thể sử dụng kết hợp chúng sẽ cho hiệu quả giảm tỉ lệ mất burst cao hơn nhiều so với việc dùng riêng lẽ từng phương pháp. Chương 4 CÁC GIẢI THUẬT XẾP LỊCH TRONG MẠNG OBS 4.1 Giới thiệu chương 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). Trong phần này, em sẽ trình bày về 2 loại xếp lịch này dựa trên hai giải thuật cơ bản là FFUC (First Fit Unscheduled Channel) và LAUC (Latest Available Unscheduled Channel). 4.2 Các thông số sử dụng trong các thuật toán sắp xếp Các thông số được sử dụng cho hầu hết các loại thuật toán sắp xếp là: : Chiều dài burst chưa được sắp xếp. : Thời gian tới của burst chưa được sắp xếp. W: Số kênh dữ liệu ngõ ra. : Số burst tối đa dùng trên một kênh ngõ ra. : Kênh ngõ ra thứ i. : Thời gian rỗi sớm nhất của kênh thứ i, dùng cho bộ xếp lịch ko sử dụng void filling. , : 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. : Nếu kênh rỗi, gap là sự chênh lệch giữa thời gian đến của burst và các thông số đối với trường hợp không sử dụng void filling, và thông số đối với trường hợp có void filling. Thông số Gap là cơ sở để thuật toán quyết định nên sử dụng kênh nào khi có hơn 1 kênh rỗi. Trong trường hợp kênh không rỗi, hệ số gap bằng 0. 4.3 Các giải thuật xếp lịch cơ bản 4.3.1 Các thuật toán không sử dụng void-filling 4.3.1.1 Thuật toán FFUC Giải thuật FFUC (First Fit Unschedule Channel) 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ố = - , 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 4.1: Mô hình giải thuật 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 thuật toán. 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. i =ncc i i≤ n Y N begin Sắp xếp burst update end fdl ≤ max Y Làm trễ N i++ scheTime > TH Y Channel = i Drop burst N Hình 4.2: Lưu đồ giải thuật FFUC 4.3.1.2 Giải thuật LAUC Giải thuật LAUC (Latest Available Unschedule Channel) 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ố = - , 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. LAUT 0 Hình 4.3: Mô hình giải thuật 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 thuật toán, 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. i = ncc i i≤ n i ++ Y N Tìm channel begin Có channel Sắp xếp burst update end fdl ≤ max N Y Làm trễ N Y Drop burst N Y Hình 4.4: Lưu đồ giải thuật LAUC 4.3.2 Giải thuật có sử dụng void filling Giải thuật 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ừ giải thuật FFUC và LAUC ban đầu gọi là FFUC có sử dụng void filling (FFUC-VF) và giải thuật 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. 4.3.2.1 Giải thuật FFUC_VF Các giải thuật 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 sẽ chọn kênh có hệ số i nhỏ nhất làm kênh ngõ ra. Hình 4.5 Mô hình giải thuật 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 thuật toán, nhưng thuật toán FFUC sẽ chọn kênh đầu tiên (kênh 0) làm kênh ngõ ra cho burst dữ liệu. 4.3.2.2 Thuật toán LAUC_VF Cũng tương tự như thuật toán FFUC_VF, thuật toán LAUC có sử dụng void filling 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 sẽ chọn kênh rỗi gần nhất thay vì là kênh rỗi đầu tiên. Hình 4.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 sẽ chọn kênh số 3 do có thời gian rỗi gần với burst dữ liệu nhất. scheTime ≥ start (end–scheTime)≥ ScheDur scheTime – start < diff scheTime ≥ TH Channel = i diff = scheTime- TH Y N (scheTime – TH) < diff Y N Y N N Y N result = Channel begin end i = ncc i Channel = i diff = scheTime-start i++ Y i<=n N N N Y N N Y Y Y Hình 4.7: Lưu đồ giải thuật LAUC_VF Tóm lại: Thuật toán FFUC là một thuật toán khá đơn giản, dễ thực hiện, nhưng bù lại khả năng mất burst dữ liệu của thuật toán này khá cao. Thuật toán LAUC hay còn gọi là horizon phức tạp hơn, nhưng nó lại cho hiệu quả cao hơn so với FFUC. Việc sử dụng void filling sẽ làm tăng hiệu quả kênh truyền dữ liệu hơn, đồng thời nó cũng làm giảm tỉ lệ mất burst đáng kể cho hệ thống. Chất lượng hệ thống sẽ cải thiện rất nhiều nếu sử dụng chung với FDL (Fiber Delay Line). 4.3.3 Vấn đề sử dụng các đường dây trễ quang FDL trong các giải thuật xếp lịch Để giảm tỉ lệ mất burst ta có thể sử dụng các đường dây trễ quang FDL. Các tính chất cũng như hoạt động của FDL đã được trình bày trong phần các phương pháp giải quyết xung đột ở chương 2 4.3.3.1 Thuật toán không sử dụng FDL Hình 4.8 : Lưu đồ thuật toán không sử dụng FDL Totalchannel: Số kênh sử dụng trong mạng. Ncc: Số kênh dành cho burst header Time gap: Tham số xem xét xem coi có sắp xếp được burst dữ liệu vào kênh truyền hay không . startTime: thời điểm tới của burst dữ liệu. horizon_[i]: Thời điểm rỗi của kênh thứ i. Thuật toán FirstFit: unsigned int ndc = totalchannel_ - ncc_; // số kênh dữ liệu int ch = UNAVAILABLE; for( int i = 0; i < ndc; i++ ) { double time_gap = startTime - horizon_[i];// horrizon_[i]: if ( time_gap >= 0.0 ) { ch = i; break; } // end of >= 0.0 } // end of for if ( ch != UNAVAILABLE ) { result.Fflag() = FOUND; result.LambdaID() = ch; result.StartTime() = startTime; } else { result.Fflag() = NOT_FOUND; } return (result); } Thuật toán Horizon (LAUC): unsigned int ndc = totalchannel_ - ncc_; int ch = UNAVAILABLE; double min_time_gap; for( int i = 0; i < ndc; i++ ) { double time_gap_ = startTime - horizon_[i]; if ( time_gap_ >= 0.0 ) { if ( ch == UNAVAILABLE ) { // the first time for updating min_time_gap min_time_gap = time_gap_; ch = i; } else { if ( min_time_gap > time_gap_ ) { min_time_gap = time_gap_; ch = i; } } // end of UNAVAILABLE } // end of >= 0.0 } // end of for // evaluate the search process to report searching result if ( ch != UNAVAILABLE ) { result.Fflag() = FOUND; result.LambdaID() = ch; result.StartTime() = startTime; } else { result.Fflag() = NOT_FOUND; } return (result); } 4.3.3.2 Thuật toán có sử dụng FDL FirstFit/Horizon Hình 4.9 : lưu đồ thuật toán có sử dụng FDL Đoạn code dùng cho các loại thuật toán có sử dụng bộ đệm FDL giống như không sử dụng bộ đệm, chỉ khác ở chỗ, trước khi cho drop một burst thì biến số starttime sẽ được cộng thêm một lượng là unitdelay, sau đó sẽ là một vòng loop tìm kiếm kênh rỗi lại. Đoạn code cần thêm vào như sau: for( int j = 0; i < N; j++ ) {… startTime = starTime + unitdelay. } else { result.Fflag() = NOT_FOUND; } return (result); } 4.5 Kết luận chương Trong chương này đã trình bày các giải thuật lập lịch trong mạng OBS. Các giải thuật cơ bản là FFUC và LAUC với các trường hợp có hay không sử dụng void filling, trường hợp có hay không sử dụng các đường tạo trễ FDL. Yêu cầu đặt ra là ta phải chọn được giải thuật 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 giải thuật để chon được giải thuật 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. Việc kết hợp các giải thuật cơ bản với sử dụng void filling hay FDL cũng được đề cặp đến trong phần mô phỏng. Chương 5 MÔ PHỎNG VÀ KẾT QUẢ 5.1 Giới thiệu chương Trong chương 3 đã trình bày các giải thuật xếp lịch trong mạng OBS. Muốn sắp xếp được càng nhiều burst trên các kênh dữ liệu yêu cầu ta phải chọn được thuật toán tốt nhất để giảm thiểu khả năng mất burst. Đây là một vấn đề rất quan trọng đối với chất lượng của mạng OBS. Đồng thời để giảm khả năng mất burst đến mức thấp nhất có thể ta phải chọn được kích thước burst tối ưu trong quá trình thiết lập burst từ các gói tin riêng rẽ ở đầu vào.Chương này đưa ra kết quả mô phỏng ứng với từng thuật toán được xem xét để chọn được thuật toán nào tốt nhất cho quá trình sắp xếp burst vào các kênh dữ liệu trong mạng OBS. Bên cạnh đó các kết quả mô phỏng cho quá trình thiết lập burst cũng được nêu lên để đánh giá và chọn ra dải kích thước burst trong đó xác suất mất burst là nhỏ nhất đối với mô hình mạng cụ thể trong bài toán mô phỏng. Đồng thời chương này còn giới thiệu sơ lược phần mềm mô phỏng NS2 phục vụ cho mô phỏng các thuật xếp lịch trên. 5.2. Giới thiệu phần mềm NS2 Phần mềm NS2(network simulation version 2) là chương trình mô phỏng mã nguồn mở dành cho mục đích nghiên cứu, thực hiện mạng số liệu dựa trên chuyển mạch gói. Không chỉ là công cụ mô phỏng, NS-2 còn là chương trình có nhiều module hỗ trợ và một thư viện rất tiện ích cho việc mô phỏng các sự kiện riêng lẻ. NS2 là chương mô phỏng hướng đối tượng được viết bằng hai ngôn ngữ lập trình C++ và OTcl, chúng hỗ trợ chặt chẽ cho nhau. Kiến trúc phần mềm NS2 TK8.4.5 OTcl tclcl Tcl8.4.5 ns-2.28 nam-1.19 tcl ex test lib ... ... Các ví dụ Các kiểm tra Mã C++ Mã OTcl ns-allinone-2.28 mcast Hình 5.1. Kiến trúc thư mục cài đặt của NS2 và NAM trong môi trường Linux Trong số các thư mục con của ns-allinone-2.28 thì ns-2 là nơi chứa các file phục vụ cho mô phỏng (cả viết bằng C++ lẫn OTcl). Trong thư mục này, tất cả OTcl code và những kịch bản ví dụ đều chứa trong thư mục gọi là tcl và hầu hết được viết bằng C. Thư mục tcl có những thư mục con, trong số đó có thư mục lib chứa mã nguồn OTcl cho những thành phần cơ bản nhất và quan trọng nhất (agent, node, link, packet, address, routing,…). Ns-lib. Tcl: Lớp mô phỏng và đa số các định nghĩa chức năng thành phần của nó ngoại trừ LAN, Web, và Multicast được chứa trong file này. Ns-default. Tcl: Những giá trị mặc định cho các thong số cấu hình cho các thành phần mạng được chứa ở đây. Bởi vì nhiều thành phần mạng được bổ sung bằng C++, nên những thông số là những biến C++ tạo ra các giá trị cho OTcl qua chức năng liên kết OTcl. Ns-packet. Tcl: Thành phần khởi tạo những định dạng header của gói được chứa trong file này. Khi tạo ra một gói header thì phải đăng kí header trong file này để tạo ra những xử lý khởi tạo. Ở mức độ người sử dụng: Việc mô phỏng bắt đầu bằng việc nắm rõ các câu lệnh tạo đối tượng mô phỏng từ đó xây dựng các kịch bản mô phỏng Tcl. Sau khi tạo một kịch bản mô phỏng Tcl, việc chạy chương trình chỉ bằng lệnh trong terminal trong Linux. Ở mức độ người vừa phát triển vừa sử dụng: Việc phát triển phần mềm bắt đầu từ việc nắm rõ cấu trúc thư mục chính trong NS2 cùng với một số file quan trọng liên quan trọng liên quan đến đối tượng mới cần them vào. Khi người sử dụng tạo ra một chương trình mô phỏng chạy trên nền NS2 cho riêng mình thì cũng có thể tạo đối tượng riêng cho mình, đó cũng là một ưu điểm của phần mềm NS2 mã nguồn mở. Kiến trúc liên kết của NS2: Một bộ phận chính khác trong NS-2 là link. Phần tử kết hợp này gồm ba phần chính: hàng đợi, delay và drophead-object. Hàng đợi quản lý thông lượng các gói phát trên link. Phần tử delay giả lập trễ khi gói truyền trong link. Và drophead-object quản lý các gói bị rớt từ hàng đợi của link. Cấu trúc của link trong NS-2 được mô tả như hình 5.2 Hình 5.2. Kiến trúc liên kết của NS2 5.3. Mô phỏng các giải thuật xếp lịch trong mạng OBS Trong phần mô phỏng sử dụng mô hình mạng gồm 10 node lõi và 10 node biên nối vòng ring như hình. Giao thức được sử dụng là JET với thời gian offset là 0.000001s. Mỗi liên kết có 6 kênh bước sóng gồm 2 kênh điều khiển và 4 kênh dữ liệu. Băng thông mỗi kênh là 20Gb/s. Phương pháp thiết lập burst được sử dụng là thiết lập burst vừa theo độ dài vừa theo thời gian với kích thước tối đa của mỗi burst là 60000 byte, thời gian thiết lập là 0.0003s. Hình 5.3 Mô hình mạng OBS nối vòng ring Kết quả cho ra ở mỗi thuật toán là lượng dữ liệu truyền được qua mạng ứng với lưu lượng của mạng thay đổi từ 1.0000 đến 1.1000 Erlang 5.3.1 Thuật toán FFUC Hình 5.4. Lượng dữ liệu truyền được qua mạng khi sử dụng thuật toán FFUC 5.3.2 Thuật toán LAUC Hình 5.5 Lượng dữ liệu truyền được qua mạng khi sử dụng thuật toán LAUC 5.3.3 Thuật toán LAUC_VF Hình 5.6 Lượng dữ liệu truyền được qua mạng khi sử dụng thuật toán LAUC-VF 5.3.4. So sánh kết quả các thuật toán trên Để dễ dàng so sánh hiệu quả các thuật toán trên em lấy số liệu kết quả của cả 3 và vẽ trên cùng một đồ thị Hình 5.7 So sánh lượng dữ liệu truyền qua mạng đối với 3 thuật toán Dựa vào đồ thị trên ta có thể thấy lượng dữ liệu truyền qua mạng của 2 thuật toán FFUC và LAUC gần như bằng nhau nên 2 đường biểu diễn của chúng trên đồ thị trùng nhau. Trong thực tế thì thuật toán LAUC tuy có sử dụng tài nguyên tốt hơn FFUC do tạo khoảng trống giữa thời gian đến của burst và thời gian sử dụng cuối cùng của kênh dữ nhưng các khoảng trống này khá nhỏ không thể sắp xếp burst khác được nên hiệu quả của thuật toán FFUC và LAUC là như nhau. Còn thuật toán LAUC_VF do có xét đến khoảng trống trên các kênh dữ liệu để sắp xếp burst nên hiệu quả cao hơn, lượng dữ liệu truyền được qua mạng cao hơn hẳn 2 thuật toán kia. Bảng: lượng dữ liệu truyền qua mạng cho các thuật toán 5.3.5 So sánh các thuật toán có và không có sử dụng FDL 5.3.5.1 Thuật toán LAUC không sử dụng FDL Hình 5.8 Lượng dữ liệu truyền qua mạng đối với thuật toán LAUC không sử dụng FDL 5.3.5.2 Thuật toán LAUC có sử dụng FDL Hình 5.9 Lượng dữ liệu truyền qua mạng đối với thuật toán LAUC có sử dụng FDL Qua 2 đồ thị biểu diễn kết quả lượng dữ liệu truyền qua mạng khi sử dụng thuật toán LAUC có và không có sử dụng bộ đệm FDL ta thấy việc sử dụng bộ đệm đã làm giảm khả năng mất burst đáng kể, giúp cải thiện khả năng truyền dữ liệu qua mạng rất lớn. Dù gây ra sự tốn kém nhất định nhưng việc sử dụng bộ đệm rất hiệu quả trong mạng OBS vì giúp giảm khả năng mất burst rất cao. 5.4. Mô phỏng ảnh hưởng của quá trình thiết lập burst trong mạng OBS (Burst Asembly) 5.4.1. Ảnh hưởng của thiết lập burst đến độ trễ trong mạng OBS Trong mạng OBS các thông số mạng cần chọn một cách hợp lý và các giao thức mạng cần chọn một cách hợp lý sao cho tôt nhất về mặt mất mát và độ trễ. Hình 5.10 Độ trễ end-to-end trung bình so với kích thước burst Như hình 5.10 ta thấy kích thước burst tăng lên thì độ trễ end-to end cũng tăng lên theo. Điều này là do kích thước burst tăng lên thì cần thời gian chờ để cho số lượng gói đến đủ để tạo thành một burst. Độ trễ end-to-end ảnh hưởng rất lớn đến các dịch yêu cầu thời gian thực. Với một yêu cầu về độ trễ trung bình thì ta có được giới hạn trên của kích thước burst. Khi có các yêu cầu về dịch vụ và các thông số mạng cho trước ta có thể tìm ra kích thước tối ưu của burst dữ liệu. 5.4.2. Bài toán mô phỏng quá trình thiết lập burst Việc mô phỏng nhằm tìm được một giá trị hay một dải giá trị về kích thước burst cho xác suất mất gói nhỏ nhất trong một mạng OBS với một topo và các thông số mạng liên quan được giới hạn trước. Các thông số giới hạn trong bài toán mô phỏng: Mô phỏng mạng NSFNET 14 node, khoảng cách ghi trên hình tính bằng km. Các node mạng đều là các node kết hợp Liên kết là song hướng, mỗi hướng có hai kênh điều khiển và hai kênh dữ liệu. Các gói đến có kích thước cố định là 1250 bytes Tốc độ truyền dẫn trên mỗi kênh truyền là 10Gb/s Thời gian chuyển mạch là 10 us Thời gian xử lý gói điều khiển là 2.5 us Lưu lượng được phân bố đồng nhất giữa tất cả các cặp node ngõ vào Định tuyến dựa vào đường đi ngắn nhất giữa các cặp node Thiết lập burst dựa vào giới hạn tối đa về kích thước burst Kích thước gói điều khiển là cố định và bằng 64 bytes Giải thuật lập lịch kênh truyền là LAUCVF Trong mô phỏng so sánh các xác suất mất gói với các mức ngưỡng khác nhau trong khi mạng có và không có phân đoạn burst trong giải quyết xung đột. Mô phỏng bắt đầu với việc xem xét trong mạng chỉ có một lớp dịch vụ (mức ưu tiên) và sau đó là hai lớp dịch vụ.Ta mô phỏng trường hợp: Một mức ngưỡng và có hai ưu tiên. 5.4.3. Sơ đồ thuật toán Start Burstsize=50 Seed = 12345 excute Seed<=102345 burstsize<= 1200 Sai Process and excute Return Seed=Seed+10000 burstsize=burstsize + 50 Seed = 12345 đúng đúng Hình 5.11. Lưu đồ thuật toán mô phỏng Giải thích lưu đồ thuật toán: Burstsize là kích thước burst được tính bằng số lượng gói tin trong một burst dữ liệu. Seed được sử dụng để tạo ra một con số ngẫu nhiên cho việc tạo lưu lượng Poisson. Với mỗi số Seed việc phát lưu lượng Poisson sẽ khác nhau. Đầu tiên chương trình sẽ gán các thông số ban đầu: burstsize = 50, seed = 12345. Ta sẽ có kết quả về xác suất mất gói ứng với kích thước burst và seed đó. Sau đó seed sẽ được tăng lên 10000 và chạy lần thứ hai, chương trình cứ tiếp tục như vậy cho đến khi seed đạt giá trị 102345. Sau đó ta lấy giá trị trung bình của xác suất mất burst tức là ta đã có một điểm trên trên đồ thị ứng với kích thước burst là 50. Ta lần lượt tăng kích thước burst lên 50 cho đến khi đạt 1200 gói tin/burst. Như vậy ta được đồ thị mô tả về xác suất mất burst ứng với kích thước burst từ 50 đến 1200 gói tin/ burst. 5.4.4. Trường hợp một mức ngưỡng có hai mức ưu tiên Hình 5.12 Xác suất mất gói của từng mức dịch vụ đối với các kích thước burst khác nhau. Ta có hai mức ưu tiên là mức ưu tiên số 1 cao hơn và mức ưu tiên số 0 là mức ưu tiên nhỏ hơn. Theo hình ta có đối với lớp dịch vụ cao hơn thì kích thước burst tối ưu là từ 200 đến 700 còn đối với mức ưu tiên thấp hơn thì kich thước burst tối ưu là 550 đến 700. Lớp dịch vụ có mức ưu tiên cao hơn sẽ cho xác suất mất gói thấp hơn. 5.5 Kết luận chương Như vậy là trong chương này em đã tiến hành mô phỏng được các thuật toán lập lịch và nêu kết quả tối ưu quá trình thiết lập burst. Đối với việc mô phỏng các thuật toán lập lịch em đã lấy kết quả vẽ trên cùng một đồ thị lượng dữ liệu truyền qua mạng của các thuật toán sắp xếp kênh dữ liệu trong mạng OBS gồm FFUC, LAUC, LAUC_VF để thấy được ưu điểm của thuật toán LAUC_VF so với 2 thuật toán kia. Phần kết quả đối với thuật toán có sử dụng và không sử dụng FDL cũng được trình bày. Qua đó ta thấy được việc sử dụng FDL đã làm giảm lượng burst mất đi đáng kể, từ đó làm tăng lượng dữ liệu được truyền đi. Vậy thuật toán tối ưu là thuật toán LAUCVF kết hợp với các đường trễ quang FDL sẽ cho kết quả tốt nhất. Từ kết quả mô phỏng của bài toán tối ưu trong quá trình thiết lập burst cho thấy tồn tại một kích thước burst cho xác suất mất burst là nhỏ nhất. Còn kích thước burst là bao nhiêu thì tùy thuộc vào topo mạng và các thông kèm theo. Trong đồ án em chỉ xét trường hợp các gói đến có kích thước cố định nên kích thước burst cũng được tính bằng số lượng gói của nó. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ĐỀ TÀI Trong hoàn cảnh các dịch vụ mạng đang phát triển mạnh mẽ với nhiều loại hình phong phú, đa dạng không chỉ dừng lại ở các dịch vụ tốc độ cố định như thoại hay truyền hình mà còn phục vụ nhiều cho truyền dữ liệu với tốc độ thay đổi. Vì vậy đặt ra yêu cầu phải có một công nghệ đáp ứng được tính chất đột biến của lưu lượng trong mạng. Và chuyển mạch chùm quang OBS là sự lựa chọn ưu việt nhất khi các công nghệ hiện đại đáp ứng cho chuyển mạch gói quang OPS như bộ đệm quang hay logic quang vẫn chưa thực hiện được. Dù không có nhiều ưu điểm nổi bật như OPS nhưng OBS cũng có thể truyền được một lượng dữ liệu với tốc độ cao và là một công nghệ hứa hẹn của mạng đường trục thế hệ sau. Mục đích của đồ án là giới thiệu tổng quát về chuyển mạch chùm quang, trong đó tìm hiểu sâu hơn và tiến hành mô phỏng các giải thuật xếp lịch trong mạng OBS cũng như tìm ra kích thước burst tối ưu để giảm thiểu tỉ lệ mất burst. Qua kết quả mô phỏng 2 vấn đề trên có thể kết luận rằng thuật toán tối ưu cho việc sắp xếp kênh dữ liệu là LAUC_VF kết hợp với việc sử dụng bộ đệm FDL vì cho lượng dữ liệu truyền qua mạng cao nhất so với các thuật toán còn lại. Đồng thời ta thấy được đối với topo mạng trong phần mô phỏng trên thì kích thước burst nằm trong khoảng 350-750 gói cho xác suất mất burst nhỏ nhất đối với trường hợp một mức ngưỡng và không có mức ưu tiên. Còn trường hợp một mức ngưỡng và có 2 mức ưu tiên thì số gói 550-750 đối với mức ưu tiên số 0 và số gói 200-700 đối với mức ưu tiên số 1 trong một burst là tối ưu. Như vậy đối với mỗi mô hình mạng cụ thể luôn tồn tại một dải kích thước burst xác định cho xác suất mất burst nhỏ nhất. Hướng phát triển của đề tài là xây dựng một mô hình mạng phức tạp hơn với việc tăng số lượng node, số lượng các bộ scheduler. Từ đó tiến hành mô phỏng với nhiều thuật toán khác, kết hợp 2 phương thức sắp xếp burst dựa trên mức ngưỡng (chiều dài burst) và bộ định thời (thời gian sắp xếp) để nâng cao chất lượng cho mạng OBS. TÀI LIỆU THAM KHẢO [1] Banks, J., Carson, J., Nelson, B., Nicol, D., (2001) Discrete-Event System Simulation, Third Edition, New Jersey: Prentice-Hall [2] Battestilli, T., and Perros, H., (2003), An Introduction to optical burst switching IEEE Communications Magazine, vol .41, no .8, pp .S10-S15 [3] Biao Chen, Vinod M. Vokkarane, Jason P.Ju, “Absolute QoS Differentiation in Optical Burst Switched Network”, IEEE, 2004 [4] Chen, Y.,Qiao, c and Yu ,X., (2004), Optical burst switching: a new area in optical networking research, IEEE Network, vol .18, pp.16-23 [5] Chunming Qiao, “Optical Burst Switching OBS – A new paradigm for a Optical Internet”, IEEE [6] Fall K and Varadhan K., (2005), The ns Manual, UC Berkeley, LBNL, USC/ISI, and Xerox PARC, Jan., [7] Gauger, C.M. (2003), Trends in Optical Burrst Switching, Proceedings of SPIE ITCOM 2003, Orlando [8] Hai Le Vu and Moshe, “Blocking Probability for Priority Classes in Optical Burst Switching Network”, IEEE [9] Jinhui Xu, Qiao, Jikai Li and Guang Xu, “Efficient Channel Scheduling Algorithms in Optical Burst Switched Network”, IEEE, 2003 [10] Martin Nord, “Optical switching technology for optical burst and packet switch”, 2002 [11] M. Klinkowski ,“Performance Analysis of Isolated Adaptice Routing in OBS network”, Advanced Broadband communication Center, 2005. PHỤ LỤC Mã nguồn các giải thuật xếp lịch #Các thông số ban đầu #10CNs in ring; 10 attached ENs #20 Gbit/s channels StatCollector set debug_ 0 Classifier/BaseClassifier/EdgeClassifier set type_ 0 Classifier/BaseClassifier/CoreClassifier set type_ 1 #Thời gian xử lý gói tin điều khiển tại một node là 1us source ../lib/ns-obs-lib.tcl source ../lib/ns-obs-defaults.tcl source ../lib/ns-optic-link.tcl set ns [new Simulator] set nf [open basic01.nam w] set sc [new StatCollector] set tf [open trace01.tr w] set ndf [open ndtrace01.tr w] set old_data 0 # dump all the traces out to the nam file $ns namtrace-all $nf $ns trace-all $tf $ns nodetrace-all $ndf #====================================================================# # các thông số bất biến trong mạng BurstManager offsettime 0.00001 #kích thước burst tối đa BurstManager maxburstsize 60000 #thời gian thiết lập burst BurstManager bursttimeout 0.0003 Classifier/BaseClassifier/CoreClassifier set bhpProcTime 0.000001 Classifier/BaseClassifier/EdgeClassifier set bhpProcTime 0.0000015 #giả sử có 1 FDL trên mỗi kênh bước sóng đầu ra Classifier/BaseClassifier set nfdl 10 Classifier/BaseClassifier set fdldelay 0.0001 Classifier/BaseClassifier set option 0 Classifier/BaseClassifier set maxfdls 8 Classifier/BaseClassifier set ebufoption 1 #this is a fixed delay line present at the ingress of every node OBSFiberDelayLink set FDLdelay 0.0001 # total number of edge nodes set edge_count 10 # total number of core routers set core_count 10 # total bandwidth/channel (1mb = 1000000) set bwpc 20000000000 #set bwpc # delay in milliseconds set delay 0.02ms # tổng số kênh bước sóng trên 1 liên kết set maxch 4 # số kênh điều khiển set ncc 1 # số kênh dữ liệu set ndc 3 #====================================================================# # các quá trình hỗ trợ # finish procedure proc finish {} { global ns nf sc tf ndf old_data $ns flush-trace $ns flush-nodetrace close $nf close $tf close $ndf $sc display-sim-list #Execute NAM on the trace file #exec nam basic01.nam & exec awk { { if ( $1=="r") { old_data = old_data + $5 } print $2, old_data*1.0 } } ndtrace01.tr > ffuc.data exec xgraph ffuc.data & puts "Simulation complete"; exit 0 } #print $2, old_data*8.0/$2/10000000000 #tạo ra topo node biên-node lõi-node biên Simulator instproc create_topology { } { $self instvar Node_ global E C global edge_count core_count global bwpc maxch ncc ndc delay set i 0 # thiết lập node biên while { $i < $edge_count } { set E($i) [$self create-edge-node $edge_count] set nid [$E($i) id] set string1 "E($i) node id: $nid" puts $string1 incr i } set i 0 # thiết lập node lõi while { $i < $core_count } { set C($i) [$self create-core-node $core_count] set nid [$C($i) id] set string1 "C($i) node id: $nid" puts $string1 incr i } $self createDuplexFiberLink $E(0) $C(0) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $E(1) $C(1) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $E(2) $C(2) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $E(3) $C(3) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $E(4) $C(4) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $E(5) $C(5) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $E(6) $C(6) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $E(7) $C(7) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $E(8) $C(8) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $E(9) $C(9) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $C(0) $C(1) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $C(1) $C(2) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $C(2) $C(3) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $C(3) $C(4) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $C(4) $C(5) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $C(5) $C(6) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $C(6) $C(0) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $C(7) $C(0) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $C(8) $C(0) $bwpc $delay $ncc $ndc $maxch $self createDuplexFiberLink $C(9) $C(0) $bwpc $delay $ncc $ndc $maxch $self build-routing-table } #create a self-similar traffic-stream over a UDP agent Simulator instproc create_selfsim_connection { selfsim udp null src dest start0 stop0 } { upvar 1 $udp udpr upvar 1 $selfsim selfsimr upvar 1 $null nullr upvar 1 $src srcr upvar 1 $dest destr set udpr [ new Agent/UDP] $self attach-agent $srcr $udpr set selfsimr [ new Application/Traffic/SelfSimilar ] $selfsimr set starttime $start0 $selfsimr set stoptime $stop0 $selfsimr attach-agent $udpr set nullr [ new Agent/Null ] $self attach-agent $destr $nullr $self connect $udpr $nullr $self at $start0 "$selfsimr start" $self at $stop0 "$selfsimr stop" puts "traffic stream between $src = $srcr and $dest = $destr created" } $ns create_topology Agent/UDP set packetSize_ 1500 Application/Traffic/SelfSimilar set batchsize 4500 Application/Traffic/SelfSimilar set sb 0 Application/Traffic/SelfSimilar set Hb -0.5 Application/Traffic/SelfSimilar set rate 5000.0 Application/Traffic/SelfSimilar set std_dev_inter_batch_time 1.0e-5 Application/Traffic/SelfSimilar set Ht 0.5 #add traffic stream between every pair of edge nodes in both directions set i 0 while {$i < $edge_count} { set j 0 while {$j < $edge_count} { if {$i != $j} { $ns create_selfsim_connection selfsim($i:$j) udp($i:$j) null($i:$j) E($i) E($j) 1.0 1.1 } incr j } incr i } $ns at 5.1 "finish" $ns run Mã nguồn thiết lập burst set number [lindex $argv 0] set opt(seed) [lindex $argv 1] # source for simulation source /home/ext/ns-allinone-2.28/ns-2.28/obs4ns-3.4/tcl/lib/ns-obs-lib.tcl source /home/ext/ns-allinone-2.28/ns-2.28/obs4ns-3.4/tcl/lib/ns-obs-node.tcl source /home/ext/ns-allinone-2.28/ns-2.28/obs4ns-3.4/tcl/lib/ns-obs-link.tcl source /home/ext/ns-allinone-2.28/ns-2.28/obs4ns-3.4/tcl/lib/ns-obs-stats.tcl source /home/ext/ns-allinone-2.28/ns-2.28/obs4ns-3.4/tcl/lib/ns-obs-defaults.tcl set ns [new Simulator] global defaultRNG $defaultRNG seed $opt(seed) Connector/ObsLink dc_bandwidth 10Gb Connector/ObsLink cc_bandwidth 10Gb Agent/Burstifier set max_db_size_ [expr 1250*$number] Agent/Burstifier set bhp_size_ 64 Agent/Burstifier set timeout_ 2000ms Agent/OXC switch_time 10us Agent/SCU max_bhp_proc_time 2.5us Agent/Burstifier set max_packets_ 2000 [Agent/SCU set bhp_proc_time_] set max_ [Agent/SCU max_bhp_proc_time] Agent/Burstifier set max_segmentations_ 10 Agent/Burstifier set min_segmentable_size_ 1250 Agent/Burstifier set segmentation_ true Agent/SCU max_segmentations 10 Agent/SCU min_segmentable_size 1250 Agent/SCU set segmentation_ 10 Agent/SCU set deflection_ 0 set edge_count 14 set core_count 14 set ndc 1 set ncc 1 set n_app 364 set n_links 21 set stype LAUCVF set load 0.5 # # set up the hybrid nodes set i 1 while { $i <= $core_count } { set c($i) [$ns ObsHybridNode $ncc $ndc ChannelScheduler/$stype 2] incr i } #creat NSFNET in real distances $ns duplex-obs-link $c(1) $c(2) $ncc $ndc 1100 ChannelScheduler/$stype $ns duplex-obs-link $c(1) $c(3) $ncc $ndc 1600 ChannelScheduler/$stype $ns duplex-obs-link $c(1) $c(8) $ncc $ndc 2800 ChannelScheduler/$stype $ns duplex-obs-link $c(2) $c(3) $ncc $ndc 600 ChannelScheduler/$stype $ns duplex-obs-link $c(2) $c(4) $ncc $ndc 1000 ChannelScheduler/$stype $ns duplex-obs-link $c(3) $c(6) $ncc $ndc 2000 ChannelScheduler/$stype $ns duplex-obs-link $c(4) $c(5) $ncc $ndc 600 ChannelScheduler/$stype $ns duplex-obs-link $c(4) $c(11) $ncc $ndc 2400 ChannelScheduler/$stype $ns duplex-obs-link $c(5) $c(6) $ncc $ndc 1100 ChannelScheduler/$stype $ns duplex-obs-link $c(5) $c(7) $ncc $ndc 800 ChannelScheduler/$stype $ns duplex-obs-link $c(6) $c(10) $ncc $ndc 1200 ChannelScheduler/$stype $ns duplex-obs-link $c(6) $c(13) $ncc $ndc 2000 ChannelScheduler/$stype $ns duplex-obs-link $c(7) $c(8) $ncc $ndc 700 ChannelScheduler/$stype $ns duplex-obs-link $c(8) $c(9) $ncc $ndc 700 ChannelScheduler/$stype $ns duplex-obs-link $c(9) $c(10) $ncc $ndc 900 ChannelScheduler/$stype $ns duplex-obs-link $c(9) $c(12) $ncc $ndc 500 ChannelScheduler/$stype $ns duplex-obs-link $c(9) $c(14) $ncc $ndc 500 ChannelScheduler/$stype $ns duplex-obs-link $c(11) $c(12) $ncc $ndc 800 ChannelScheduler/$stype $ns duplex-obs-link $c(11) $c(14) $ncc $ndc 800 ChannelScheduler/$stype $ns duplex-obs-link $c(12) $c(13) $ncc $ndc 300 ChannelScheduler/$stype $ns duplex-obs-link $c(13) $c(14) $ncc $ndc 300 ChannelScheduler/$stype $ns compile-obs set rate [expr $load*$ndc*[Connector/ObsLink dc_bandwidth]/$n_app] #k refer to class of service set k 0 while {$k < 2} { set i 1 while {$i <= $edge_count} { set j 1 while {$j <= $edge_count} { if {$i != $j} { #the rate of one class is a half set Poi($i$j$k) [new Application/Traffic/Poisson] $Poi($i$j$k) set rate_ $rate $Poi($i$j$k) set packetSize_ 1250 #creat udp to attach traffic set udp($i$j$k) [$c($i) set burstifier_([$c($j) id]:$k)] $Poi($i$j$k) attach-agent $udp($i$j$k) $udp($i$j$k) set-traffic-generator $Poi($i$j$k) $ns at 0.0 "$udp($i$j$k) start" } incr j } incr i } incr k } proc stop {} { global ns udp edge_count for { set k 0 } { $k <2} { set k [expr $k + 1]} { for { set i 1 } { $i <= $edge_count} { set i [expr $i + 1]} { for { set j 1 } { $j <= $edge_count} { set j [expr $j + 1]} { if { $i != $j } { $ns at-now "$udp($i$j$k) stop" } } } } set now [$ns now] $ns at [expr $now + 0.2] "finish" } # finish procedure proc finish {} { global ns sc0 sc1 defaultRNG number set ip_snd0 [expr [$sc0 get-counter-value DATA_SND]] set ip_rcv0 [expr [$sc0 get-counter-value DATA_RCV]] set ip_drop0 [expr $ip_snd0 - $ip_rcv0] set ip_p0 [expr 1.0*$ip_drop0/$ip_snd0] set file0 [open "results-0.txt" "a"] puts $file0 "$ip_p0" set ip_snd1 [expr [$sc1 get-counter-value DATA_SND]] set ip_rcv1 [expr [$sc1 get-counter-value DATA_RCV]] set ip_drop1 [expr $ip_snd1 - $ip_rcv1] set ip_p1 [expr 1.0*$ip_drop1/$ip_snd1] set file1 [open "results-1.txt" "a"] puts $file1 "$ip_p1" exit 0 } set sc0 [$ns get-global-stats-collector 0] $sc0 set-counter-convergence DATA_SND 1250000 Stats stop-command "stop" set sc1 [$ns get-global-stats-collector 1] $sc1 set-counter-convergence DATA_SND 1250000 Stats stop-command "stop" # enable stats collector $ns at [RouteLogic/ObsRoute transit_time] "$ns enable-stats" $ns run