Luận văn: Các cơ chế định tuyến QoS và thuật toán mở đường ngắn nhất đầu tiên (OSPF) mở rộng : Luận văn ThS. Công nghệ điện tử - viễn thông: 60 52 70
Nhà xuất bản: ĐHCN
Ngày: 2011
Chủ đề: Kỹ thuật điện tử
Thuật toán
Cơ chế định tuyến
Kỹ thuật truyền thông
Miêu tả: 77 tr. + CD-ROM
Luận văn ThS. Kỹ thuật điện tử -- Trường Đại học Công nghệ . Đại học Quốc gia Hà Nội, 2011
Giới thiệu các khái niệm, các vấn đề liên quan cần nghiên cứu về định tuyến đảm bảo QoS và đặt vấn đề cho các mở rộng sang OSPF. Trình bày về định tuyến QoS trong mạng phân cấp và các cơ chế định tuyến đảm bảo QoS. Mở rộng của OSPF cho định tuyến
MỤC LỤC
MỞ ĐẦU ........................................................................................................... 1
CHƢƠNG 1 - TỔNG QUAN VỀ ĐỊNH TUYẾN QoS ...................................... 3
1.1. Giới thiệu định tuyến dựa trên QoS .......................................................... 3
1.1.1. Định tuyến.......................................................................................... 3
1.1.2. Định tuyến dựa trên QoS .................................................................... 5
1.1.3. Mục đích của định tuyến dựa trên QoS............................................... 7
1.2. Các vấn đề cơ bản của định tuyến dựa trên QoS....................................... 8
1.2.1. Metric và sự tính toán đƣờng đi.......................................................... 8
1.2.2. Lan truyền và duy trì thông tin ........................................................... 9
1.2.3. Mô hình thông tin trạng thái không chính xác .................................. 10
1.2.4. Điều khiển của quản trị mạng........................................................... 11
1.2.5. Vấn đề thuật toán trong định tuyến dựa trên QoS. ............................ 11
1.2.6. Vấn đề động trong định tuyến dựa trên QoS..................................... 15
1.3. Kỹ thuật OSPF và vấn đề mở rộng OSPF cho định tuyến QoS ............... 17
1.3.1. Kỹ thuật OSPF ................................................................................. 17
1.3.2. Độ tin cậy trong định tuyến dựa trên QoS......................................... 21
1.3.3. Đặt vấn đề nghiên cứu thuật toán OSPF mở rộng ............................. 22
CHƢƠNG 2 – CƠ BẢN VỀ CÁC CƠ CHẾ ĐỊNH TUYẾN QoS [2] .............. 25
2.1. Định tuyến QoS nội miền ....................................................................... 25
2.1.1. Vấn đề thuật toán lựa chọn đƣờng đi ................................................ 26
2.1.2. Định tuyến đa đích ........................................................................... 31
2.1.3. Định tuyến liên kết riêng biệt ........................................................... 33
2.1.4. Phƣơng pháp định tuyến dựa trên dự đoán........................................ 34
2.2. Định tuyến QoS liên miền[14]................................................................ 36ii
2.2.1. Các mở rộng QoS và kỹ thuật lƣu lƣợng sử dụng BGP..................... 37
2.2.2. Các phƣơng pháp che phủ ................................................................ 37
2.2.3. Multihoming..................................................................................... 39
2.3. Bảng định tuyến ..................................................................................... 42
2.3.1. Cơ chế trao đổi thông tin để xây dựng bảng định tuyến .................... 44
2.3.2. Các chính sách cập nhật.................................................................... 44
2.3.3. Cơ chế chuyển tiếp ........................................................................... 46
2.3.4. Chuyển tiếp hai mức giới hạn........................................................... 49
CHƢƠNG 3 - OSPF MỞ RỘNG CHO ĐỊNH TUYẾN QoS........................... 51
3.1. Mở rộng đảm bảo chất lƣợng dịch vụ cho OSPF [7]- [12] ...................... 51
3.1.1. Các khả năng tùy chọn QoS.............................................................. 51
3.1.2. Mã hóa tài nguyên khi TOS mở rộng................................................ 52
3.1.3. Mã hóa băng thông ........................................................................... 53
3.1.4. Mã hóa trễ ........................................................................................ 55
3.2. Các cơ chế thực hiện mở rộng QoS cho OSPF........................................ 55
3.2.1. Các thuật toán và thông tin lựa chọn đƣờng dẫn ............................... 55
3.2.2. Thông báo thông tin trạng thái liên kết ............................................. 63
3.3. Khảo sát cơ chế chuyển tiếp trong định tuyến OSPF mở rộng cho QoS.. 66
3.3.1. Hiệu suất của các phiên bản không giới hạn ..................................... 68
3.3.2. Hiệu suất của các phiên bản giới hạn................................................ 72
KẾT LUẬN...................................................................................................... 75
TÀI LIỆU THAM KHẢO ................................................................................ 76
MỞ ĐẦU
Ngày nay, khi công nghệ viễn thông đang phát triển mạnh mẽ trên toàn
thế giới thì vấn đề QoS là mối quan tâm lớn nhất không chỉ của các nhà cung
cấp dịch vụ viễn thông mà của cả những khách hàng sử dụng dịch vụ. Nhằm
mục đích nâng cao chất lƣợng và hiệu quả của mạng thì một trong những giải
pháp đƣợc quan tâm là định tuyến đảm bảo chất lƣợng dịch vụ (định tuyến QoSQoSR). QoSR không những có vai trò làm tăng chất lƣợng dịch vụ mà còn có ý
nghĩa quan trọng trong việc giảm chi phí vận hành mạng, đem lại hiệu quả kinh
doanh và ý nghĩa kinh tế to lớn trên đà phát triển của mạng viễn thông.
Vấn đề định tuyến trên mạng Internet hiện nay tập trung chủ yếu vào việc
cung cấp kết nối và thƣờng chỉ hỗ trợ dịch vụ dữ liệu “cố gắng tối đa”, với các
giao thức định tuyến dùng phƣơng pháp định tuyến tìm đƣờng ngắn nhất OSPF,
việc định tuyến đƣợc tối ƣu dựa trên các số đo tĩnh nhƣ là số lƣợng các chặng và
các trọng số mang tính quản trị. Dịch vụ đƣợc cung cấp bởi những giao thức này
chỉ thích hợp cho các ứng dụng dữ liệu truyền thống mà không thích hợp cho
nhiều ứng dụng yêu cầu sự đảm bảo chặt chẽ về độ trễ và băng thông. Hơn nữa,
với sự phát triển bùng nổ của lƣu lƣợng Internet, việc duy trì định tuyến tìm
đƣờng ngắn nhất của Internet hiện thời dẫn đến sự phân bố mất cân đối của lƣu
lƣợng.
Các giao thức định tuyến hiện nay đƣợc sử dụng trong các mạng IP,
không có bất kỳ nhận thức nào về nguồn tài nguyên sẵn có và yêu cầu. Điều này
có nghĩa là luồng lƣu lƣợng thƣờng đƣợc định tuyến qua các tuyến đƣờng không
có khả năng hỗ trợ các yêu cầu của chúng, trong khi các tuyến đƣờng kế tiếp
nhau với đủ các nguồn tài nguyên có sẵn. Điều này có thể dẫn đến suy giảm
đáng kể về hiệu suất. Mục tiêu của định tuyến đảm bảo QoS là cung cấp các
thuật toán định tuyến có khả năng nhận biết đƣờng dẫn để đáp ứng số lƣợng tối
đa có thể có của các luồng lƣu lƣợng với các yêu cầu QoS. Theo đó, định tuyến
đảm bảo QoS trong bối cảnh của Internet ngày nay đã nhận đƣợc sự quan tâm
ngày càng lớn.
Xuất phát từ thực tế trên, đề tài nghiên cứu: “Các cơ chế định tuyến QoS
và thuật toán mở đƣờng ngắn nhất đầu tiên (OSPF) mở rộng” đƣợc lựa
chọn. Thay vì tìm hiểu các vấn đề chung khá rộng lớn của định tuyến QoS, ở
đây chỉ tập trung vào một vấn đề cụ thể, dựa trên một giao thức định tuyến hiện
có. Cụ thể là, mô tả một tập hợp các đề xuất bổ sung cho giao thức định tuyến
OSPF để hỗ trợ cho việc định tuyến đảm bảo chất lƣợng của dịch vụ (QoS)
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi2
trong IP. Tập trung vào các luồng lƣu lƣợng đơn điểm, chú trọng tới các metric
cần thiết để hỗ trợ QoS, các cơ chế thông báo liên kết kết hợp, thuật toán lựa
chọn đƣờng dẫn, cũng nhƣ các khía cạnh của việc thiết lập tuyến đƣờng đảm bảo
QoS. Mục tiêu là định rõ một cách tiếp cận, trong khi đạt đƣợc các mục tiêu cải
thiện hiệu suất cho các luồng lƣu lƣợng QoS, làm nhƣ vậy với các tác động ít
nhất có thể trên giao thức OSPF hiện có.
Nội dung chính của luận văn gồm ba chƣơng:
Chƣơng 1: Tổng quan về định tuyến đảm bảo QoS
Nội dung chính của chƣơng này là giới thiệu các khái niệm, các vấn đề
liên quan cần nghiên cứu về định tuyến đảm bảo QoS và đặt vấn đề cho các mở
rộng sang OSPF.
Chƣơng 2: Các cơ chế định tuyến QoS
Nội dung chính là trình bày về định tuyến QoS trong mạng phân cấp và
các cơ chế định tuyến đảm bảo QoS.
Chƣơng 3: OSPF mở rộng cho định tuyến đảm bảo chất lƣợng
Nội dung tập trung vào các mở rộng của OSPF cho định tuyến QoS.3
CHƢƠNG 1 - TỔNG QUAN VỀ ĐỊNH TUYẾN QoS
1.1. Giới thiệu định tuyến dựa trên QoS
1.1.1. Định tuyến
Định tuyến là sự lựa chọn đƣờng đi để truyền một đơn vị dữ liệu từ trạm
nguồn đến trạm đích trong một liên mạng theo tiêu chí nhất định. Chức năng
định tuyến đƣợc thực hiện ở tầng mạng, cho phép router đánh giá các đƣờng đi
sẵn có tới đích và chọn đƣờng đi thích hợp (Hình 1.1). Để đánh giá đƣờng đi,
định tuyến sử dụng các thông tin topo mạng, các thông tin này có thể do ngƣời
quản trị thiết lập hay đƣợc thu lƣợm thông qua các giao thức định tuyến.
Hình 1.1. Định tuyến
Tầng mạng hỗ trợ chuyển gói từ đầu cuối tới đầu cuối cố gắng tối đa
(best-effort) qua các mạng đƣợc kết nối với nhau, sử dụng bảng định tuyến để
gửi các gói từ mạng nguồn đến mạng đích. Sau khi đã quyết định sử dụng đƣờng
đi nào, router tiến hành việc chuyển gói. Nó lấy một gói nhận đƣợc ở giao diện
vào và chuyển tiếp gói này tới giao diện ra tƣơng ứng (giao diện thể hiện đƣờng
đi tốt nhất tới đích cho gói).
Mục tiêu cơ bản của các phƣơng pháp định tuyến là nhằm sử dụng tối đa
tài nguyên mạng, và tối thiểu hoá giá thành mạng. Để đạt đƣợc điều này kỹ thuật
định tuyến phải tối ƣu đƣợc các tham số mạng và ngƣời sử dụng nhƣ: xác suất
tắc nghẽn, băng thông, độ trễ, độ tin cậy, giá thành,v.v... Vì vậy, một kỹ thuật
định tuyến phải thực hiện tốt hai chức năng chính sau đây:
Quyết định chọn đƣờng theo những tiêu chuẩn tối ƣu nào đó.
Cập nhật thông tin định tuyến
tuỳ từng trường hợp vào kiến trúc, hạ tầng cơ sở mạng mà các kỹ thuật định tuyến
Chọn đƣờng?
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi4
khác nhau đƣợc áp dụng. Các tiêu chuẩn tối ƣu khi chọn đường dẫn từ trạm
nguồn tới trạm đích có thể phụ thuộc vào yêu cầu ngƣời sử dụng dịch vụ mạng.
Giữa mạng và ngƣời sử dụng có thể có các thoả thuận ràng buộc về chất lƣợng
dịch vụ cung cấp hay một số yêu cầu khác, điều đó có thể dẫn tới khả năng chọn
đƣờng của mạng chỉ là cận tối ƣu đối với một loại hình dịch vụ cụ thể, hay với
một số nhóm ngƣời sử dụng dịch vụ cụ thể. Chức năng cập nhật thông tin định
tuyến là chức năng quan trọng nhất mà các giao thức định tuyến phải thừa hành,
các giải pháp cập nhật thông tin định tuyến đƣa ra hiện nay tập trung vào giải
quyết bài toán cân đối lƣu lƣợng báo hiệu và định tuyến trên mạng với tính đầy
đủ và sự nhanh chóng của thông tin định tuyến.
Có nhiều cách để phân loại giao thức định tuyến, trong đó cách phân loại
phổ biến nhất là phân định tuyến thành định tuyến theo véc-tơ khoảng cách và
định tuyến theo trạng thái kết nối.
Định tuyến theo trạng thái kết nối: các nút mạng quảng bá thông tin định
tuyến tới tất cả các nút trong liên mạng. Tuy nhiên, mỗi router chỉ gửi một
phần bảng định tuyến (phần mô tả trạng thái kết nối của router) và xây
dựng một bức tranh về toàn bộ mạng trong bảng topo. Mỗi khi topo trạng
thái kết nối thay đổi, các router đầu tiên biết đƣợc sự thay đổi này sẽ gửi
một thông báo trạng thái kết nối LSA (Link State Advertisement) mới tới
các router khác hay tới một router chỉ định (nơi các router khác có thể sử
dụng để cập nhật). LSA này sẽ đƣợc tràn ngập (flooding) tới tất cả các
router trên liên mạng.
Định tuyến theo véc-tơ khoảng cách: là một thuật toán thích nghi nhằm
tính toán con đƣờng ngắn nhất giữa các cặp nút trong mạng, dựa trên
phƣơng pháp tập trung đƣợc biết đến nhƣ là thuật toán Bellman-Ford. Các
nút mạng thực hiện quá trình trao đổi thông tin trên cơ sở của địa chỉ đích,
nút kế tiếp và con đƣờng ngắn nhất tới đích.
Khi tính toán đƣờng đi ngắn nhất sử dụng định tuyến theo trạng thái kết
nối và định tuyến theo véc-tơ khoảng cách, thông tin trạng thái của mạng thể
hiện qua các số đo (Metric) thông qua giá (cost), các bộ định tuyến phải đƣợc
cập nhật giá trên tuyến kết nối. Khi có sự thay đổi topo mạng hay lƣu lƣợng,
các nút mạng phải khởi tạo và tính toán lại tuyến đƣờng đi ngắn nhất, tuỳ
theo giao thức đƣợc sử dụng trong mạng.
Các bảng định tuyến chứa thông tin đƣợc sử dụng bởi phần mềm chuyển
mạch để chọn tuyến tốt nhất. Các thuật toán phức tạp có thể chọn tuyến dựa trên5
nhiều metric bằng cách kết hợp chúng thành một metric phức hợp. Các metric
đƣợc sử dụng phổ biến gồm: chiều dài đƣờng đi, độ tin cậy, độ trễ, băng thông,
tải và giá truyền thông. Chúng ta có thể so sánh định tuyến véc-tơ khoảng cách
với định tuyến trạng thái kết nối theo một số tiêu chí nhƣ trong Bảng 1.1:
Bảng 1.1. So sánh định tuyến trạng thái kết nối và véc-tơ khoảng cách.
Véc-tơ khoảng cách Trạng thái kết nối
Nhận thức về topo mạng từ các
router kế cận.
Có đƣợc cái nhìn toàn cảnh về liên
mạng.
Cộng vào véc-tơ khoảng cách từ
router này tới router khác.
Tính toán đƣờng đi ngắn nhất tới tất cả
các router.
Cập nhật định kỳ, hội tụ chậm. Cập nhật ngay khi thay đổi, hội tụ nhanh.
Chuyển bản sao của bảng định
tuyến tới các router kế cận.
Chuyển cập nhật định tuyến trạng thái
kết nối tới tất cả các router.
Định tuyến véc-tơ khoảng cách lấy dữ liệu topo từ thông tin bảng định
tuyến của các router kế cận. Định tuyến trạng thái kết nối có đƣợc một cái
nhìn toàn cảnh về topo của liên mạng bằng cách tích luỹ tất cả các LSA cần
thiết.
Định tuyến véc-tơ khoảng cách xác định đƣờng đi tốt nhất bằng cách cộng
thêm vào giá trị metric mà nó nhận đƣợc khi thông tin định tuyến đƣợc gửi từ
router này tới router khác. Đối với định tuyến trạng thái kết nối, mỗi router làm
việc độc lập trong việc tính toán đƣờng đi ngắn nhất tới các mạng đích.
Trong hầu hết các giao thức định tuyến véc-tơ khoảng cách, cập nhật định
tuyến về thay đổi topo mạng đƣợc gửi định kỳ. Các cập nhật đƣợc gửi từ router
này tới router khác, dẫn đến mạng hội tụ chậm. Với các giao thức định tuyến
trạng thái kết nối, cập nhật đƣợc gửi ngay khi topo mạng thay đổi. Các gói thông
báo trạng thái kết nối LSA có kích thƣớc tƣơng đối nhỏ đƣợc chuyển tới tất cả
các router, do đó thời gian hội tụ sẽ nhanh hơn khi topo mạng thay đổi.
1.1.2. Định tuyến dựa trên QoS
Định tuyến dựa trên QoS là cơ chế định tuyến theo đó đƣờng đi cho các
luồng đƣợc xác định dựa trên một số hiểu biết về sự sẵn sàng của tài nguyên
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi6
trong mạng cũng nhƣ nhu cầu QoS của luồng [3]. Hay nói cách khác, đó là “một
giao thức định tuyến động có mở rộng tiêu chí chọn đƣờng của nó bao gồm các
tham số QoS nhƣ băng thông sẵn có, hiệu quả sử dụng đƣờng đầu cuối và kết
nối, mức tiêu thụ tài nguyên nút, trễ và trƣợt, biến động trễ”. Nói một cách ngắn
gọn là định tuyến động có tính đến QoS.
Hình 1.2 là ví dụ đơn giản về định tuyến dựa trên QoS. Giả sử có luồng
lƣu lƣợng từ nút A tới nút C yêu cầu băng thông 4Mbps, mặc dù đƣờng A-B-C
ngắn hơn, nhƣng nó sẽ không đƣợc chọn vì không có đủ băng thông. Thay vào
đó đƣờng A-D-E-C đƣợc chọn.
Hình 1.2. Ví dụ về phương pháp định tuyến dựa trên QoS
Bên cạnh đó, còn có hai khái niệm liên quan là định tuyến dựa trên
chính sách và định tuyến ràng buộc. Mối quan hệ giữa ba kiểu định tuyến
đƣợc thể hiện trong hình 1.3.
Hình 1.3. Mối quan hệ giữa ba kiểu định tuyến
Định tuyến ràng buộc
Định tuyến theo QoS Định tuyến theo
chính sách7
Định tuyến dựa trên chính sách là quyết định định tuyến không dựa
trên hiểu biết về topo mạng và các số đo mà dựa theo các chính sách quản
trị. Định tuyến theo chính sách thƣờng đƣợc cấu hình tĩnh.
Định tuyến ràng buộc là một quan niệm phát triển từ định tuyến dựa trên
QoS nhƣng có ý nghĩa rộng hơn. Nó tính đƣờng đi để thoả mãn một số ràng
buộc, bao gồm cả các ràng buộc về QoS (yêu cầu QoS và sự sẵn sàng của tài
nguyên) và các ràng buộc theo chính sách.
1.1.3. Mục đích của định tuyến dựa trên QoS
Các giao thức định tuyến Internet hiện nay đƣợc gọi là giao thức định
tuyến “cố gắng tối đa”. Các giao thức này chỉ sử dụng “đƣờng ngắn nhất” tới
đích, chúng thƣờng dùng các thuật toán tối ƣu với mục tiêu đơn, theo đó chỉ xem
xét một số đo (băng thông, số chặng, giá). Nhƣ vậy, toàn bộ lƣu lƣợng đƣợc
định tuyến vào “đƣờng ngắn nhất”, ngay cả khi tồn tại đƣờng cạnh tranh khác,
chúng không đƣợc sử dụng chừng nào chúng chƣa trở thành đƣờng ngắn nhất.
Điều này có thể dẫn tới tắc nghẽn của một vài kết nối, trong khi các kết nối khác
không đƣợc dùng hết.
Định tuyến “cố gắng tối đa” sẽ chuyển lƣu lƣợng từ một đƣờng tới đƣờng
“tốt hơn” mỗi khi nó tìm đƣợc. Việc này xảy ra ngay cả khi đƣờng đang dùng
đáp ứng đƣợc các yêu cầu dịch vụ của lƣu lƣợng. Kiểu chuyển đổi này là không
mong muốn vì nó dẫn tới sự dao động định tuyến, lƣu lƣợng sẽ bị định tuyến
qua lại giữa các đƣờng cạnh tranh. Thậm chí còn tồi tệ hơn vì kiểu dao động này
có thể làm tăng biến động trễ và trƣợt.
Định tuyến dựa trên QoS đƣợc đánh giá là giải quyết hay tránh các vấn đề đã
nêu trên. Các mục tiêu chính của định tuyến dựa trên QoS là:
Thứ nhất, là để đáp ứng các yêu cầu QoS của ngƣời sử dụng. Định tuyến
dựa trên QoS đƣợc giả thiết là để tìm một đƣờng từ nguồn đến đích để
thoả mãn các yêu cầu của ngƣời sử dụng về băng thông, trễ đầu cuối, …
Ngoài ra, việc này phải đƣợc thực hiện trong chế độ động chứ không phải
là cấu hình tĩnh. Trong trƣờng hợp có một vài tuyến khả thi sẵn có, tuyến
đƣợc lựa chọn có thể là cơ sở cho một vài chính sách ràng buộc. Ví dụ:
chúng ta có thể chọn tuyến ít chi phí nhất hay theo nhà cung cấp dịch vụ
chỉ định.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi8
Thứ hai, là để tối ƣu hoá mức độ sử dụng tài nguyên mạng. Đây là mục
đích theo quan điểm của nhà cung cấp dịch vụ. Tất cả các nhà cung cấp
muốn khai thác tối đa khả năng mạng hiện thời của họ, nhờ thế đạt lợi
nhuận cao nhất. Bên cạnh đó, đây cũng là yêu cầu xuất phát từ góc độ kỹ
thuật xây dựng mạng. Định tuyến dựa trên QoS đƣợc trông đợi để quản lý
lƣu lƣợng mạng một cách hiệu quả sao cho thông lƣợng qua mạng là lớn
nhất. Một lƣợc đồ thông thƣờng là luôn lựa chọn đƣờng ngắn nhất trong
số các đƣờng khả thi, vì đƣờng dài hơn có nghĩa là sử dụng tài nguyên
mạng nhiều hơn.
Thứ ba, khi mà mạng ở tình trạng tải lớn, khả năng thực thi của mạng
giảm, giống nhƣ xảy ra tắc nghẽn, định tuyến dựa trên QoS đƣợc mong
đợi là sẽ cho chất lƣợng tốt hơn (ví dụ: thông lƣợng tốt hơn) so với định
tuyến cố gắng tối đa, (định tuyến cố gắng tối đa có thể làm giảm thực thi
mạng một cách đột ngột).
1.2. Các vấn đề cơ bản của định tuyến dựa trên QoS
Định tuyến dựa trên QoS thì khó thiết kế và thực thi hơn nhiều so với định
tuyến cố gắng tối đa. Trong hầu hết các trƣờng hợp mục đích không phải là tìm giải
pháp tốt nhất, mà là tìm giải pháp với chi phí có thể chấp nhận đƣợc.
1.2.1. Metric và sự tính toán đƣờng đi
Có hai vấn đề cơ bản của phƣơng pháp định tuyến dựa trên QoS: Thứ
nhất, đo và thu thập thông tin trạng thái mạng nhƣ thế nào; Thứ hai, tính toán
các lộ trình dựa trên thông tin đã thu đƣợc nhƣ thế nào. Sự lựa chọn metric là rất
quan trọng theo nghĩa rằng: “các metric phải thể hiện các đặc tính mạng cơ bản
mà ta quan tâm”. Do đó các metric nhƣ băng thông sẵn có, trễ, biến động trễ, …
đƣợc sử dụng phổ biến; cũng nhƣ là các metric xác định kiểu bảo đảm QoS mà
mạng cung cấp. Không có phƣơng pháp hỗ trợ yêu cầu QoS nào mà không thể
biểu diễn bởi tổ hợp nào đó của các metric hiện hữu.
Bên cạnh đó cần xem xét sự phức tạp trong tính toán, nghĩa là việc tính
toán đƣờng đi dựa trên một metric hay tổ hợp các metric phải không quá phức
tạp. Tiếc rằng, định tuyến dựa trên QoS thƣờng đƣợc thực hiện với nhiều ràng
buộc và việc tính toán đƣờng dựa trên tổ hợp nhất định nào đó của các metric đã
đƣợc chứng minh là bài toán NP (No Polynomial) hoàn thiện. Rất nhiều thuật
toán đƣợc đề xuất để giải quyết vấn đề này. Một phƣơng pháp chung nhất đƣợc
Ở đây, ta chạy thuật toán BF tiêu chuẩn, đƣợc mô tả trong (3.1), có đƣợc
nhƣ một đầu ra một bảng định tuyến QoS với α nằm trong khoảng 0.5 1, là
một tham số chỉ ra “risk proneness - hiểm” của ngƣời ra quyết định (giá trị càng
thấp, „trạng thái nguy hiểm” càng cao). Thật vậy, cho HR là một tham số chỉ ra
bao nhiêu chặng ngƣời ra quyết định sẵn sàng đánh đổi lấy sự an toàn. Sau đó,
khi một yêu cầu kết nối phù hợp với giá trị b của băng thông, thực hiện nhƣ sau:
Từ bảng định tuyến, có đƣợc hmin là số chặng tối thiểu của một tuyến
đƣờng với băng thông nhỏ nhất là αb
Từ bảng định tuyến, có đƣợc hmax , số chặng tối đa của một tuyến đƣờng
an toàn, nghĩa là với băng thông nhỏ nhất là 2b
Nếu
hmin HR hmax : chọn tuyến đƣờng an toàn
Nếu khác: từ bảng, chọn tuyến đƣờng có băng thông lớn nhất trong số
những tuyến đƣờng có hmin HR chặng.
3.2.2.3. Chi tiết hóa phƣơng pháp (3)
Một vấn đề chính của phƣơng pháp đơn giản trên là tiềm ẩn khả năng các
tuyến đƣờng tốt không đƣợc để ý đến. Một ví dụ đơn giản, xem xét 2 đƣờng dẫn
giữa nguồn và đích: đƣờng dẫn thứ nhất có hai liên kết với 10 đơn vị băng
thông, đƣờng dẫn thứ hai có ba liên kết, hai trong số đó là 20 đơn vị băng thông
và liên kết còn lại với 10 đơn vị băng thông. Giả sử rằng, một yêu cầu kết nối
với 10 đơn vị băng thông đang đƣợc xử lý. Theo phƣơng pháp đơn giản, ta sẽ
không tạo một chú giải cho đƣờng dẫn thứ hai, khi nó cho băng thông tƣơng tự
nhƣ đƣờng dẫn đầu tiên nhƣng với số chặng nhiều hơn. Tuy nhiên, đƣờng dẫn
thứ hai có độ mạo hiểm ít hơn, do đó có thể sẽ là khôn ngoan hơn khi chọn nó.
Cách tiếp cận sau diễn giải vấn đề này.
Cho b1 b2 ... bK với K M là các giá trị băng thông khác nhau tƣơng ứng
với thông báo cuối cùng cho mỗi liên kết (nhƣ trƣớc, M dùng để chỉ số của các
liên kết). Các bƣớc sau đây đƣợc thực hiện cho mỗi bi , 1 i K :
Xóa các liên kết “cấm”, nghĩa là xóa những liên kết với băng thông nhỏ
hơn 0.5bi
Chỉ định “giá” 0 cho một liên kết “an toàn”, nghĩa là, liên kết với băng
thông ít nhất là 2bi , và 1 cho tất cả các liên kết khác, nghĩa là các liên kết
với băng thông thông báo trong phạm vi 0.5 ~ 2 b b i i .
Chạy thuật thoán BF, sử dụng “giá” trên nhƣ là metric.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi66
Kết quả là, nhận đƣợc một bảng cho từng giá trị băng thông (quan tâm) và
cho từng số các chặng h, với đƣờng dẫn có không nhiều hơn h chặng mà có số
các liên kết không an toàn nhỏ nhất (và số các liên kết an toàn lớn nhất) đối với
giá trị băng thông. Sau đó, khi có một kết nối phù hợp với yêu cầu băng thông là
b đơn vị, nghĩa là b(i1) b bi với 1 i K , ngƣời ra quyết định có thể xác định
các tùy chọn khác nhau cho sự trả giá giữa độ an toàn và số chặng cho giá trị
băng thông là bi , và chọn đƣờng dẫn tƣơng ứng theo cảm nhận của nó về sự cân
bằng giữa hai tiêu chuẩn đó.
Phƣơng pháp này là phức tạp về cả thời gian chạy và kích thƣớc bảng, là
M lần lớn hơn so với một thuật toán BF tiêu chuẩn. Phƣơng pháp sau đây nhằm
giải quyết các vấn đề của phƣơng pháp đơn giản (2), nhƣng không phức tạp nhƣ
trong (3).
3.2.2.4. Giảm sự phức tạp của phƣơng pháp (3)
Biểu thị bởi bmax là giá trị lớn nhất mà một băng thông kết nối có thể đạt
đƣợc. Khi các giá trị băng thông thông báo tăng lên theo cấp số nhân, ví dụ nhƣ
với cơ số bằng 2, thuật toán đƣa ra đoán hạn chế phạm vi đƣợc cho phép để
có thể đƣợc thông báo chuỗi tăng lên theo cấp số nhân của ngƣỡng, gọi là 1, 2,
4…. Ví dụ, về nguyên tắc một thông điệp thông báo trạng thái liên kết đƣợc ban
hành chỉ khi một ngƣỡng mới đƣợc vƣợt qua, và rồi thông điệp thông báo trạng
thái liên kết sẽ thông báo ngƣỡng gần nhất với giá trị băng thông hiện thời. Bằng
cách này, tỷ lệ giữa các giá trị băng thông thực tế và các giá trị băng thông thông
báo đƣợc giữ trong phạm vi 0.5…2. Tuy nhiên, số các giá trị thông báo khác
nhau, K, bây giờ trở thành 0(log(bmax )) nhỏ hơn là 0(M) nhƣ trong (3). Theo đó,
độ phức tạp về không gian và thời gian đƣợc giảm xuống 0(MH log(bmax )) và
0(NH log(bmax )) .
3.3. Khảo sát cơ chế chuyển tiếp trong định tuyến OSPF mở rộng cho QoS
Khi cần thông báo thông tin trạng thái dùng để các nút cập nhật bảng định
tuyến của chúng, cả trong OSPF tiêu chuẩn và trong OSPF mở rộng cho định
tuyến QoS nhƣ mô tả ở trên, ngƣời ta dùng phƣơng pháp lan tràn (flooding) để
đƣa thông báo tới tất cả các nút liên quan một cách nhanh chóng nhất. Chƣơng 2
đã trình bày một số cơ chế flooding nhằm giảm quá tải mạng do truyền bản tin
thăm dò dùng để cập nhật định tuyến. Kết quả của các đề xuất trƣớc đây là một
cơ chế chuyển tiếp hai mức.67
Động cơ thúc đẩy cho sự chuyển tiếp dựa trên bảng hai mức là để giảm
quá tải bản tin của flooding. Ví dụ đƣa ra trên hình dƣới đây giúp cho việc hiểu
chuyển tiếp dựa trên bảng 2 mức có thể giảm quá tải nhƣ thế nào. Cho v là nút
đƣợc quan tâm và u1,u2,....um là m hàng xóm của nó. Router v nhận một yêu cầu
kết nối cho một đích có hơn hai chặng. Nhu cầu băng thông là 5. Một trong
những hàng xóm u1,u2,....um là thích hợp. Trong bối cảnh nhƣ vậy, nếu chuyển
tiếp thăm dò dựa trên phƣơng pháp hai mức đƣợc sử dụng, thì thăm dò sẽ đƣợc
loại bỏ. Tuy nhiên, nếu một flooding đơn giản đƣợc sử dụng, thì router v có thể
gửi m bản sao thăm dò tới u1,u2,....um và các thăm dò sẽ bị loại bỏ cuối cùng tại
mỗi
u1,u2,....um . Nhƣ vậy, “lan tràn mù - blind flooding” sinh thêm quá tải. Ngoài
ra, trong chuyển tiếp dựa trên bảng hai mức, nếu đích đến trong vòng hai chặng
thì các thăm dò sẽ đƣợc hƣớng dẫn chỉ về phía đích. Mặt khác, nếu các thăm dò
đƣợc ngập tràn một cách “mù”, ngoại trừ đích, nhiều nút khác sẽ vẫn nhận thăm
dò. Để giảm quá tải, thông tin bổ sung về các hàng xóm mức hai phải đƣợc lƣu
giữ tại mỗi router. Việc duy trì thông tin này tạo thêm tải trong các hình thức
duy trì bảng. Cách tiếp cận hai mức sẽ là hợp lý, nếu quá tải tạo ra do việc duy
trì bảng là ít hơn nhiều so với việc lƣu trữ trong chuyển tiếp thăm dò. Việc lƣu
trữ trong chuyển tiếp thăm dò phụ thuộc vào tài nguyên sẵn có và topo mạng.
Trong luận văn này, đề cập đến chuyến tiếp dựa trên bảng hai mức nhƣ là
chuyển tiếp hai mức.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Nhà xuất bản: ĐHCN
Ngày: 2011
Chủ đề: Kỹ thuật điện tử
Thuật toán
Cơ chế định tuyến
Kỹ thuật truyền thông
Miêu tả: 77 tr. + CD-ROM
Luận văn ThS. Kỹ thuật điện tử -- Trường Đại học Công nghệ . Đại học Quốc gia Hà Nội, 2011
Giới thiệu các khái niệm, các vấn đề liên quan cần nghiên cứu về định tuyến đảm bảo QoS và đặt vấn đề cho các mở rộng sang OSPF. Trình bày về định tuyến QoS trong mạng phân cấp và các cơ chế định tuyến đảm bảo QoS. Mở rộng của OSPF cho định tuyến
MỤC LỤC
MỞ ĐẦU ........................................................................................................... 1
CHƢƠNG 1 - TỔNG QUAN VỀ ĐỊNH TUYẾN QoS ...................................... 3
1.1. Giới thiệu định tuyến dựa trên QoS .......................................................... 3
1.1.1. Định tuyến.......................................................................................... 3
1.1.2. Định tuyến dựa trên QoS .................................................................... 5
1.1.3. Mục đích của định tuyến dựa trên QoS............................................... 7
1.2. Các vấn đề cơ bản của định tuyến dựa trên QoS....................................... 8
1.2.1. Metric và sự tính toán đƣờng đi.......................................................... 8
1.2.2. Lan truyền và duy trì thông tin ........................................................... 9
1.2.3. Mô hình thông tin trạng thái không chính xác .................................. 10
1.2.4. Điều khiển của quản trị mạng........................................................... 11
1.2.5. Vấn đề thuật toán trong định tuyến dựa trên QoS. ............................ 11
1.2.6. Vấn đề động trong định tuyến dựa trên QoS..................................... 15
1.3. Kỹ thuật OSPF và vấn đề mở rộng OSPF cho định tuyến QoS ............... 17
1.3.1. Kỹ thuật OSPF ................................................................................. 17
1.3.2. Độ tin cậy trong định tuyến dựa trên QoS......................................... 21
1.3.3. Đặt vấn đề nghiên cứu thuật toán OSPF mở rộng ............................. 22
CHƢƠNG 2 – CƠ BẢN VỀ CÁC CƠ CHẾ ĐỊNH TUYẾN QoS [2] .............. 25
2.1. Định tuyến QoS nội miền ....................................................................... 25
2.1.1. Vấn đề thuật toán lựa chọn đƣờng đi ................................................ 26
2.1.2. Định tuyến đa đích ........................................................................... 31
2.1.3. Định tuyến liên kết riêng biệt ........................................................... 33
2.1.4. Phƣơng pháp định tuyến dựa trên dự đoán........................................ 34
2.2. Định tuyến QoS liên miền[14]................................................................ 36ii
2.2.1. Các mở rộng QoS và kỹ thuật lƣu lƣợng sử dụng BGP..................... 37
2.2.2. Các phƣơng pháp che phủ ................................................................ 37
2.2.3. Multihoming..................................................................................... 39
2.3. Bảng định tuyến ..................................................................................... 42
2.3.1. Cơ chế trao đổi thông tin để xây dựng bảng định tuyến .................... 44
2.3.2. Các chính sách cập nhật.................................................................... 44
2.3.3. Cơ chế chuyển tiếp ........................................................................... 46
2.3.4. Chuyển tiếp hai mức giới hạn........................................................... 49
CHƢƠNG 3 - OSPF MỞ RỘNG CHO ĐỊNH TUYẾN QoS........................... 51
3.1. Mở rộng đảm bảo chất lƣợng dịch vụ cho OSPF [7]- [12] ...................... 51
3.1.1. Các khả năng tùy chọn QoS.............................................................. 51
3.1.2. Mã hóa tài nguyên khi TOS mở rộng................................................ 52
3.1.3. Mã hóa băng thông ........................................................................... 53
3.1.4. Mã hóa trễ ........................................................................................ 55
3.2. Các cơ chế thực hiện mở rộng QoS cho OSPF........................................ 55
3.2.1. Các thuật toán và thông tin lựa chọn đƣờng dẫn ............................... 55
3.2.2. Thông báo thông tin trạng thái liên kết ............................................. 63
3.3. Khảo sát cơ chế chuyển tiếp trong định tuyến OSPF mở rộng cho QoS.. 66
3.3.1. Hiệu suất của các phiên bản không giới hạn ..................................... 68
3.3.2. Hiệu suất của các phiên bản giới hạn................................................ 72
KẾT LUẬN...................................................................................................... 75
TÀI LIỆU THAM KHẢO ................................................................................ 76
MỞ ĐẦU
Ngày nay, khi công nghệ viễn thông đang phát triển mạnh mẽ trên toàn
thế giới thì vấn đề QoS là mối quan tâm lớn nhất không chỉ của các nhà cung
cấp dịch vụ viễn thông mà của cả những khách hàng sử dụng dịch vụ. Nhằm
mục đích nâng cao chất lƣợng và hiệu quả của mạng thì một trong những giải
pháp đƣợc quan tâm là định tuyến đảm bảo chất lƣợng dịch vụ (định tuyến QoSQoSR). QoSR không những có vai trò làm tăng chất lƣợng dịch vụ mà còn có ý
nghĩa quan trọng trong việc giảm chi phí vận hành mạng, đem lại hiệu quả kinh
doanh và ý nghĩa kinh tế to lớn trên đà phát triển của mạng viễn thông.
Vấn đề định tuyến trên mạng Internet hiện nay tập trung chủ yếu vào việc
cung cấp kết nối và thƣờng chỉ hỗ trợ dịch vụ dữ liệu “cố gắng tối đa”, với các
giao thức định tuyến dùng phƣơng pháp định tuyến tìm đƣờng ngắn nhất OSPF,
việc định tuyến đƣợc tối ƣu dựa trên các số đo tĩnh nhƣ là số lƣợng các chặng và
các trọng số mang tính quản trị. Dịch vụ đƣợc cung cấp bởi những giao thức này
chỉ thích hợp cho các ứng dụng dữ liệu truyền thống mà không thích hợp cho
nhiều ứng dụng yêu cầu sự đảm bảo chặt chẽ về độ trễ và băng thông. Hơn nữa,
với sự phát triển bùng nổ của lƣu lƣợng Internet, việc duy trì định tuyến tìm
đƣờng ngắn nhất của Internet hiện thời dẫn đến sự phân bố mất cân đối của lƣu
lƣợng.
Các giao thức định tuyến hiện nay đƣợc sử dụng trong các mạng IP,
không có bất kỳ nhận thức nào về nguồn tài nguyên sẵn có và yêu cầu. Điều này
có nghĩa là luồng lƣu lƣợng thƣờng đƣợc định tuyến qua các tuyến đƣờng không
có khả năng hỗ trợ các yêu cầu của chúng, trong khi các tuyến đƣờng kế tiếp
nhau với đủ các nguồn tài nguyên có sẵn. Điều này có thể dẫn đến suy giảm
đáng kể về hiệu suất. Mục tiêu của định tuyến đảm bảo QoS là cung cấp các
thuật toán định tuyến có khả năng nhận biết đƣờng dẫn để đáp ứng số lƣợng tối
đa có thể có của các luồng lƣu lƣợng với các yêu cầu QoS. Theo đó, định tuyến
đảm bảo QoS trong bối cảnh của Internet ngày nay đã nhận đƣợc sự quan tâm
ngày càng lớn.
Xuất phát từ thực tế trên, đề tài nghiên cứu: “Các cơ chế định tuyến QoS
và thuật toán mở đƣờng ngắn nhất đầu tiên (OSPF) mở rộng” đƣợc lựa
chọn. Thay vì tìm hiểu các vấn đề chung khá rộng lớn của định tuyến QoS, ở
đây chỉ tập trung vào một vấn đề cụ thể, dựa trên một giao thức định tuyến hiện
có. Cụ thể là, mô tả một tập hợp các đề xuất bổ sung cho giao thức định tuyến
OSPF để hỗ trợ cho việc định tuyến đảm bảo chất lƣợng của dịch vụ (QoS)
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi2
trong IP. Tập trung vào các luồng lƣu lƣợng đơn điểm, chú trọng tới các metric
cần thiết để hỗ trợ QoS, các cơ chế thông báo liên kết kết hợp, thuật toán lựa
chọn đƣờng dẫn, cũng nhƣ các khía cạnh của việc thiết lập tuyến đƣờng đảm bảo
QoS. Mục tiêu là định rõ một cách tiếp cận, trong khi đạt đƣợc các mục tiêu cải
thiện hiệu suất cho các luồng lƣu lƣợng QoS, làm nhƣ vậy với các tác động ít
nhất có thể trên giao thức OSPF hiện có.
Nội dung chính của luận văn gồm ba chƣơng:
Chƣơng 1: Tổng quan về định tuyến đảm bảo QoS
Nội dung chính của chƣơng này là giới thiệu các khái niệm, các vấn đề
liên quan cần nghiên cứu về định tuyến đảm bảo QoS và đặt vấn đề cho các mở
rộng sang OSPF.
Chƣơng 2: Các cơ chế định tuyến QoS
Nội dung chính là trình bày về định tuyến QoS trong mạng phân cấp và
các cơ chế định tuyến đảm bảo QoS.
Chƣơng 3: OSPF mở rộng cho định tuyến đảm bảo chất lƣợng
Nội dung tập trung vào các mở rộng của OSPF cho định tuyến QoS.3
CHƢƠNG 1 - TỔNG QUAN VỀ ĐỊNH TUYẾN QoS
1.1. Giới thiệu định tuyến dựa trên QoS
1.1.1. Định tuyến
Định tuyến là sự lựa chọn đƣờng đi để truyền một đơn vị dữ liệu từ trạm
nguồn đến trạm đích trong một liên mạng theo tiêu chí nhất định. Chức năng
định tuyến đƣợc thực hiện ở tầng mạng, cho phép router đánh giá các đƣờng đi
sẵn có tới đích và chọn đƣờng đi thích hợp (Hình 1.1). Để đánh giá đƣờng đi,
định tuyến sử dụng các thông tin topo mạng, các thông tin này có thể do ngƣời
quản trị thiết lập hay đƣợc thu lƣợm thông qua các giao thức định tuyến.
Hình 1.1. Định tuyến
Tầng mạng hỗ trợ chuyển gói từ đầu cuối tới đầu cuối cố gắng tối đa
(best-effort) qua các mạng đƣợc kết nối với nhau, sử dụng bảng định tuyến để
gửi các gói từ mạng nguồn đến mạng đích. Sau khi đã quyết định sử dụng đƣờng
đi nào, router tiến hành việc chuyển gói. Nó lấy một gói nhận đƣợc ở giao diện
vào và chuyển tiếp gói này tới giao diện ra tƣơng ứng (giao diện thể hiện đƣờng
đi tốt nhất tới đích cho gói).
Mục tiêu cơ bản của các phƣơng pháp định tuyến là nhằm sử dụng tối đa
tài nguyên mạng, và tối thiểu hoá giá thành mạng. Để đạt đƣợc điều này kỹ thuật
định tuyến phải tối ƣu đƣợc các tham số mạng và ngƣời sử dụng nhƣ: xác suất
tắc nghẽn, băng thông, độ trễ, độ tin cậy, giá thành,v.v... Vì vậy, một kỹ thuật
định tuyến phải thực hiện tốt hai chức năng chính sau đây:
Quyết định chọn đƣờng theo những tiêu chuẩn tối ƣu nào đó.
Cập nhật thông tin định tuyến
tuỳ từng trường hợp vào kiến trúc, hạ tầng cơ sở mạng mà các kỹ thuật định tuyến
Chọn đƣờng?
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi4
khác nhau đƣợc áp dụng. Các tiêu chuẩn tối ƣu khi chọn đường dẫn từ trạm
nguồn tới trạm đích có thể phụ thuộc vào yêu cầu ngƣời sử dụng dịch vụ mạng.
Giữa mạng và ngƣời sử dụng có thể có các thoả thuận ràng buộc về chất lƣợng
dịch vụ cung cấp hay một số yêu cầu khác, điều đó có thể dẫn tới khả năng chọn
đƣờng của mạng chỉ là cận tối ƣu đối với một loại hình dịch vụ cụ thể, hay với
một số nhóm ngƣời sử dụng dịch vụ cụ thể. Chức năng cập nhật thông tin định
tuyến là chức năng quan trọng nhất mà các giao thức định tuyến phải thừa hành,
các giải pháp cập nhật thông tin định tuyến đƣa ra hiện nay tập trung vào giải
quyết bài toán cân đối lƣu lƣợng báo hiệu và định tuyến trên mạng với tính đầy
đủ và sự nhanh chóng của thông tin định tuyến.
Có nhiều cách để phân loại giao thức định tuyến, trong đó cách phân loại
phổ biến nhất là phân định tuyến thành định tuyến theo véc-tơ khoảng cách và
định tuyến theo trạng thái kết nối.
Định tuyến theo trạng thái kết nối: các nút mạng quảng bá thông tin định
tuyến tới tất cả các nút trong liên mạng. Tuy nhiên, mỗi router chỉ gửi một
phần bảng định tuyến (phần mô tả trạng thái kết nối của router) và xây
dựng một bức tranh về toàn bộ mạng trong bảng topo. Mỗi khi topo trạng
thái kết nối thay đổi, các router đầu tiên biết đƣợc sự thay đổi này sẽ gửi
một thông báo trạng thái kết nối LSA (Link State Advertisement) mới tới
các router khác hay tới một router chỉ định (nơi các router khác có thể sử
dụng để cập nhật). LSA này sẽ đƣợc tràn ngập (flooding) tới tất cả các
router trên liên mạng.
Định tuyến theo véc-tơ khoảng cách: là một thuật toán thích nghi nhằm
tính toán con đƣờng ngắn nhất giữa các cặp nút trong mạng, dựa trên
phƣơng pháp tập trung đƣợc biết đến nhƣ là thuật toán Bellman-Ford. Các
nút mạng thực hiện quá trình trao đổi thông tin trên cơ sở của địa chỉ đích,
nút kế tiếp và con đƣờng ngắn nhất tới đích.
Khi tính toán đƣờng đi ngắn nhất sử dụng định tuyến theo trạng thái kết
nối và định tuyến theo véc-tơ khoảng cách, thông tin trạng thái của mạng thể
hiện qua các số đo (Metric) thông qua giá (cost), các bộ định tuyến phải đƣợc
cập nhật giá trên tuyến kết nối. Khi có sự thay đổi topo mạng hay lƣu lƣợng,
các nút mạng phải khởi tạo và tính toán lại tuyến đƣờng đi ngắn nhất, tuỳ
theo giao thức đƣợc sử dụng trong mạng.
Các bảng định tuyến chứa thông tin đƣợc sử dụng bởi phần mềm chuyển
mạch để chọn tuyến tốt nhất. Các thuật toán phức tạp có thể chọn tuyến dựa trên5
nhiều metric bằng cách kết hợp chúng thành một metric phức hợp. Các metric
đƣợc sử dụng phổ biến gồm: chiều dài đƣờng đi, độ tin cậy, độ trễ, băng thông,
tải và giá truyền thông. Chúng ta có thể so sánh định tuyến véc-tơ khoảng cách
với định tuyến trạng thái kết nối theo một số tiêu chí nhƣ trong Bảng 1.1:
Bảng 1.1. So sánh định tuyến trạng thái kết nối và véc-tơ khoảng cách.
Véc-tơ khoảng cách Trạng thái kết nối
Nhận thức về topo mạng từ các
router kế cận.
Có đƣợc cái nhìn toàn cảnh về liên
mạng.
Cộng vào véc-tơ khoảng cách từ
router này tới router khác.
Tính toán đƣờng đi ngắn nhất tới tất cả
các router.
Cập nhật định kỳ, hội tụ chậm. Cập nhật ngay khi thay đổi, hội tụ nhanh.
Chuyển bản sao của bảng định
tuyến tới các router kế cận.
Chuyển cập nhật định tuyến trạng thái
kết nối tới tất cả các router.
Định tuyến véc-tơ khoảng cách lấy dữ liệu topo từ thông tin bảng định
tuyến của các router kế cận. Định tuyến trạng thái kết nối có đƣợc một cái
nhìn toàn cảnh về topo của liên mạng bằng cách tích luỹ tất cả các LSA cần
thiết.
Định tuyến véc-tơ khoảng cách xác định đƣờng đi tốt nhất bằng cách cộng
thêm vào giá trị metric mà nó nhận đƣợc khi thông tin định tuyến đƣợc gửi từ
router này tới router khác. Đối với định tuyến trạng thái kết nối, mỗi router làm
việc độc lập trong việc tính toán đƣờng đi ngắn nhất tới các mạng đích.
Trong hầu hết các giao thức định tuyến véc-tơ khoảng cách, cập nhật định
tuyến về thay đổi topo mạng đƣợc gửi định kỳ. Các cập nhật đƣợc gửi từ router
này tới router khác, dẫn đến mạng hội tụ chậm. Với các giao thức định tuyến
trạng thái kết nối, cập nhật đƣợc gửi ngay khi topo mạng thay đổi. Các gói thông
báo trạng thái kết nối LSA có kích thƣớc tƣơng đối nhỏ đƣợc chuyển tới tất cả
các router, do đó thời gian hội tụ sẽ nhanh hơn khi topo mạng thay đổi.
1.1.2. Định tuyến dựa trên QoS
Định tuyến dựa trên QoS là cơ chế định tuyến theo đó đƣờng đi cho các
luồng đƣợc xác định dựa trên một số hiểu biết về sự sẵn sàng của tài nguyên
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi6
trong mạng cũng nhƣ nhu cầu QoS của luồng [3]. Hay nói cách khác, đó là “một
giao thức định tuyến động có mở rộng tiêu chí chọn đƣờng của nó bao gồm các
tham số QoS nhƣ băng thông sẵn có, hiệu quả sử dụng đƣờng đầu cuối và kết
nối, mức tiêu thụ tài nguyên nút, trễ và trƣợt, biến động trễ”. Nói một cách ngắn
gọn là định tuyến động có tính đến QoS.
Hình 1.2 là ví dụ đơn giản về định tuyến dựa trên QoS. Giả sử có luồng
lƣu lƣợng từ nút A tới nút C yêu cầu băng thông 4Mbps, mặc dù đƣờng A-B-C
ngắn hơn, nhƣng nó sẽ không đƣợc chọn vì không có đủ băng thông. Thay vào
đó đƣờng A-D-E-C đƣợc chọn.
Hình 1.2. Ví dụ về phương pháp định tuyến dựa trên QoS
Bên cạnh đó, còn có hai khái niệm liên quan là định tuyến dựa trên
chính sách và định tuyến ràng buộc. Mối quan hệ giữa ba kiểu định tuyến
đƣợc thể hiện trong hình 1.3.
Hình 1.3. Mối quan hệ giữa ba kiểu định tuyến
Định tuyến ràng buộc
Định tuyến theo QoS Định tuyến theo
chính sách7
Định tuyến dựa trên chính sách là quyết định định tuyến không dựa
trên hiểu biết về topo mạng và các số đo mà dựa theo các chính sách quản
trị. Định tuyến theo chính sách thƣờng đƣợc cấu hình tĩnh.
Định tuyến ràng buộc là một quan niệm phát triển từ định tuyến dựa trên
QoS nhƣng có ý nghĩa rộng hơn. Nó tính đƣờng đi để thoả mãn một số ràng
buộc, bao gồm cả các ràng buộc về QoS (yêu cầu QoS và sự sẵn sàng của tài
nguyên) và các ràng buộc theo chính sách.
1.1.3. Mục đích của định tuyến dựa trên QoS
Các giao thức định tuyến Internet hiện nay đƣợc gọi là giao thức định
tuyến “cố gắng tối đa”. Các giao thức này chỉ sử dụng “đƣờng ngắn nhất” tới
đích, chúng thƣờng dùng các thuật toán tối ƣu với mục tiêu đơn, theo đó chỉ xem
xét một số đo (băng thông, số chặng, giá). Nhƣ vậy, toàn bộ lƣu lƣợng đƣợc
định tuyến vào “đƣờng ngắn nhất”, ngay cả khi tồn tại đƣờng cạnh tranh khác,
chúng không đƣợc sử dụng chừng nào chúng chƣa trở thành đƣờng ngắn nhất.
Điều này có thể dẫn tới tắc nghẽn của một vài kết nối, trong khi các kết nối khác
không đƣợc dùng hết.
Định tuyến “cố gắng tối đa” sẽ chuyển lƣu lƣợng từ một đƣờng tới đƣờng
“tốt hơn” mỗi khi nó tìm đƣợc. Việc này xảy ra ngay cả khi đƣờng đang dùng
đáp ứng đƣợc các yêu cầu dịch vụ của lƣu lƣợng. Kiểu chuyển đổi này là không
mong muốn vì nó dẫn tới sự dao động định tuyến, lƣu lƣợng sẽ bị định tuyến
qua lại giữa các đƣờng cạnh tranh. Thậm chí còn tồi tệ hơn vì kiểu dao động này
có thể làm tăng biến động trễ và trƣợt.
Định tuyến dựa trên QoS đƣợc đánh giá là giải quyết hay tránh các vấn đề đã
nêu trên. Các mục tiêu chính của định tuyến dựa trên QoS là:
Thứ nhất, là để đáp ứng các yêu cầu QoS của ngƣời sử dụng. Định tuyến
dựa trên QoS đƣợc giả thiết là để tìm một đƣờng từ nguồn đến đích để
thoả mãn các yêu cầu của ngƣời sử dụng về băng thông, trễ đầu cuối, …
Ngoài ra, việc này phải đƣợc thực hiện trong chế độ động chứ không phải
là cấu hình tĩnh. Trong trƣờng hợp có một vài tuyến khả thi sẵn có, tuyến
đƣợc lựa chọn có thể là cơ sở cho một vài chính sách ràng buộc. Ví dụ:
chúng ta có thể chọn tuyến ít chi phí nhất hay theo nhà cung cấp dịch vụ
chỉ định.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi8
Thứ hai, là để tối ƣu hoá mức độ sử dụng tài nguyên mạng. Đây là mục
đích theo quan điểm của nhà cung cấp dịch vụ. Tất cả các nhà cung cấp
muốn khai thác tối đa khả năng mạng hiện thời của họ, nhờ thế đạt lợi
nhuận cao nhất. Bên cạnh đó, đây cũng là yêu cầu xuất phát từ góc độ kỹ
thuật xây dựng mạng. Định tuyến dựa trên QoS đƣợc trông đợi để quản lý
lƣu lƣợng mạng một cách hiệu quả sao cho thông lƣợng qua mạng là lớn
nhất. Một lƣợc đồ thông thƣờng là luôn lựa chọn đƣờng ngắn nhất trong
số các đƣờng khả thi, vì đƣờng dài hơn có nghĩa là sử dụng tài nguyên
mạng nhiều hơn.
Thứ ba, khi mà mạng ở tình trạng tải lớn, khả năng thực thi của mạng
giảm, giống nhƣ xảy ra tắc nghẽn, định tuyến dựa trên QoS đƣợc mong
đợi là sẽ cho chất lƣợng tốt hơn (ví dụ: thông lƣợng tốt hơn) so với định
tuyến cố gắng tối đa, (định tuyến cố gắng tối đa có thể làm giảm thực thi
mạng một cách đột ngột).
1.2. Các vấn đề cơ bản của định tuyến dựa trên QoS
Định tuyến dựa trên QoS thì khó thiết kế và thực thi hơn nhiều so với định
tuyến cố gắng tối đa. Trong hầu hết các trƣờng hợp mục đích không phải là tìm giải
pháp tốt nhất, mà là tìm giải pháp với chi phí có thể chấp nhận đƣợc.
1.2.1. Metric và sự tính toán đƣờng đi
Có hai vấn đề cơ bản của phƣơng pháp định tuyến dựa trên QoS: Thứ
nhất, đo và thu thập thông tin trạng thái mạng nhƣ thế nào; Thứ hai, tính toán
các lộ trình dựa trên thông tin đã thu đƣợc nhƣ thế nào. Sự lựa chọn metric là rất
quan trọng theo nghĩa rằng: “các metric phải thể hiện các đặc tính mạng cơ bản
mà ta quan tâm”. Do đó các metric nhƣ băng thông sẵn có, trễ, biến động trễ, …
đƣợc sử dụng phổ biến; cũng nhƣ là các metric xác định kiểu bảo đảm QoS mà
mạng cung cấp. Không có phƣơng pháp hỗ trợ yêu cầu QoS nào mà không thể
biểu diễn bởi tổ hợp nào đó của các metric hiện hữu.
Bên cạnh đó cần xem xét sự phức tạp trong tính toán, nghĩa là việc tính
toán đƣờng đi dựa trên một metric hay tổ hợp các metric phải không quá phức
tạp. Tiếc rằng, định tuyến dựa trên QoS thƣờng đƣợc thực hiện với nhiều ràng
buộc và việc tính toán đƣờng dựa trên tổ hợp nhất định nào đó của các metric đã
đƣợc chứng minh là bài toán NP (No Polynomial) hoàn thiện. Rất nhiều thuật
toán đƣợc đề xuất để giải quyết vấn đề này. Một phƣơng pháp chung nhất đƣợc
Ở đây, ta chạy thuật toán BF tiêu chuẩn, đƣợc mô tả trong (3.1), có đƣợc
nhƣ một đầu ra một bảng định tuyến QoS với α nằm trong khoảng 0.5 1, là
một tham số chỉ ra “risk proneness - hiểm” của ngƣời ra quyết định (giá trị càng
thấp, „trạng thái nguy hiểm” càng cao). Thật vậy, cho HR là một tham số chỉ ra
bao nhiêu chặng ngƣời ra quyết định sẵn sàng đánh đổi lấy sự an toàn. Sau đó,
khi một yêu cầu kết nối phù hợp với giá trị b của băng thông, thực hiện nhƣ sau:
Từ bảng định tuyến, có đƣợc hmin là số chặng tối thiểu của một tuyến
đƣờng với băng thông nhỏ nhất là αb
Từ bảng định tuyến, có đƣợc hmax , số chặng tối đa của một tuyến đƣờng
an toàn, nghĩa là với băng thông nhỏ nhất là 2b
Nếu
hmin HR hmax : chọn tuyến đƣờng an toàn
Nếu khác: từ bảng, chọn tuyến đƣờng có băng thông lớn nhất trong số
những tuyến đƣờng có hmin HR chặng.
3.2.2.3. Chi tiết hóa phƣơng pháp (3)
Một vấn đề chính của phƣơng pháp đơn giản trên là tiềm ẩn khả năng các
tuyến đƣờng tốt không đƣợc để ý đến. Một ví dụ đơn giản, xem xét 2 đƣờng dẫn
giữa nguồn và đích: đƣờng dẫn thứ nhất có hai liên kết với 10 đơn vị băng
thông, đƣờng dẫn thứ hai có ba liên kết, hai trong số đó là 20 đơn vị băng thông
và liên kết còn lại với 10 đơn vị băng thông. Giả sử rằng, một yêu cầu kết nối
với 10 đơn vị băng thông đang đƣợc xử lý. Theo phƣơng pháp đơn giản, ta sẽ
không tạo một chú giải cho đƣờng dẫn thứ hai, khi nó cho băng thông tƣơng tự
nhƣ đƣờng dẫn đầu tiên nhƣng với số chặng nhiều hơn. Tuy nhiên, đƣờng dẫn
thứ hai có độ mạo hiểm ít hơn, do đó có thể sẽ là khôn ngoan hơn khi chọn nó.
Cách tiếp cận sau diễn giải vấn đề này.
Cho b1 b2 ... bK với K M là các giá trị băng thông khác nhau tƣơng ứng
với thông báo cuối cùng cho mỗi liên kết (nhƣ trƣớc, M dùng để chỉ số của các
liên kết). Các bƣớc sau đây đƣợc thực hiện cho mỗi bi , 1 i K :
Xóa các liên kết “cấm”, nghĩa là xóa những liên kết với băng thông nhỏ
hơn 0.5bi
Chỉ định “giá” 0 cho một liên kết “an toàn”, nghĩa là, liên kết với băng
thông ít nhất là 2bi , và 1 cho tất cả các liên kết khác, nghĩa là các liên kết
với băng thông thông báo trong phạm vi 0.5 ~ 2 b b i i .
Chạy thuật thoán BF, sử dụng “giá” trên nhƣ là metric.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi66
Kết quả là, nhận đƣợc một bảng cho từng giá trị băng thông (quan tâm) và
cho từng số các chặng h, với đƣờng dẫn có không nhiều hơn h chặng mà có số
các liên kết không an toàn nhỏ nhất (và số các liên kết an toàn lớn nhất) đối với
giá trị băng thông. Sau đó, khi có một kết nối phù hợp với yêu cầu băng thông là
b đơn vị, nghĩa là b(i1) b bi với 1 i K , ngƣời ra quyết định có thể xác định
các tùy chọn khác nhau cho sự trả giá giữa độ an toàn và số chặng cho giá trị
băng thông là bi , và chọn đƣờng dẫn tƣơng ứng theo cảm nhận của nó về sự cân
bằng giữa hai tiêu chuẩn đó.
Phƣơng pháp này là phức tạp về cả thời gian chạy và kích thƣớc bảng, là
M lần lớn hơn so với một thuật toán BF tiêu chuẩn. Phƣơng pháp sau đây nhằm
giải quyết các vấn đề của phƣơng pháp đơn giản (2), nhƣng không phức tạp nhƣ
trong (3).
3.2.2.4. Giảm sự phức tạp của phƣơng pháp (3)
Biểu thị bởi bmax là giá trị lớn nhất mà một băng thông kết nối có thể đạt
đƣợc. Khi các giá trị băng thông thông báo tăng lên theo cấp số nhân, ví dụ nhƣ
với cơ số bằng 2, thuật toán đƣa ra đoán hạn chế phạm vi đƣợc cho phép để
có thể đƣợc thông báo chuỗi tăng lên theo cấp số nhân của ngƣỡng, gọi là 1, 2,
4…. Ví dụ, về nguyên tắc một thông điệp thông báo trạng thái liên kết đƣợc ban
hành chỉ khi một ngƣỡng mới đƣợc vƣợt qua, và rồi thông điệp thông báo trạng
thái liên kết sẽ thông báo ngƣỡng gần nhất với giá trị băng thông hiện thời. Bằng
cách này, tỷ lệ giữa các giá trị băng thông thực tế và các giá trị băng thông thông
báo đƣợc giữ trong phạm vi 0.5…2. Tuy nhiên, số các giá trị thông báo khác
nhau, K, bây giờ trở thành 0(log(bmax )) nhỏ hơn là 0(M) nhƣ trong (3). Theo đó,
độ phức tạp về không gian và thời gian đƣợc giảm xuống 0(MH log(bmax )) và
0(NH log(bmax )) .
3.3. Khảo sát cơ chế chuyển tiếp trong định tuyến OSPF mở rộng cho QoS
Khi cần thông báo thông tin trạng thái dùng để các nút cập nhật bảng định
tuyến của chúng, cả trong OSPF tiêu chuẩn và trong OSPF mở rộng cho định
tuyến QoS nhƣ mô tả ở trên, ngƣời ta dùng phƣơng pháp lan tràn (flooding) để
đƣa thông báo tới tất cả các nút liên quan một cách nhanh chóng nhất. Chƣơng 2
đã trình bày một số cơ chế flooding nhằm giảm quá tải mạng do truyền bản tin
thăm dò dùng để cập nhật định tuyến. Kết quả của các đề xuất trƣớc đây là một
cơ chế chuyển tiếp hai mức.67
Động cơ thúc đẩy cho sự chuyển tiếp dựa trên bảng hai mức là để giảm
quá tải bản tin của flooding. Ví dụ đƣa ra trên hình dƣới đây giúp cho việc hiểu
chuyển tiếp dựa trên bảng 2 mức có thể giảm quá tải nhƣ thế nào. Cho v là nút
đƣợc quan tâm và u1,u2,....um là m hàng xóm của nó. Router v nhận một yêu cầu
kết nối cho một đích có hơn hai chặng. Nhu cầu băng thông là 5. Một trong
những hàng xóm u1,u2,....um là thích hợp. Trong bối cảnh nhƣ vậy, nếu chuyển
tiếp thăm dò dựa trên phƣơng pháp hai mức đƣợc sử dụng, thì thăm dò sẽ đƣợc
loại bỏ. Tuy nhiên, nếu một flooding đơn giản đƣợc sử dụng, thì router v có thể
gửi m bản sao thăm dò tới u1,u2,....um và các thăm dò sẽ bị loại bỏ cuối cùng tại
mỗi
u1,u2,....um . Nhƣ vậy, “lan tràn mù - blind flooding” sinh thêm quá tải. Ngoài
ra, trong chuyển tiếp dựa trên bảng hai mức, nếu đích đến trong vòng hai chặng
thì các thăm dò sẽ đƣợc hƣớng dẫn chỉ về phía đích. Mặt khác, nếu các thăm dò
đƣợc ngập tràn một cách “mù”, ngoại trừ đích, nhiều nút khác sẽ vẫn nhận thăm
dò. Để giảm quá tải, thông tin bổ sung về các hàng xóm mức hai phải đƣợc lƣu
giữ tại mỗi router. Việc duy trì thông tin này tạo thêm tải trong các hình thức
duy trì bảng. Cách tiếp cận hai mức sẽ là hợp lý, nếu quá tải tạo ra do việc duy
trì bảng là ít hơn nhiều so với việc lƣu trữ trong chuyển tiếp thăm dò. Việc lƣu
trữ trong chuyển tiếp thăm dò phụ thuộc vào tài nguyên sẵn có và topo mạng.
Trong luận văn này, đề cập đến chuyến tiếp dựa trên bảng hai mức nhƣ là
chuyển tiếp hai mức.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: