TÌM ĐƯỜNG TRONG MÔ HÌNH HỆ THỐNG ROUTING TĨNH

Để xem xét một hệ thống mạng phục vụ cho việc tìm đường cho truyền message như thế nào. Ta xây dựng một mô hình mô phỏng cho mạng để nghiên cứu tính hiệu quả của mạng phục vụ việc truyền nhận các message như thế nào. Ở đây ta đánh giá thời gian delay trung bình của mỗi message trong hệ thống.
Nội dung trích xuất từ tài liệu:
TÌM ĐƯỜNG TRONG MÔ HÌNH HỆ THỐNG ROUTING TĨNHMỘT SỐ VẤN ĐỀ LIÊN QUAN ĐẾN VIỆC TÌM ĐƯỜNG MÔ HÌNH HỆ THỐNG ROUTING TĨNHI. GIỚI THIỆU :Để xem xét một hệ thống mạng phục vụ cho việc tìm đường cho truyềnmessage như thế nào. Ta xây dựng một mô hình mô phỏng cho mạng để nghiêncứu tính hiệu quả của mạng phục vụ việc truyền nhận các message như th ế n ào.Ở đ ây ta đánh giá thời gian delay trung bình của mỗi message trong hệ thống.Mô hình hệ thống routing tĩnh giống như mô hình hệ thống mạng hàng, gồmmỗi hàng đơn là M/M/1. Hệ thống này là một mạng h àng mơ, khách hàng từngoài h ệ thống có thể vào b ất kỳ Slave n ào trên mạng và rời khỏi hệ thống khiđược phục vụ xong. Khách hàng đi trên đường liên lạc của mạng. Đường đi củakhách hàng trong hệ thống được xác định trước theo thuật giải tìm đườngrouting tĩnh (xác định qij_xác suất mà khách hàng sau khi phục vụ ở Slave i vàđi đến nút j).Mỗi trung tâm xử lý i tương ứng với link i của mạng bao gồm một Slave vớitốc độ phục vụ (i và hàng ch ờ của các message cần gởi trên mạng(có giới hạn).Hàng được phục vụ theo cơ ch ế FIFO. Hàng đợi ở mỗi node là có giới hạn vìthường tài nguyên của mạng đều có giới hạn. Tốc độ đến của khách hàng(message) vào hệ thống do người đánh giá hệ thống nhập vào .II. CÁC THÔNG SỐ CỦA HỆ THỐNG :Tốc độ phục vụ tại Slave i là m i=tốc độ truyền của link i/chiều dài củamessage eTốc độ đến tại hàng đợi của Slave i là l i =g i + (qji (trong đó e là số đường kếtnối của mạng. j=1Thời gian đợi trung b ình của message là T = N/ g .trong đó: g là tốc độ đến của khách hàng vào hệ thống.N là số khách hàng trung bình trong hệ thống.Hệ thống này được mô phỏng để đánh giá thời gian chờ (delay) trung bình củamỗi message trong hàng đợi.Hệ thống mạng này có giải thuật tìm đ ường theo phương pháp routing tĩnh,giao thức truyền nhận đơn giản (tức khi gởi từ máy n ày đến máy khác bảo đảmnhận đúng).Hệ thống này được tiếp cận theo cơ chế sắp xếp sự kiện (có 2 sự kiện chính : sựkiện đến và đi của message).Trạng thái của hệ thống được biểu diễn bởi số message trong các h àng đ ợi vàsố trạng thái các Slave các máy đang chuẩn bị gởi message .Thời gian xảy ra sự kiện được chứa trong hàng FEL.Hệ thống này có bộ đếm thống kê chứa các biến : số message đợi, tổng thờigian đợi của các message .Thời điểm đến của các message, thời gian các Slave (máy) xây dựng messagetheo đúng với giao thức mạng cũng là ngẫu nhiên được phân bố theo h àmPoisson .Khi có một message bắt đầu đư ợc gởi từ máy i tới máy j, thì sau một thời giantruyền xác định trước, message này sẽ đến các máy trung gian k,....Các máytrung gian tiếp tục gởi message này đi cho đến khi tới đích (máy j). Do việc gởiđược tiến h ành như thế nên message được lưu lại trong h àng đợi của mỗi máytrung gian khi máy đó đang bận ( trạng thái BUSY ), ho ặc được gởi thẳng khimáy đó đang rãnh ( trạng thái IDLE).Hàng đợi được quản lý theo cơ chế FIFO.Message (khách hàng) vào hệ thống tại nút bất kì và ra khỏi hệ thống khimessage đó đã đến đích cần gởi đến.Điều kiện để kết thúc mô phỏng là thời gian mô phỏng đạt đến thời gian địnhtrước. Vấn đề tìm đường trong hệ thống mạch chuyển gói phức tạp hơn tronghệ thống chuyển mạch điện tử.- Chức năng của mạch chuyển gói là nhận những gói từ trạm nguồn và cung cấp nó đến ngư ời nhận. Để hoàn thành việc đó một con đường hay một routing thông qua mạng được chọn, thông thường khả năng cho phep nhiều hơn. Điều đó có nghĩa là con đường đ ược chọn phải mạnh. Đảm bảo một só yêu cầu cần thiết trong chức năng đường truyền như thoả mản các tính chất sau:  Correctrer and Simplicity ( đúng và đơn giản). Đảm bảo các packet phảiđến đư ợc nơi nhận và thuật toán phải dể hiện thực.  Robustrer (Linh động). Có khả năng hoạt động ngay sau khi thay đổi vềhệ thống. Thay đổi: Topology. Traffic.Cũng như những sự cố bất thư ờng xãy ra trong một mạng máy tính thườngxuyên. Công bằng và tối ưu: Các thuật toán phải đảm bảo công bằng và cố gắngtruyền các packet tới nơi nhận nhanh nhất.- Sự chọn đường thường dựa vào tiêu chuẩn đơn giản là chọn đư ờng đi ngắnnhất (một đường thông qua mạng với it1 node nhất ) thông qua mạng. Tiêuchu ẩn chung cho đường ngắn nhất là đường giá trị nhỏ nhất không trong trườnghợp đó, giá trị bao gồm cho tường đường, và đường thông qua mạng bao gồmtích lũy giá trị bé nhất.- Để giải quyết các yêu cầu trên người ta đưa ra các giải thuật tìm đường đi ngắn nhất theo từng trường hợp khác nhau, mà em đi tìm hiểu cũng như đi phân tích các giải thuật đó.- Do đó có nhiều kỹ thật tìm đ ường khác nhau. Sự phân biệt giữa chúng chủ yếu căn cứ vào các yếu tố liên quan đến hai chức năng trên, đó là:  Sự phân tán của các chức năng trên các nút của các mạng. (a)  Sự thích nghi của trạng thái hiện hành của mạng. (b)  Các tiêu chuẩn tối ưu để chọn đường. (c)Dựa vào yếu tố ...