Download miễn phí Đồ án Chọn đường và ứng dụng trong thiết kế mạng WAN



Flooding là một thuật toán định đường tĩnh, trong đó mọi gói đưa vào
một nút được gửi tới tất cả các đường ra trừ đường nó đã tới. Flooding đã tạo
ra một số lượng lớn các bản sao. Do đó cần cómột công cụ để ngăn cản quá
trình tăng này. Một giới hạn nhưvậy là bộ đếm hop (hop counter), chứa trong
header của mỗi gói, và nó được giảm mỗi khi đi quamột node. Khi bộ đếm
hop có giá trị zero thì gói sẽbị huỷ. Bộ đếm hop phải được phải được khởi tạo
ban đầu với giá trị hop bằng với khoảng cách từ nguồn tới đích. Nếu không
biết độ dài đường đi này thì nó được tính với trường hợp xấu nhất, đó là tính
theo giá trị đường kính lớn nhất của mạng. Nhưvậy, trong Flooding tất cả các
đường đều được thử nên các bản sao đến được đích theo một đường đi ngắn
nhất.


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-13-do_an_chon_duong_va_ung_dung_trong_thiet_ke_mang_w.OvoIQ78QBX.swf /tai-lieu/de-tai-ung-dung-tren-liketly-54674/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

