Các kĩ thuật quản lý trong mạng IP

router đặt ở đường biên mạng (router biên), router biên quyết định xem gói nào nhận được đảm bảo, các gói này không bị loại bỏ. Khi các thiết bị truy nhập thu thập và phân phối các luồng dữ liệu từ phía đầu phát khách hàng, router biên sẽ truyền tải các dịch vụ phân biệt trên cơ sở các đặc điểm của lưu lượng. Các router hiệu năng cao cho phép thực hiện thực hiện các chính sách quản lý mạng đã được định nghĩa bởi các luồng lưu lượng được phân loại, băng thông phân bố, thiết lập các độ ưu tiên hàng đợi và đánh dấu các tuyến tối ưu. Router biên truyền thông với các router lõi trong cùng một mạng hoặc với các router biên ở các mạng khác. Ngoài ra router biên còn có khả năng định tuyến lưu lượng tĩnh và liên kết hoặc kết nối tới một hoặc nhiều router lõi. Các tuyến giữa router biên và các router lõi liên quan có thể rất nhiều. Kiến trúc mạng logic cơ bản có thể là mạng sao (star), ring hoặc chain. Mạng mesh cũng được thể hiện trong cấu trúc này. Nhìn chung về cấu trúc router biên cũng tương tự như cấu trúc chung của router đã nói ở trên. Chỉ có hoạt động hơi khác so với router lõi. Router biên hoạt động theo chế độ phân tải còn router lõi hoạt động theo chế độ tập trung tải packet Meter Classifier Marker Shaper / Dropper Hình 2.10: Sơ đồ xử lý gói tin trong router biên Bộ phân loại tiêu chuẩn: lựa chọn các gói trên cơ sở giá trị điểm mã DS. Các gói được lựa chộn sau đó sẽ được truyền tương ứng hoặc tuỳ thuộc vào việc điều phối lưu lượng nếu cần thiết. Phân loại đa trường: Bộ phân loại này lựa chọn các gói trên cơ sở nội dung của một số trường tiêu đề điển hình, là sự phối hợp của địa chỉ nguồn, địa chỉ đích, trường DS, trường giao thức ID, trường số cổng nguồn, cổng đích. Bộ đánh dấu: thực thể này có thể thiết lập giá trị của trường DSCP. Hệ thống hoạt động và định giá băng tần: Các thiết bi nay đựoc cấu hình với các chính sách hoạt động.Chúng lưu giữ sự phân phối lưu lượng hiện tại của các lưu lượng được đánh dấu và biên dịch các yêu cầu mới để đánh dấu lưu lượng. Bộ điều phối lượng: thực thể này có nhiệm vụ đo đạc, đánh dấu, loại bỏ và định dạng lưu lượng. Bộ điều phối lưu lượng có thể đánh dấu lại lưu lượng hoặc có thể loại bỏ, định dạng các gói để thay đổi các tham số tạm thời của luồng và gắn cho nó một tiểu sử lưu lưọng Bộ đo: đo tốc độ của luồng lưu lượng được lựa chọn bởi bộ phân loại.Việc đo này được sử dụng bởi các thành phàn trên hoặc được dùng cho mục đích đếm và đo. Bộ bắt giữ: Định giá kết quả đo được tạo ra từ bộ đo và sử dụng chúng để làm cho các profile lưu lượng trên cơ sở các chính sách có hiệu lực. Bộ loại bỏ gói: loại bỏ một số hoặc tất cả các gói trong luồng lưu lượng nhằm mục đích đưa luồng lưu lượng vào profile lưu lượng. Tiến trình này gọi là bắt giữ các luồng. Định dạng: Trễ các gói bên trong luồng lưu lượng để nó tuân theo một số profile lưu lượng được định dạng. Một bộ định dạng có thể loại bỏ các gói nếu không gian bộ đệm không còn đủ chỗ để chứa các gói có độ trễ. Các bộ điều phối lưu lượng thường được lắp đặt bên trong các node DS đầu vào và các node đường biên đầu ra, nó cũng được lắp đặt bên trong một node ở trong một miền DS. Các node đầu vào của một miền nguồn là node đầu tiên đánh dấu các gói. Các node đầu ra sẽ chuyển các gói tới miền DS khác và có thể đánh dấu lại các gói nếu cần thiết. Các luật điều phối lưu lượng này nằm trong TCA (traffic conditioning agreement) và được áp đặt bởi các bộ phân phối lưu lượng. Các luật TCA được kết nối tới các SLA (service level agreement) được tạo ra giữa khách hàng và nhà cung cấp dịch vụ. Các thoả thuận này sẽ chỉ định loại dịch vụ khách hàng sẽ nhận. Điều này có nghĩa là các miền DS bên trong một vùng bao gồm các ISP ngang hàng với các cái khác và thiết lập các SLA ngang hàng. DS thể hiện phân phối lưu lượng để chắc chắn rằng việc đưa lưu lượng và bên trong miền DS sẽ phù hợp với các luật lệ trong TCA, phù hợp với các chính sách cung cấp dịch vụ của miền. Bộ phân loại lưu lượng hướng các gói để phù hợp với các thành phần điều phối lưu lượng. Các bộ điều phối lưu lượng sử dụng các prifile lưu lượng để chỉ định ra điều kiện của lưu lượng như thế nào. Một profile lưu lưọng định nghĩa các luật lệ cho quá trình chỉ định các gói dù ở trong hay ở ngoài một profile. Các gói bên ngoài profile có thể được xếp hàng cho đến khi chúng ở trong profle (được định dạng), bị loại bỏ (bắt giữ), được đánh dấu bằng điểm mã mới (được đánh dấu lại). Các gói bên profle có thể được sắp xếp lại dưới mức cho phép. Bộ đo sẽ đo các luồng lưu lượng và trạng thái của bộ đo có hiệu lực đối với các gói được đánh dấu, loại bỏ và đinh dạng. Hình dưới mô tả các gói khi đi vào bộ phân loại. Bộ đo sẽ đo luồng lưu lượng và chuyển thông tin tới các thành phần khởi sự một quá trình tương ứng. Bộ đánh dấu sẽ thiết lập giá trị DSCP của gói. Thiết lập các bit trong trường IP của các gói tại các biên của mạng.Sử dụng các bit này để quyết định xem các gói được truyền đi như thế nào bởi các node ,điều phối các gói được đánh dấu sao cho phù hợp với các yêucầu hoặc luật lệ của dịch vụ. Các yêu cầu hoặc luật lệ của mỗi dịch vụ phải được thiết lập thông qua cơ chế chính sách quản trị. Router biên có rất nhiều chức năng, và các chức năng này phụ thuộc vào từng loại router khác nhau. Router biên gồm 3 loại cơ bản: Router chặng đầu tiên (first hop router): đây là router gần với trạm host gửi gói tin nhất. Các gói được phân loại và được đánh dấu tuỳ thuộc vào profile SLS được ấn định cho kết nối. Nó là đáp ứng của việc thiết lập một cam kết về lưu lượng và băng thông mà người sử dụng và nhà cung cấp dịch vụ đưa ra. Router đầu vào: Nó được lắp đặt tại điểm đầu vào của miền DS và nó đảm nhiệm chức năng phân loại tất cả các gói đến trên cơ sở trường DS. Router đầu ra : được lắp đặt tại điểm đầu ra của các mạng DS để điều khiển lưu lượng. Nó cũng đảm nhiệm chức năng phân loại lưu lượng dựa trên trường DS. 2.3.2 Router lõi (core router) Router lõi xử lý lưu lượng trong nội mạng, không liên quan gì tới các mạng khác. Router lõi phải xử lý một số lượng lưu lượng lớn bên trong một mạng, và chức năng của chúng là thêm vào các luồng thông tin và thực hiện việc phân loại, gửi ngược trở lại các gói tin. Do đó các vung lắp đặt router lõi thường lớn và có dạng lưới. Thông thường các node mạng lắp đặt các vùng router lõi cùng các server để cung cấp các dịch vụ Internet (email server, web server, RADIUS, DNS…). Thêm vào các vùng router lõi cũng thường là các điểm trung tâm cho các các kết nối tới các mạng IP khác (do đó nó còn được gọi là các điểm liên tổng đài (IxPs) hay các NAP công cộng). Trong mạng quốc gia lớn các router lõi còn có thể được phân nhỏ ra thành các sub-router và các router lõi transit. Việc giám sát router lõi bao gồm 4 tham số cơ bản dùng để định nghĩa một lớp dịch vụ: băng thông, trễ, jitter, và độ mất gói. Để chuyển tải các lưu lượng hỗn hợp của các loại dịch vụ khác nhau, ví dụ cho loại dịch vụ X được định nghĩa mức chất lượng dịch vụ của mỗi luồng lưu lượng và thực hiện điều khiển QoS để thể hiện mức chất lượng đó (điều khiển hàng đợi đa lớp). Quá trình bắt giữ lưu lượng sẽ giám sát lưu lượng đi vào trong router biên ở mỗi luồng lưu lượng được phân loại bởi việc phối hợp của địa chỉ nguồn và địa chỉ đích ,các đường MPLS, thông tin trong trường DS của header gói tin được dùng để định hướng, giám sát gói tin. Khi gói tin đi vào trong router lõi, nó sẽ sử dụng các thông tin đánh dấu trước đó để thực hiện các đảm bảo liên quan, sau đó được đưa vào hàng đợi tuỳ theo từng lớp chất lượng dịch vụ hay độ ưu tiên của loại dịch vụ mà luồng lưu lượng đó truyền tải. Tại đây các gói tin sẽ được định hướng truyền, thời điểm truyền gói tin sẽ do bộ lập lịch quyết định tuỳ thuộc vào trường ưu tiên trong phần header của gói. Gói tin có độ ưu tiên thấp có thể bị loại bỏ khi có tắc nghẽn xảy ra trong mạng. Router sử dụng nhiều thuật toán, cách thức quản lý để đảm bảo chất lượng dịch vụ trong mạng: như các thuật toán quản lý hàng đợi, thuật toán lập lịch … Các router lõi là các router tốc độ cao được ứng dụng trong phần lõi và phần xương sống của mạng IP. Dữ liệu truyền qua các bộ xử lý trung tâm có tốc độ lên tới hàng trăm Gbps. kiến trúc mạng của các router lõi có dạng lưới hoặc liên lưới ngay cả khi kiến trúc của router biên hay router truy nhập có dạng star hay double star. Nhìn chung hoạt động của router có hai chức năng chính: định tuyến và chuyển gói. Trong suốt quá trình định tuyến router thu thập và xử lý thông tin trong cấu hình mạng và thiết lập ra bảng định tuyến. Bảng này chứa các thông tin được yêu cầu để định hướng và truyền lại gói. Tại các khoảng thời gian 30 đến 60 phút các router sẽ kết nối tới tổng đài và update các bảng định tuyến. Trong suốt quá trình định tuyến các router sẽ định tuyến dữ liệu tới cổng vào đi ra đầu ra tương ứng được chỉ định trong bảng định tuyến. Tuỳ thuộc vào loại lưu lượng có độ ưu tiên khác nhau mà các luồng thông tin được đưa ào hàng đợi khác nhau và được lập lịch đưa ra sớm hay muộn. Để chuyển các gói thì đầu tiên các gói phải được đóng gói và địa chỉ hướng chuyển phải được thiết lập trước khi một gói đi vào hàng đợi đầu ra tương ứng. Cuối cùng khi các gói ở đầu ra lại đước đóng gói thêm một lần nữa. Để tránh tắc nghẽn trong mạng các gói sẽ được chớ trong hàng đợi để chờ xử lý. Trong các mạng DS thì các trường precedence của gói sẽ được đọc ra và các gói dữ liệu sẽ tham gia vào hàng đợi được phân theo độ ưu tiên tại các cổng đầu ra tuỳ thuộc vào lớp lưu lượng của nó. Các có chế hàng đợi dựa trên giao thức RSVP như: hàng đợi có độ trễ thấp (LLQ) hay hàng đợi cân bằng có trọng số (WFQ) cũng phục vụ mục đích ưu tiên hoá các gói trong hàng đợi tối thiểu hoá độ trễ truyền dẫn và thời gian xử lý. Tất cả các hệ thống router yêu cầu 3 thành phần cơ bản để thực hiện 2 chức năng trên: Phần mềm định tuyến (được thiết lập và update trong bảng định tuyến) Các thành phần cho xử lý và định hướng lại các gói (phân loại, bộ lọc, hàng đợi , đánh địa chỉ cho các gói) Các card đầu vào và đầu ra, bao gồm cả backplane. Các card và các giao diện được liên kết nối qua backplane trên cơ sở bus hoặc kiến trúc chuyển mạch. Tóm lại các router là thành phần có bản của mạng, để mạng hoạt động hiệu quả hơn thì ta cần quan tâm nhiều hơn đến khả năng làm việc của các router, do đó các nhà kĩ thuật đang tìm mọi cách để nâng cao khả năng hoạt động và chức năng của router. Có rất nhiều thế hệ router mới ra đời cho phép xử lý các lường lưu lượng đa dạng nhanh hơn và đảm bảo chấ lượng dịch vụ tốt hơn.Việc thiết kế phân phối lưu lượng và điều khiển luồng và cung cấp các tính năng mạng để thoả mãn các yêu cầu về dữ liệu và lưu lượng đa phương tiện trong các loại ứng dụng khác nhau. Việc cung cấp mạng thích hợp có vai trò quan trọng trong việc cung cấp chất lượng dịch vụ QoS cho các yêu cầu của khách hàng bởi nhà cung cấp dịch vụ. Mục đích thiết kế thành phần các router biên là để giám sát mạng tránh các vi phạm cam kết mức dịch vụ (SLA) và việc ăn trộm băng thông. Người sử dụng có thể đưa vào lưu lượng không hợp lệ hoặc vượt quá mức cho phép từ các điểm truy nhập khác nhau gây ảnh hưởng tới chất lượng dịch vụ trong mạng. Do đó lưu lượng ban đầu vào mạng được giám sát điều khiển bởi router lõi. Bộ phân phối và các thành phần điều khiển luồng sẽ giảm bớt tắc nghẽn và việc phân phối không công bằng các tài nguyên mạng. Các router biên sẽ chia sẻ các thông tin tắc nghẽn với các router luồng trên để giữ lại các tài nguyên bị lãng phí trong các miền đường xuống. Việc đánh giá khả năng hoạt động và mở rộng của router biên thông qua các yếu tố: Đối với các router lõi phải ấn định tốc độ tối ưu cho mỗi luồng lưu lượng và trọng số cho các hàng đợi để tối đa hoá lợi nhuận cho các nhà cung cấp dịch vụ của miền mạng. Việc cung cấp phù hợp là rất cần thiết để cung cấp các đường biên cam kết mức dịch vụ như trễ ,khả năng thông qua và độ mất gói cho mỗi người sử dụng. Để chắc chắn rằng tất cả các luồng đều nhận được sự chia sẻ của SLA, thì các luồng của một vùng mạng cần được giám sát để tránh các SLA vi phạm và băng thông bị đánh cắp. Chúng ta cần định nghĩa và phát triển độ thông qua, và độ trễ, độ mất gói và bảo mật giống như các tham số của QoS được thiết kế cho lược đồ giám sát SLA biên –biên để phát hiện các vi phạm dịch vụ. Các bộ điều phối lưu lượng tại router biên được xây dựng cơ chế đánh dấu thông minh và định dạng các gói dựa trên các tham số lớp và tuân theo trạng thái của mạng. Các bộ điều phối sẽ sử dụng các đặc điểm luồng để cung cấp các cách sử dụng tài nguyên tốt hơn và củng cố chất lượng dịch vụ mức ứng dụng. Các router biên được thiết kế để phát hiện và điều chỉnh các luồng không thuận lợi gây ra các hiệu năng thấp cho các luồng tương thích như TCP (những luồng được đối xử lại trong suốt thời điểm tắc nghẽn). Các router biên đầu vào sẽ nhân bản thông tin tắc nghẽn tới các router đầu của miền mạng luồng hướng lên trước đó để giảm sự lãng phí tài nguyên tại mạng đường xuống để từ chối không nhận các gói. Các router biên mở rộng và tương thích được sử dụng để cung cấp khả năng thông qua cao, độ trễ thấp và độ mất gói cho các ứng dụng đa phương tiện hiện hành như IP Telephony, phân phối các dịch vụ media thông qua Internet. Qua sử dụng mô phỏng có thể đánh giá router biên cho các ứng dụng dữ liệu mở rộng như FTP và các ứng dụng nhạy với độ trễ như Telnet và lưu lượng WWW. 2.4 Tổng kết chương Chương 2 giới thiệu chung về cấu trúc và các tính năng của router. Router là một thiết bị mạng quan trọng tại lớp Internet trong mô hình TCP/IP, chức năng chính của router là định tuyến và chuyển gói tin đến chặng tiếp theo. Chương này cũng giới thiệu về cấu trúc CQS trong router. Cấu trúc này cho phép xử lý các gói tin tại lớp Internet, cải thiện chất lượng dịch vụ và điều khiển tắc nghẽn. CHƯƠNG 3: QUẢN LÝ HÀNG ĐỢI VÀ CÁC THUẬT TOÁN 3.1 Các kĩ thuật hàng đợi 3.1.1 Giới thiệu hàng đợi trong Router Lý thuyết hàng đợi nảy sinh một cách tự nhiên trong việc nghiên cứu các chuyển mạch kênh, và chuyển mạch gói. Trong các mạng chuyển mạch kênh, cuộc gọi đến chuyển mạch ngẫu nhiên, mỗi cuộc gọi sẽ giữ kênh trong một khoảng thời gian ngẫu nhiên nào đó. Trong mạng chuyển mạch gói, các gói tin với các chiều dài khác nhau đi qua mạng, tài nguyên mạng (các chuyển mạch,kết nối sẽ được chia sẻ cho các gói). Các bản tin được định tuyến đến các node tiếp theo. Thời gian sử dụng bộ đệm (trễ hàng đợi) là một vấn đề quan trọng trong truyền dẫn thông tin. Thời gian này phụ thuộc vào các thời gian xử lý, độ dài bản tin hay thời gian chờ xử lý khi chưa có tài nguyên sử dụng. Trong các ứng dụng tương tác và thời gian thực thì thời gian trả lời trung bình được xem như một tiêu chuẩn quan trọng còn trong các ứng dụng khác thì thông lượng lại là điều quan trọng nhất. Việc mô tả hàng đợi theo lý thuyết toán học rất phức tạp nên ta chỉ mô tả chúng theo mô hình đơn giản được sử dụng trong các mạng IP: Server Queue Dispatching discipline departures w=items wait Tw=wait time q= items in queuing system Tq = queuing time Ts= service time P= utilization arrivals λ =arrival rate Hình 3.1: Mô hình hàng đợi đơn giản trong mạng Tin tức (có thể là gói tin hay bản tin) đến hệ thống để yêu cầu phục vụ. Nếu server rỗi thì gói tin sẽ được phục vụ ngay lập tức, ngược lại chúng sẽ được lưu giữ trong các hàng đợi. Khi rời khỏi hàng đợi các gói sẽ được xử lý. Các tham số cơ bản liên quan tới hàng đợi: Bảng 3.1 : Bảng các tham số cơ bản của hàng đợi Tham số Kí hiệu Chú thích Tốc độ đến TB λ Thời gian gói tin đến hệ thống hàng đợi với vận tốc λ trên một đơn vị thời gian(s) Tốc độ rời khỏi TB μ Các gói tin rời khỏi hệ thống với tốc độ μ trên một đơn vị thời gian Hiệu suất sử dụng dịch vụ p Là khoảng thời gian server bận do phải xử lý lý,đo bằng P= λ /μ Độ dài TB Lw Là số gói nằm trong hàng đợi trung bình tại tất cả các thời điểm t Thời gian đợi TB Tw Có hai định nghĩa: Thứ nhất: được tính bằng tất cả thời gian gói tin đến xử lý (bao gồm cả các gói không phải chờ trong hàng đợi) Thứ hai: chỉ tính TB thời gian các gói tin phải chờ trong hàng đợi Thời gian phục vụ TB Ts Thời gian TB giữa thời điểm gửi gói tới server và thời điểm rời khỏi server Độ dài hàng đợi TB Lq Số gói trung bình trong hệ thống, bao gồm các gói đang được sử dụng và các gói đang chờ trong hàng đợi. Thời gian xếp hàng TB Tq Thời gian các gói ở trong hệ thống. Các gói đến hàng đợi với tốc độ thay đổi λ và đây là một quá trình poisson, thời giạ phục vụ có phân bố mũ tốc độ μ (thực chất là thời gian trung bình mà các gói tin rời khỏi hàng đợi). Khi các gói đến hệ thống tăng thì hiệu suất sử dụng hệ thống cũng tăng, dẫn tới tắc nghẽn có khả năng xảy ra. Với p =1 thì các server bão hoà do đó tốc lớn nhất theo lý thuyết mà hệ thống có thể xử lý được là: λmax= 1/Ts Tại λmax thì kích thước hàng đợi rất dài không thể kiểm soát được. Trong thực tế thời gian trả lời và những yêu cầu kích thước hàng đợi giới hạn tốc độ đầu vào của thông tin là 70-90% so với λmax theo lý thuyết. Tại các router và chuyển mạch trong phần lõi của kiến trúc các dịch vụ phân biệt của mạng Internet có các thuật toán lập lịch và quản lý hàng đợi. Ngày nay kiến trúc dịch vụ phân biệt bao gồm hàng đợi cân bằng có trọng số (WFQ) cùng kĩ thuật tách sớm có trọng số (WRED). Các kĩ thuật trên được sử dụng trong mạng Internet làm nhiệm vụ điều khiển tắc nghẽn và điều khiển luồng lưu lượng trong mạng. Điều khiển tắc nghẽn là vấn đề quan trọng cần giải quyết trong việc truyền tin trong mạng. Nó sử dụng hai cơ chế độc lập: Cơ chế điều khiển vòng kín (Closed Loop control): điều khiển việc truyền các gói từ các nguồn đầu cuối tới đích Các thuật toán lập lịch vòng hở (opened loop control): ràng buộc độ ưu tiên được cấu hình từ trước và phân phối băng thông cho các kết nối. Hệ thống điều khiển vòng kín bao gồm các thuật toán nguồn được điều khiển bởi các thuật toán kết nối. Thuật toán nguồn này là bất kì giao thức nào được truyền tải trên mạng Internet (ví dụ: TCP, UDP, RTP) và chúng không nhất thiết phải có phản hồi đáp ứng với tắc nghẽn. Các thuật toán điều khiển kết nối hay còn gọi là các thuật toán quản lý hàng đợi (hoặc quản lý hàng đợi tích cực AQM). Các thuật toán AQM bao gồm thuật toán loại bỏ đuôi, thuật toán phát hiện sớm ngẫu nhiên (RED). Thuật toán AQM thực hiện việc báo hiệu tới nguồn bằng việc đánh dấu các gói, thông báo tắc nghẽn tường minh (ECN) hay loại bỏ các gói. Các thuật toán lập lịch vòng mở quyết định xem gói nào sẽ được gửi kế tiếp. Thuật toán này quyết định trật tự các gói truyền dẫn trên cơ sở trật tự sắp xếp các gói đến và các lớp lưu lượng ưu tiên trong gói. Còn dịch vụ phân biệt sử dụng 3 bit trong tiêu đề mỗi gói để định nghĩa lớp. Quá trình lập lịch của gói điều khiển trật tự truyền dẫn giống như phân bố băng thông tương ứng cho mỗi lớp dịch vụ. Lập lịch bao gồm các thuật toán liên quan tới hàng đợi: hàng đợi FIFO, hàng đợi cân bằng có trọng số WFQ, và các thuật toán lập lịch như: Thuật toán RR, thuật toán PS. Hình 3.2 : Tiến trình xử lý hàng đợi trong router Để hiểu rõ về các hàng đợi được sử dụng trong có chế điều khiển tắc nghẽn ta phải trả lời các câu hỏi: Các gói sẽ được lắp đặt như thế nào trong hàng đợi. Thứ tự hay cách thức nào mà các thiết bị mạng phục vụ các hàng đợi của chúng. Các hoạt động nào của mạng để đối xử với các bó lưu lượng và hàng đợi bị tràn. Router được xem như hộp lớn, trong đó có các thành phần thực hiện việc truyền thông tin. Trong ví dụ này ta xét router có 2 giao diện. Gói tin đi từ mạng A tới mạng B. Mạng A tiếp xúc với router qua giao diện IF0, mạng B tiếp xúc với router qua giao diện IF1. Sau khi các gói được đưa đến từ giao diện IF0 sẽ được đặt vào trong hàng đợi queue 0 (hàng đợi đầu vào). Tiếp theo các gói đi vào trong router và được định hướng tới router kế tiếp dựa trên địa chỉ đích lưu giữ trong phần header của gói tin,một số gói tin đi ra từ hàng đợi queue 0 được đưa vào hàng đợi queue 1 kết nối với giao diện IF1. Hàng đợi queue1 còn gọi là hàng đợi đầu ra. Có rất nhiều kĩ thuật hàng đợi: FIFO (first in first out), PQ (priority queue-hàng đợ ưu tiên), FQ (fair queue-hàng đợi cân bằng). FIFO đây là kĩ thuật xếp hàng vào trước ra trước cơ bản. Các gói đến trước sẽ là các gói đầu tiên được xử lý. Khi hàng đợi đầy và có tắc nghẽn xảy ra thì các gói đến sẽ bị loại bỏ. Hàng đợi FIFO dựa vào hệ thống đầu cuối để điều khiển tắc nghẽn thông qua cơ chế điều khiển tắc nghẽn. Do loại hàng đợi này rất đơn giản nhiều khi không điều khiển được tắc nghẽn nên ta thường xét các loại hàng đợi hiệu quả hơn: hàng đợi ưu tiên(PQ), hàng đợi cân bằng (FQ), hàng đợi có trọng số (WQ). 3.1.2 Hàng đợi FIFO (First In First Out) FIFO là hàng đợi mặc định được sử dụng trong hầu hết các router trên thế giới. Hoạt động của FIFO. Các gói đến từ các luồng khác nhau được đối xử công bằng bằng cách đưa vào các hàng đợi theo trật tự đến (gói nào đến trước sẽ được đưa vào trước và được phục vụ trước) Hình 3.3 : Hoạt động của hàng đợi FIFO Hàng đợi hoạt động như một nơi lưu giữ các gói để tránh việc loại bỏ các gói không cần thiết khi có dấu hiệu của tắc nghẽn. Khi có tắc nghẽn xảy ra, và hàng đợi tràn thì tất cả các gói đến sẽ bị loại bỏ. Hàng đợi FIFO được sử dụng hầu hết trong các router, nó đơn giản do không phải định cấu hình cho nó mà chỉ việc sử dụng luôn. Trong các router của cisco, khi không có kế hoạch hàng đợi nào khác được cấu hình, thì tất cả các giao diện(ngoại trừ các giao diện có tốc độ bằng hoặc nhỏ hơn luồng E1) đều sử dụng hàng đợi FIFO mặc định. Tốc độ xử lý gói phải nhanh hơn tốc độ các gói đến hàng đợi IF0 thì mới tránh được hiện tượng tắc nghẽn trong mạng (hàng đợi IF1 rỗng), khi tốc độ xử lý quá thấp hơn so với tốc độ các gói vào, có nghĩa là tốc độ ra nhỏ hơn tốc gói vào (hàng đợi đầu ra dễ bị tràn) thì sẽ xảy ra tắc nghẽn khi có quá nhiều gói đi vào trong mạng, và khi vấn đề này xảy ra thì các gói đến sau sẽ bị loại bỏ 3.1.3 Hàng đợi ưu tiên PQ (Priority Queue) Kĩ thuật này được sử dụng trong trường hợp đa hàng đợi, mỗi hàng đợi có một mức ưu tiên khác nhau, hàng đợi nào có mức ưu tiên cao nhất sẽ được ưu tiên phục vụ trước. Khi có tắc nghén xảy ra thì các gói trong các hàng đợi có độ ưu tiên thấp sẽ bị loại bỏ. Có một vấn đề đối với kĩ thuật này: khi các hàng đợi có độ ưu tiên cao quá nhiều thì các gói trong hàng đợi có độ ưu tiên thấp sẽ không bao giờ được phục vụ. Các gói được phân loại và được sắp xếp vào hàng đợi tuỳ thuộc vào thông tin bên trong các gói. Tuy nhiên kĩ thuật này dễ bị lạm dụng bởi người sử dụng hay các ứng dụng do ấn định các độ ưu tiên không cho phép. Vậy PQ cho phép định nghĩa các luồng lưu lượng ưu tiên như thế nào trong mạng? Ta có thể cấu hình các độ ưu tiên lưu lượng, có thể định nghĩa một loạt các bộ lọc trên cơ sở các đặc điểm của gói qua router để sắp xếp các lưu lượng trong các hàng đợi. Hàng đợi có độ ưu tiên cao nhất sẽ được phục vụ trước cho đến khi hàng đợi rỗng, sau đó các hàng đợi có độ ưu tiên thấp hơn sẽ được phục vụ lần lượt. Câu hỏi đặt ra là PQ làm việc như thế nào? Trong quá trình truyền dẫn,các hàng đợi có độ ưu tiên cao được đối xử ưu tiên hơn các hàng đợi có mức ưu tiên thấp hơn, hay nói cách khác các, lưu lượng quan trọng sẽ được gán các mức ưu tiên cao và lưu lượng có mức ưu tiên cao nhất được truyền trước, còn lại các lưu lượng ít quan trọng hơn. Các gói được phân loại dựa trên các tiêu chuẩn phân loại của người sử dụng,và được đặt ở một trong số các hàng đợi đầu ra với các độ ưu tiên: độ ưu tiên cao, trung bình, bình thường (không được ưu tiên), ưu tiên thấp. Các gói không được ấn định độ ưu tiên sẽ được đưa tới các hàng đợi bình thường. Khi các gói được gửi tới giao diện đầu ra, các hàng đợi ưu tiên tại giao diện đó được quét các gói theo thứ tự độ ưu tiên giảm dần. Hàng đợi có độ ưu tiên cao nhất được quét đầu tiên, sau đó đến các hàng đợi trung bình và tiếp tục các hàng đợi có độ ưu tiên khác. Gói đứng đầu hàng đợi có độ ưu tiên cao nhất được truyền đầu tiên. Thủ tục này được lặp lại mỗi khi có một gói được truyền. Chiều dài lớn nhất của hàng đợi được định nghĩa theo chiều dài giới hạn. Khi một hàng đợi dài hơn chiều dài hàng đợi giới hạn thì các gói đến sau sẽ bị loại bỏ. Cơ chế hàng đợi đầu ra ưu tiên có thể được sử dụng để quản lý lưu lượng từ tất cả các giao thức trong mạng. PQ cung cấp cách đối sử ưu tiên cho các luồng lưu lượng có độ ưu tiên cao, chắc chắn rằng các luồng lưu lượng then chốt khi qua các kết nối WAN sẽ đạt được độ ưu tiên cao. Các gói được phân loại như thế nào trong kĩ thuật PQ Danh sách ưu tiên là một tập các luật lệ mô tả các gói sẽ được ấn định các độ ưu tiên như thế nào trong các hàng đợi. Ngoài ra nó cũng có thể mô tả độ ưu tiên mặc định hoặc giới hạn kích thước hàng đợi của các hàng đợi ưu tiên. Các gói được phân loại theo: Loại giao thức hoặc giao thức con Giao diện đầu vào Kích thước các gói tin Các Fragment Danh sách truy nhập Tất cả các lưu lượng dùng để quản lý và điều khiển mạng đều được ấn định độ ưu tiên cao nhất để trong trường hớp có tắc nghẽn xảy ra thì chúng được ưu tiên truyền trước. Các lưu lượng không được ấn định mức ưu tiên nào thì được đưa vào