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

Chia sẻ: Little Duck | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

121
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Để 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: TÌM ĐƯỜNG TRONG MÔ HÌNH HỆ THỐNG ROUTING TĨNH

MỘT SỐ VẤN ĐỀ LIÊN QUAN ĐẾN VIỆC TÌM ĐƯỜNG MÔ HÌNH HỆ THỐNG ROUTING TĨNH I. 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ề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. Mô hình hệ thống routing tĩnh giống như mô hình hệ thống mạng hàng, gồm mỗ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ủa khách hàng trong hệ thống được xác định trước theo thuật giải tìm đường routing 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ới tố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ủa message e Tốc độ đến tại hàng đợi của Slave i là l i =g i + (qji (trong đó e là số đường kết nối của mạng. j=1 Thờ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ủa mỗ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 đảm nhậ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ời gian đợ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 message theo đúng với giao thức mạng cũng là ngẫu nhiên được phân bố theo h àm Poisson .
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 gian truyền xác định trước, message này sẽ đến các máy trung gian k,....Các máy trung 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áy trung gian khi máy đó đang bận ( trạng thái BUSY ), ho ặc được gởi thẳng khi má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 khi message đó đã đế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 định trước. Vấn đề tìm đường trong hệ thống mạch chuyển gói phức tạp hơn trong hệ 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ường xuyê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ắng truyề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ắn nhất (một đường thông qua mạng với it1 node nhất ) thông qua mạng. Tiêu chu ẩn chung cho đường ngắn nhất là đường giá trị nhỏ nhất không trong trường hợp đó, giá trị bao gồm cho tường đường, và đường thông qua mạng bao gồm tí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ố (a) ta có kỹ thuật tìm đường tập trung (centralized routing) hoặc phân tán (Dynamic routing).
Dựa vào yếu tố (b) ta có kỹ thuật tìm đường tĩnh (static routing) hoặc tìm đường động (dynamic routing). Cuối cùng, các kỹ thuật chọn đ ườngcùng loại , theo (a) và (b) lại có thể phân biệt bởi yếu tố (c). Tiêu chuẩn tối ưu đ ể chọn đường được xác định bởi người quả lý mạng hoặnc người thiết kế mạng, nó có thể là :  Độ trể trung bình của việc truyền gói tin.  Số lượng nút trung giangiữa nguồn và đích của gói tin.  Độ an toàn của việc truyền tin.  Cước phí truyền tin. … - Việc chọn tiêu chuẩn tối ưu, như vậy phù thuộc vào nhiiều bối cảnh mạng (topology, thông lu ợng, mục dđích sử dụng…). Các tiêu chuẩn có thể th ay đổi vì b ối cảnh về mạng nhưng cũng có thể thay đổi theo thời gian. Do vậy đưa ra các giải thuật giải quyết các bài toán tìm đường đi ngắn nhất. - Và hiệu quả của các giải thuật cũng khác nhau, có giải thuật cho biết kết qu ả chính xác sau thời gian tính toán khá lâu, có giải thuật cho kết quả gần đúng, nhưng ch ỉ tốn một thời gian ngắn. Do vậy tùy thuộc vào các giải thuật tương ứng (như các giải thuật chọn thoả mãn về thời gian tuy nhiên đường đi không hoàn toàn chính xác). Nhưng người sử dụng luôn luôn mong muốn tìm được giải thuật tìm đường nhanh nhất và chính xác. III. Kỹ thuật tìm đường tập trung (centralized) hoặc phân tán (distributed routing). Tìm đường tập trung: Được tập trung bởi sự tồn tại của một hoặc vài trung - tâm điều khiển mạng thực hiện việc chọn đường sau đó gửi các bản tìm đường tới tất cả các nút dọc theo con đường đã đ ược chọn. Trong trường hợp n ày thông tin tổng thể của mạng cần dùng cho việc tìm đường chỉ đ ược cất giữ tại trung tâm điều khiển mạng. Các nút mạng có thể không gửi bất kỳ thông tin nào về trạng thái của chúng tới trung tâm hoặc gửi theo định kỳ, hoặc gửi theo một sự kiện nào đó. - Tìm đ ường phân tán: Không tồn tại các trung tâm điều khiển, quyết định tìm đường được thực hiện tại mỗi nút của mạng. Điều này đ òi hỏi việc trao đổi thông tin giữa các nút, tuỳ theo mức độ thích nghi của giải thuât5 được sử dụng. - Tìm đường tĩnh: Có thể là tập trung hay phân tán nh ưng nó không đáp ứng với mọi sự thay đởi trên mạng. Trong trường hợp này, chọn đường được thực hiện mà không có sự trao đổi thông tin, khôn g đo lường và không cập nh ật thông tin. Tiêu chuẩn tối ưu để chọn đường và b ản thân con đư ờng được chọn một lần cho toàn cuộc, không hề có sự thay đổi giữa chúng. Các kỹ thuật tìm đ ường tĩnh rõ ràng là rất đ ơn giản, do vậy sử dụng rất rộng rãi, đaặc biệt trong các mạng tương đối ổi định it1 có thay đổi về topology và lưu thông trên mạng . - Tìm đường động: Thu hút sự quan tâm của các nhà thuyết kế mãng do khả năng thuyết kế đáp ứng đối với các trạng thái khác nhau của mạng, vì đây là yếu tố quan trọng, đặc biệt đối với các ứng dụng, thời gian thực trong đó
yêu cầu đầu tiên của người sử dụng là mạng phải có khả năng cung cấp được các con đ ường khác nhau để dự phòng sự cố và thích nghi nhanh chóng với các thay đổi trên mạng. Mức độ thích hợp của một kỹ thuật con đường được đặc trưng b ởi trao đổi thông tin chọn đường trên mạng  Tóm lại: Trong đề tài này em tìm hiểu các giải thuật tìm đường trong lý thuyết và thực tế đ ã áp dụng các kỹ thuật tìm đường đã nêu ở trên. Và khi tìm hiểu các giải thuật tìm đường ứng dụng trong lý thuyết và thực tế để hiểu rỏ hơn về cách áp dụng được hợp lý. IV. Bài toán tìm đư ờng đi ngắn nhất (SHORTEST PATH ROUTING) : Bài toán tìm đường đi ngắn nhất là tìm đượng đi trong một đồ thị có trọng số (chiều d ài) nối hai đỉnh x và y đã cho trước với đặc tính là tổng các trọng số của tất cả các cạnh là nhỏ nhất trong tất cả các đường đi từ đỉnh x đến đỉnh y. Nếu tất cả các trọng số đều bằng 1 thì bài toán này trở thành bài toán tìm đường đi có cạnh ít nhất nối hai đỉnh x và y. Trong trường hợp này ta có th ể áp dụng giải thuật Breadth-First Search, sẽ trình bày ph ần sau. Giải thuật n ày có thể áp dụng để giải quyết bài toán tìm đ ường trong trư ờng hợp này. Bắt đầu từ đỉnh x, ta sét tất cả các đường đi nối từ x với một cạnh, sau đó xét tất cả các đư ờng đi nối từ x với hai cạnh và cứ như thế cho đến khi nào đ ỉnh y đựơc gặp lần đầu tiên. Khi đó đường đi ngắn nhất từ đỉnh x đến đỉnh y đ ã đ ược xác định xong. Trong trường hợp tổng quát đường đ i từ đỉnh x đến đỉnh y có thể đi qua tất cả các đ ỉnh của đồ thị, vì thế ta thường xét b ài toán tìm đường đi ngắn nhất nối từ đỉnh x cho trước với tất cả các đỉnh khác trong đồ thị. Phần này sẽ trình bàycác giải thuật tìm đường đi ngắn nhất trên một đồ thị hữu hướng. Nguyên lý tối ưu là nếu tồn tại một đường đi ngắn nhất từ đỉnh I đến đỉnh j và đỉnh k nằm trên đường đi này, thì ta phải có các đường đi từ đỉnh I đến đỉnh k và đường đi từ đỉnh k tới đỉnh j là những đường đi ngắn nhất.  Giải pháp tuần tự : Thực hiện routing từng đỉnh một. Khi một đỉnh routing xong nó có thể trở thành vật cản cho các đỉnh chưa routing. Vì vậy, phương pháp này rất nhạy cảm với thứ tự routing các đỉnh. Thông thường, thứ tự routing cuả các đỉnh căn cứ vào mức độ quan trọng, số lượng đỉnh đường nối và lượng thông tin truyền đi.  Giải pháp song song: Thực hiện routing tất cả các đỉnh cùng một lúc. Nó loại bỏ đư ợc tính phụ thuộc thứ tự cuả giải pháp tuần tự nhưng lại có độ phức tạp tính toán quá lớn. Hiện nay chưa có một giải thuật có độ phức tạp cấp đa thức n ào đưa ra, ngay cả giải thuật cho các net có hai điểm. Hiện nay người ta đang xem xét giải pháp đồng thời dựa trên phương pháp integer programming.  Giải pháp động: Các đ ối tượng tại các đỉnh có thể chuyển động, m à ta thực hiện việc tìm đủi giữa các đối tượng. Ví dụ như có hai đối tượng A và B tại một thời điểm n ào đó hai đối tượng n ày ở tại hai đỉnh khác nhau, nhưng chúng chuyển động với
hai vận tốc khác nhau. Đến một lúc nào đó hai đối tư ợng này gặp nhau, thì đ ây chính là đ iểm dừng của giải pháp động. A. Lập trình song song 1. Mục đích: Mục đích của xử lý song song là thực hiện việc tính toán nhanh h ơn hay giải quyết vấn đề lớn như : điều khiển không lưu, dự báo thời tiết, hệ thống thời gian thực… Để giải quyết những vấn đ ề này người ta phải chia nhỏ vấn đề ra và sử dụng nhiều processor để tính toán song song. Có hai hệ thống đ ược ứng dụng để giải quyết vấn đề này. a) Máy tính song song: Máy này bao gồm một nhóm các processor cùng lo ại, được kết nối với nhau theo m ột mô h ình nào đó để cho phép chúng cùng hoạt động và trao đổi dữ liệu cho nhau. b) Hệ thống phân bố: Là h ệ thống gồm nhiều processor có thể có kiễu khác nhau và được phân bố trên một vùng địa lý rộng (mạng máy tính). 2. Đánh giá hiệu quả của giải thuật song song: Cách tính 1 : Lấy B là vấn đề cần tính toán, n là kích thước của b ài toán. Độ phức tạp của giải thuật tuần tự để giải quyết vấn đề là T*(n). với giả sử là không có giải thuật tuần tự n ào tốt hơn giải thuật này. Gọi A là thuật giải song song giải quyết p trong thời gian Tp(n) trên máy tính song song gồm p processor. Speedup có được nhờ sử dụng giải thuật song song A được xác định: Trong đó p là số processor có sẵn trong hệ thống. Ngoài ra, người ta còn đo hiệu suất của giải thuật song song A bằng độ hiệu quả Ep(n) Gọi T¥ (n) là th ời gian mà giải thuật không thể chạy nhanh hơn nữa với bất kỳ số p n ào. Vì Tp(n) ³ T¥ (n), do đó: Độ hiệu quả sẽ giảm nhanh khi p tăng vượt quá T1(n)/T¥ (n). •Cách tính 2 : Speedup của giải thuật song song chạy trên p processor là tỷ số giữa thời gian chạy của giải thuật song song trên một processor và thời gian chạy của giải thuật song song trên p processor. Định nghĩa n ày không chính xác lắm (misleading) vì giải thuật song song thường chưá những hoạt động để thực hiện việc song song. 3. Các vấn đề cần chú ý khi tìm đường: a) Sự phụ thuộc chương trình (program dependence) Có hai sự phụ thuộc : sự phụ thuộc dữ liệu và sự phụ thuộc điều khiển.  sự phụ thuộc dữ liệu: có 3 lo ại phụ thuộc dữ liệu: - Phụ thuộc dòng (flow dependence) Vấn đề này xãy ra khi một hoạt động làm thay đ ổi dữ liệu và dữ liệu đó đ ược dùng cho một hoạt động sau đó. Ví dụ: ta có các phát biểu
A=B+C (1) D=A*5 (2) E=A+6 (3) Thì phát biểu (2) và (3) sử dụng dữ liệu do phát biểu (1) tạo ra. •Antidependence Xãy ra khi m ột hoạt động sử dụng vị trí nhớ đư ợc nạp bởi một hoạt động sau đó. Ví dụ: cho các phát biểu A=B+C (1) C=B*5 (2) A=D-6 (3) Phát biểu (1) phải được thực hiện trước phát biểu (2) vì (1) sử dụng giá trị hiện tại của C. •Output dependence Xãy ra khi một hoạt động nạp một vị trí nhớ mà vị trí nhớ này cũng được nạp ở hoạt động sau. trong ví dụ trên, phát biểu (3) phải thực hiện sau phát biểu (1) nếu không A sẽ chứa dữ liệu sai. - Sự phụ thuộc điều khiển (control dependence) loại phụ thuộc này là do dòng điều khiển trong chương trình. Trong ví dụ sau, phát biểu 2 đ ược thực thi phụ thuộc vào kết quả kiểm tra điều kiện 1. If (x
Bài toán tìm đ ường đi ngắn nhất đã được nguyên cứu từ lâu. Mà ta biết đến là giải thuật tuần tự Dijkstra .Bài toán tìm đường đi ngắn nhất đối với mọi điểm theo Kerr tính toán có độ phức tạp không thể nhỏ hơn O(p3) ở đây p là số đỉnh. Ở đây, chúng ta giả rằng có một processor tại mỗi đỉnh và mọi processor là đồng bộ .Chúng ta cho một giải thuật phân bố m à có th ể tìm đường ngắn nhất giữa mọi cặp đỉnh với độ phức tạp O(d.p2) d là bậc cực đại trong tấc cả các đỉnh và p là số đỉnh. Giải thuật và đô phức tạp: Giả sử rằng có một processor tại mỗi đỉnh và mọi processor được đồng bộ .Trị số không âm c(e) được kết hợp với mỗi cạnh .Trị đường đi được định nghĩa tổng trị giá các cạnh trong path đó .Trị giá đường đi thấp nhất từ v đến w là giá trị cần tìm. Giả sử các đỉnh được đánh số từ 1 đến p .Có một cạnh từ đỉnh i tới đỉnh j trị giá của cạnh này đư ợc ký hiệu là c((i,j)) .Cho p processor thực thi đòng thời theo theo giải thuật sau ( có đồng bộ data ) . Ta th ấy rằng giải thuật trên tìm đường đi ngắn nhất đối với mọi cặp điểm và có độ phức tạp (d.p2) ở đây d là bậc cực đại của graph và p là số processor.