Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Mạng và truyền thông: Các giải thuật chống tắc nghẽn

No description
by

Quang Trieu Nguyen

on 18 May 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Mạng và truyền thông: Các giải thuật chống tắc nghẽn

Fermeture du site marketing "share a coke" en Afrique du Sud et a présenté des excuses.
Nouveaux spots publicitaires
Polémique qui a accompagné le sponsoring des Jeux Olympique de Sotchi,
Début Janvier: a supprimé les images d’un mariage homosexuel de son spot publicitaire diffusé en Irlande

-
Các thuật toán chống tắc nghẽn
trong mạng

Nhóm 8
Mạng và truyền thông
Giảng viên: Ths. Lê Văn Hùng
1. Tổng quan
1.1 Tắc nghẽn là gì?
Tắc nghẽn là một hiện tượng rất quen thuộc trên mạng, mà nguyên nhân nói chung là do tài nguyên mạng giới hạn trong khi nhu cầu truyền thông tin của con người là không có giới hạn.
1.2 Nguyễn nhân gây tắc nghẽn
1.3. Mô hình tổng quan điều khiển chống tắc nghẽn
1.4. Nguyên tắc chung điều khiển tắc nghẽn
Mô tả tắc nghẽn
1.5. Các biện pháp phòng tránh tắc nghẽn
Tại tầng mạng, việc chọn sử dụng
mạch ảo
hay
datagram
sẽ tác động đến tắc nghẽn do nhiều giải thuật điều khiển tắc nghẽn chỉ chạy trên mạch ảo. Giải pháp “lập hàng đợi cho các gói tin và phục vụ chúng” liên quan đến việc một router có một hàng đợi cho mỗi ngõ vào, một hàng đợi cho mỗi ngõ ra hay cả hai.
Giải quyết
Flow control
là xử lý giao thông giữa trạm thu và trạm phát . Một giải thuật vạch đường tốt có thể giúp tránh được tắc nghẽn bằng cách trải đều giao thông trên tất cả đường nối, trong khi một giải thuật tồi chỉ đơn giản gởi quá nhiều thông tin lên một đường tải đã quá tải rồi.
Congestion control
bao gồm tạo ra hoạt động hợp lý cho các máy tính và cả các nút mạng, quá trình lưu trữ bên trong mạng, điều khiển tất cả các yếu tố làm giảm khả năng vận chuyển của toàn mạng
Biện pháp cụ thể
 Bố trí khả năng vận chuyển, xử lý, lưu trữ
 Hạn chế các gói tin vào mạng nhờ cơ chế cửa sổ trượt
 Chặn đường vào của các gói tin khi mạng quá tải.
 Hủy bỏ các gói tin bị tắc nghẽn quá thời hạn
Quản lý thời gian sống của các gói tin


2. Các thuật toán chống tắc nghẽn
2.1. Thuật toán Slow start
2.2. Thuật toán Fast Recovery
2.3. Thuật toán Traffic Shapping
2.4. Thuật toán Explicit Congestion Notification
2.5. Thuật toán Random early discard
3. Các phương pháp chống tắc nghẽn trong mạng
Cảm ơn thầy và các bạn đã lắng nghe! ^^
Mạng và truyền thông:
Ca 1 thứ 4 H407

3.1. Phương pháp DEC bit
3.3. Phương pháp EWA và FEWA
3.4. Phương pháp ETCP
3.5. Phương pháp XCP
3.2. Phương pháp điều khiển trong TCP
3.7. Phương pháp QS-TCP
3.6. Phương pháp FBA-TCP
Phân bổ băng thông hợp lý cho TCP là một phương pháp điều khiển lưu lượng TCP dựa trên thông tin phản hồi về mạng được cung cấp bởi CSFQ
Kết nối TCP đơn đi qua vùng router có khả năng CSFQ
XCP là giao thức truyền thông liên quan đến TCP. XCP phía gởi có thể điều khiển cửa sổ gởi thích hợp hơn để đạt được tính hiệu quả, bình đẳng, điều khiển tắc nghẽn có thể mở rộng qui mô và ổn định trong toàn mạng.
Thuật toán điều khiển chống tắc nghẽn phản hồi trong router có khả năng XCP được phân thành 2 phần: thuật toán hiệu quả và bình đẳng. Với phương pháp này, tính hiệu quả và tính bình đẳng giữa các kết nối XCP trong 1 router có thể được quản lý 1 cách tách biệt nhau.
Ý tưởng
Nếu cửa sổ gởi hiện tại lớn hơn cửa sổ điều khiển lưu lượng thì cửa sổ gởi mới được thiết lập bằng cửa sổ điều khiển lưu lượng:
SWND <=AWND
Sử dụng phản hồi FEWA để tính cửa sổ gởi mới . ETCP phía gởi bắt đầu với 1 cửa sổ gởi khởi tạo và cập nhật cửa sổ gởi theo các cách sau:
Nếu cửa sổ gởi hiện tại nhỏ hơn cửa sổ điều khiển lưu lượng thì cửa sổ gởi được tính như sau:
Dùng thông báo một cách rõ ràng đến phía gửi về băng thông còn khả dụng của các đường ra bằng cách sử dụng cơ chế điều khiển lưu lượng giống như trong TCP để truyền thông tin phản hồi từ các bộ định tuyến đến phía gửi
Điều khiển chống tắc nghẽn
Khôi phục dữ liệu đã mất
Quản lý kết nối.
Chức năng:
Cửa sổ tắc nghẽn
Nhược điểm
Thông tin phản hồi là ẩn
TCP không chia sẻ thông tin điều khiển