y đòi hỏi
phải có hai loại kỹ thuật thực hiện riêng cho từng loại. Việc thực hiện nhiệm
vụ thứ nhất chính là cách tính toán tìm đ−ờng dẫn mà ta hay gọi là thuật toán
tìm tuyến truyền. Các lý thuyết giải thuật để tìm tuyến truyền thì có rất nhiều
và rất đa dạng, nh−ng kỹ thuật chuyển mạch gói quan tâm tới hai thể loại
chính: chọn tuyến truyền phân nhánh (Bifurcated Routing) và chọn tuyến
truyền ngắn nhất (Shortest-Path Routing). Kĩ thuật thứ nhất còn có tên là chọn
tuyến nhiều đ−ờng dẫn gói (Multipath Routing), đ−ợc thiết kế sao cho nó có
thể tối thiểu hoá trễ trung bình của gói trên phạm vi toàn mạng. Kĩ thuật thứ
hai, chọn tuyến ngắn nhất, chủ yếu quan tâm tới trễ ng−ời sử dụng và nó chọn
ra đ−ờng dẫn có giá thành tối thiểu cho một cặp ng−ời sử dụng. Việc thực
hiện nhiệm vụ cơ bản thứ hai của việc chọn đ−ờng do các thuật toán thu nhận
và truyền thông tin chọn đ−ờng thực hiện. Mỗi giao thức chọn đ−ờng có
những ph−ơng pháp khác nhau để lấy đ−ợc thông tin chọn đ−ờng và truyền
thông tin chọn đ−ờng. Nếu dựa vào việc các thông tin chọn đ−ờng có th−ờng
xuyên đ−ợc cập nhật hay không thì ta có thể phân thành hai loại: Thuật toán
chọn đ−ờng thích nghi (Adaptive) và thuật toán chọn đ−ờng không thích nghi
(Nonadaptive). Các thuật toán không thích nghi thì không quyết định đ−ờng
truyền gói dựa trên cơ sở phép đo thông số truyền tải tức thời và topology của
mạng. Các đ−ờng dẫn từ một nút i tới một nút j nào đó đ−ợc tính toán tr−ớc và
nạp vào mạng khi mạng khởi hoạt (Network Booting).Vì thế loại hình này
đôi khi còn đ−ợc gọi là chọn tuyến tĩnh (Static Routing). Ng−ợc lại, các thuật
toán chọn đ−ờng thích nghi sẽ cho phép thay đổi tuyến truyền gói dựa vào các
thay đổi thông số truyền tải và cấu hình của mạng. Có ba nhóm thuật toán
loại này:
• Chọn tuyến tập trung (Centralized Routing) gồm các thuật toán tổng
thể sử dụng các thông tin thu thập đ−ợc từ toàn bộ mạng để đ−a ra các kết quả
tối −u.
• Chọn tuyến cách ly (Isolated Routing) có các thuật toán vận hành
trên từng trạm riêng biệt và dựa vào thông tin nó thu thập đ−ợc tại trạm này,
ví dụ nh− độ dài của hàng, . ..
• Chọn tuyến phân bố (Distributed Routing) là tổ hợp của cả hai hình
thức trên.
Thực chất, các thuật toán hiện nay đang đ−ợc sử dụng đều là các thuật
toán thích nghi, chúng cũng chính là các thuật toán chọn tuyến truyền ngắn
nhất đã trình bày ở trên. Sự đa dạng chỉ là do cách gọi khác nhau tạo nên.
Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN
Nguyễn xuân tr−ờng - đtth2 - k40 48
Trong phần sau, ta sẽ xét sơ l−ợc thuật toán phân nhánh (đa đ−ờng dẫn ), vì
nó ít đ−ợc sử dụng, phần còn lại chủ yếu tập trung vào các thuật toán chọn
tuyến ngắn nhất.
3.2 Thuật toán chọn tuyến phân nhánh
3.2.1 Thuật toán phân nhánh (Bifurcated Routing)
Muốn đảm bảo thông tin giữa một cặp ng−ời sử dụng, đôi khi mạng
không phải chỉ chọn ra một đ−ờng dẫn duy nhất để chuyển các gói từ nguốn
tới đích mà phải sử dụng nhiều đ−ờng để phân bớt l−ợng tải của từng đ−ờng
dây. Thí dụ hình 1.4 mô tả chi tiết vấn đề này. Tất cả các đ−ờng dây ghép nối
trong mạng hình 1.4 đều có dung l−ợng là 10 đơn vị (các đơn vị đo ở đây chỉ
là các thông số đánh giá t−ơng đối và không đ−ợc xác định chi tiết ) . Có một
đích (nút số 6 ) và hai nút nguồn (nút số 1 và nút số 2), nút 1 có l−ợng tải đ−a
đén là 5 đơn vị, nút 2 có l−ợng tải là L. Ta sẽ xét hai tr−ờng hợp cụ thể t−ơng
ứng với hai giá trị của L:
a ) Tr−ờng hợp với L = 5
Với l−ợng tải của tất cả các nút nh− trên,so với dung l−ợng đ−ờng dây
nối giữa nguồn và đích thì có thể xem là nhỏ, do vậy có thể chọn các tuyến
truyền gói theo đ−ờng bên trái (1 - 3 - 6) và bên phải (2 - 5 - 6) ứng với các
nút 1 và 2. Nếu ta chọn tuyến ở giữa, 1 - 4 - 6 cho nút 1 và 2 - 4 - 6 cho nút 2,
thì luồng thông tin trên đ−ờng nối (4,6) sẽ bằng với dung l−ợng của đ−ờng
nên trễ sẽ cao.
b ) Tr−ờng hợp L = 15
Khi tải áp đặt vào nút 2 tăng thêm 10 đơn vị nữa, tức là tải tổng thể là
15 đơn vị, nếu ta tiếp tục chọn theo một trong hai đ−ờng dẫn đã xét ở trên cho
nút 2 thì có thể dễ dàng nhận thấy là một phần thông tin ( 5 đơn vị ) đ−a tới
nút này sẽ bị từ chối do dung l−ợng đ−ờng truyền bị hạn chế. Mặt khác, nếu ta
chọn tuyến cho nút 1 theo nhánh bên trái (1 → 3 → 6), còn nút 2 theo nhánh
(2 → 5 → 6) và (2 → 4 → 6) thì l−ợng tải tới không v−ợt quá 75% dung
Thu
5 L
Hình 3.4: Ví dụ về yêu cầu thiết lập
thuật toán nhiều đ−ờng
Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN
Nguyễn xuân tr−ờng - đtth2 - k40 49
l−ợng của từng đ−ờng, trễ truyền gói tổng thể đ−ợc đảm bảo t−ơng đối nhỏ và
điều quan trọng là không một phần tải nào bị từ chối.
Để đảm bảo cho việc nâng cao hoạt tính của mạng, ph−ơng thức
chuyển mạch phân nhánh đã đ−ợc thiết lập, mặc dù nó không có ứng công cụ
thể nh−ng ng−ời ta vẫn phải dùng đến nó trong việc thiết kế cấu hình mạng
(Topological Design). Việc chọn ra đ−ờng dẫn trong mạng nhằm mục đích tối
thiểu hoá trễ trung bình trong toàn mạng thông qua việc đánh giá nguồn -
đích. Kỹ thuật này có thể sử dụng cho cả mạng dữ liệu đồ DG và cả mạng ảo
VC. Với mạng DG, khi các gói đén trạm chuyển mạch, các trạm sẽ chọn
tuyến cho từng gói riêng biệt, độc lập với các phép chọn cho các gói đến cùng
một đích tr−ớc đó. Với mạng VC, bất cứ khi nào VC đ−ợc thiết lập thì tuyến
cũng đồng thời đ−ợc chọn, song các VC khác nhau đ−ợc chọn tuyến độc lập
với nhau.
Đích Chọn 1 Chọn 2 Chọn 3
A A 0.63 I 0.2
1
H 0.1
6
B A 0.45 H 0.3
1
I 0.2
3
C A 0.34 I 0.3
3
H 0.3
3
D H 0.50 A 0.2
5
I 0.2
5
E A 0.40 I 0.4
0
H 0.2
0
F A 0.35 H 0.3
2
I 0.3
3
G H 0.47 A 0.3
0
K 0.2
3
H H 0.63 K 0.2
1
A 0.1
6
I I 0.65 A 0.2
2
H 0.1
3
J
K K 0.67 H 0.2
2
A 0.1
1
L K 0.42 H 0.4
2
A 0.1
6
Phép chọn tuyến phân nhánh đ−ợc thực hiện nh− sau: mỗi trạm chuyển
mạch có một bảng chọn tuyến ( Routing Table ) để tới tất cả các trạm khác,
A B C D
I J K L
Hình 3.5: Ví dụ minh hoạ ph−ơng thức chọn tuyến phân nhánh
( Bảng chọn tuyến cho nút J )
Đồ án tốt nghiệp Chọn đ−ờng vμ ứng dụng trong thiết kế mạng WAN
Nguyễn xuân tr−ờng - đtth2 - k40 50
trên đó mỗi hàng chỉ ra khả năng dẫn gói tới tới một trạm khác theo thứ tự là
tuyến tốt nhất, tốt thứ hai, thứ ba... theo đánh giá trọng số (Weight). Tr−ớc khi
chuyển gói đi, trạm tạo ra một số ngẫu nhiên và sử dụng nó để chọn tuyến
dựa trên việc so sánh nó với trọng số của bảng chọn tuyến. Các bảng này do
các vận hành viên của mạng tự thiết lập,nạp vào cho các trạm tr−ớc khi vận
hành mạng và giữ không đổi từ đó trở đi. Sau đây ta đ−a ra một ví dụ để miêu
tả việc chọn tuyến phân nhánh. Xét mạng hình 3.5, A, B, C, D, E, F, G, H, I,
J, K, L là các nút chuyển mạch của mạ...

---