Đối với mạng đa dịch vụ
: thuật toán điều khiển chống tắc nghẽn của TCP không đem lại tính bình đẳng cần thiết cho các ứng dụng.

Đối với mạng có lưu lượng biến đổi động
: biến đổi nhanh, điều khiển tắc nghẽn của TCP tỏ ra bất ổn định và không hội tụ.

Phương pháp:
Sử dụng phản hồi ẩn
Ưu điểm:
Khá đơn giản và hữu hiệu
Nhược điểm:
Không đạt được tính hiệu,thông lượng rất thấp.
Tính bình đẳng, độ hội tụ, độ mịn điều khiển cũng không đạt được.
Thuật toán không phù hợp cho các ứng dụng mới trong NGN.
Giải pháp:
Thông báo cho các luồng TCP tại thời điểm bắt đầu xảy ra tắc nghẽn để giảm tốc độ đến, nếu cần thiết thì giảm tốc đọ các luồng khác. Do đó trong trường hợp tắc nghẽn thì giảm tải lưu lượng TCP trong mạng mà không được đồng bộ toàn luồng.
Mục đích thiết kế thuật toán
 Tránh tắc nghẽn
 Tránh đồng bộ toàn cục
 Đường biên của kích thước hàng đợi trung bình
Thuật toán RED:
 Phần 1:
dùng để tính toán kích thước hàng đợi trung bình, được quyết định bởi mức độ của các bó được cho phép đi vào hàng đợi của router. Nó đưa ra bản mô tả các chu kỳ khi hàng đợi rỗng (chu kỳ rỗi) bằng cách đánh giá số lượng m của các gói nhỏ có thể được truyền trong suốt chu kỳ rỗi bởi router. Sau mỗi chu kỳ rỗi, router lại tính toán kích thước hàng đợi TB như thể m gói đã đến được hàng đợi rỗng trong suốt chu kỳ đó.
 Phần 2:
được sử dụng để tính toán xác suất đánh dấu gói và sau đó quyết định xem router đánh dấu các gói có thường xuyên không, để đưa ra các mức tắc nghẽn rõ ràng. Mục đích đánh dấu các gói 1 cách đều đặn của các router là tránh đồng bộ trên toàn thể luồng TCP, tránh lệch và điều khiển kích thước hàng đợi trung bình. Độ chiếm giữ hàng đợi lớn thì xác suất laoị bỏ gói càng cao, độ chiếm giữ hàng đợi càng gần giá trị maxth thì xác suất loại bỏ gói dần tiến tới giá trị maxp
Mô tả quan hệ giữa maxp và độ chiếm giữ lại hàng đợi
2.4.1 ECN đánh dấu trong tiêu đề IP
ECN đánh dấu trên tiêu đề gói tin IP và TCP. ECN sử dụng 2 bit dự trữ trong phần tiêu đề TCP và 2 bit dự trữ trên phần tiêu đề IP.
2.4.1 ECN đánh dấu trong tiêu đề TCP
ECN yêu cầu định nghĩa 2 cờ sử dụng 2 bit của trường dự trữ (reserved field) trong tiêu đề TCP
Khi có quá nhiều gói tin hiện diện trong một mạng con (hoặc một phần của nó), hiệu năng hoạt động của hệ thống bị giảm. Tình trạng này được gọi là “tắc nghẽn”.


Giải pháp
Vòng đóng
Cố gắng giải quyết vấn đề tắc nghẽn bằng cách đưa ra thiết kế tốt cho mạng, thực chất là để đảm bảo tắt nghẽn sẽ không xảy ra. Một khi mạng được khởi động và chạy, sẽ không có việc sửa chữa giữa kỳ.
Vòng mở
Quyết định khi nào nên chấp nhận luồng giao thông mới, quyết định khi nào thì bỏ qua các gói tin và bỏ qua gói nào.
Chu trình phản hồi thông tin. Cách tiếp cận này bao gồm 3 phần:
 Giám sát hệ thống để phát hiện nơi nào và khi nào xảy ra tắc nghẽn.
 Chuyển thông tin đến những nơi cần có những hành động ứng phó.
 Điều chỉnh lại hoạt động của hệ thống để khắc phục sự cố.

Ý tưởng
Giảm cửa sổ phát khi có tắc nghẽn và phát lại với kích thước cửa sổ tăng dần cho tới mức cực đại khi có thể
Vấn đề cần quan tâm khi sử dụng thuật toán
Làm mất rất nhiều thời gian để đạt tốc độ cực đại, đặc biệt là trong môi trường trẽ lớn như VSAT.
Sự nhầm lẫn giữa tắc nghẽn mạng và lỗi do đường truyền
Cải thiện thuật toán Slow-Start
Tạo cho router gần với phía kết nối vệ tinh gửi trả tín hiệu báo nhận (ACK) đối với các gói dữ liệu TCP nhằm tạo cho phía gửi có cảm giác đang tham gia vào một quá trình truyền dẫn với khoảng cách khá ngắn.
Ý tưởng
Vấn đề:
Router phải làm khá nhiều công việc sau khi nó gửi tín hiệu báo nhận.
Cơ chế này cần sử dụng kiểu đường truyền đối xứng
Sử dụng
Khi nhận được 1 gói tin ACK hồi đáp cho dữ liệu đã gửi. Kích thước cwnd được gán bằng giá trị ssthresh
Thuật toán Fast Recovery quy định việc thực hiện thuật toán tránh tắc nghẽn ngay sau khi thực hiện phát lại nhanh
Hạn
chế:
 Việc phát lại các gói bị lỗi
 Trong mạng không đối xứng
 Kỹ thuật quản lý kênh ACK
 Điều khiển tần suất phát ACK để tối ưu hóa quá trình truyền phát dữ liệu trên kênh phát
Các công cụ định hình lưu lượng (traffic-shaping) làm chậm các gói tin khi các gói đi ra khỏi một router sao cho tốc độ truyền tổng thể không vượt quá một giới hạn đã định nghĩa.
Các khái niệm điều hoà lưu lượng traffic-shaping (TS)
Cách hoạt động của công cụ điều hoà lưu lượng Shaping.
Cơ chế hoạt động của mô hình thùng thẻ - Token Bucket
Bùng nổ vượt giới hạn - Excess Burst
Trong thủ tục thiết lập kết nối TCP (TCP SYN và TCP SYN/ACK) phía gởi TCP chèn một yêu cầu bắt đầu nhanh (Quick Start Request) vào gói TCP, đó chính là tốc độ khởi tạo mà phía gởi muốn truyền. Mỗi bộ định tuyến dọc theo đường truyền xác nhận liệu nó có thể đáp ứng yêu cầu lưu lượng mới này. Nếu nó có thể đáp ứng yêu cầu mới này thì nó sẽ truyền yêu cầu QS đi, ngược lại nó sẽ giảm tốc độ dữ liệu đến một giá trị phù hợp.
Để làm được điều đó bộ định tuyến cần thiết phải giám sát sự khác nhau của trọng tải hiện tại và dung lượng sẵn sàng và những yêu cầu QS trong thời gian gần đây. Khi yêu cầu QS (QS request) tới TCP phía nhận, một đáp ứng QS (QS response) tương ứng được tạo ra và chèn vào một thông báo nhận được gởi trở về phía gởi.
Nhận được đáp ứng QS, phía gởi điều chỉnh cửa sổ chống tắc nghẽn khởi tạo theo tốc độ dữ liệu chỉ ra trong đáp ứng QS. Để tránh lưu lượng bùng phát, phía gởi tăng dữ liệu từng bước vào cửa sổ khởi tạo. QSTCP đòi hỏi tất cả các bộ định tuyến, phía gởi và phía nhận hỗ trợ khởi tạo nhanh (QS).
Designer: Shin
Hàng đợi của bộ định tuyến bị đầy
Các bộ xử lý chậm
Các đường truyền băng thông thấp
Kích thước bộ đệm của hàng đợi quá nhỏ
Tốc độ xử lý chậm,cấu hình bộ định tuyến kém
Full transcript