Đề tài Mạng IP và vấn đề quản lý bộ đệm

i thành một địa chỉ vật lý sử dụng ARP. Vậy địa chỉ subnet này từ đâu, vì tất cả 32 bit của địa chỉ IP được sử dụng cho định danh mạng và định danh host. Câu trả lời là các nhà thiết kế mạng IP cung cấp một phương tiện để mượn một số bit từ định danh host để tạo ra một địa chỉ subnet. Một thông số được gọi là mặt nạ mạng con (subnet mask) cho biết bao nhiêu bit được sử dụng cho định danh subnet và bao nhiêu còn lại cho định danh host thật sự. Giống một địa chỉ IP, một subnet mask là một số nhị phân 32 bit. Các bit của subnet mask được sắp xếp theo một dạng thức cho biết định danh subnet của địa chỉ IP mà mặt nạ này kết hợp. Hình 1.6 cho thấy một cặp địa chỉ IP/subnet mask. Mỗi vị trí bit trong subnet mask đại diện cho một vị trí bit trong địa chỉ IP. Subnet mask sử dụng một bit 1 cho mỗi bit trong địa chỉ IP thuộc định danh mạng và định danh subnet. Subnet mask sử dụng một bit 0 để chỉ định bất kỳ bit nào trong địa chỉ IP thuộc định danh host. Như vậy, có thể xem xét subnet như một bản đồ sử dụng để đọc địa chỉ IP. Hình 1.7 cho thấy sự phân phối các bit địa chỉ trong một mạng được phân mạng con so với một mạng không được phân mạng con. Các bảng định tuyến sử dụng trong các router và các host trên một mạng phân mạng con sẽ chứa thông tin về subnet mask cùng với mỗi địa chỉ IP. Như Hình 1.8 cho thấy, một datagram đang tới được định tuyến đến mạng sử dụng trường định danh mạng xác định bởi lớp địa chỉ. Khi datagram đến mạng này, nó được định tuyến đến phân mạng thích hợp sử dụng định danh subnet. Sau khi đến phân đoạn, định danh host được sử dụng để phân phối datagram đến đúng máy tính. 1.3. IP - MỘT HỆ THỐNG PHI KẾT NỐI Nghiên cứu về lưu lượng Internet cho thấy rằng đa số các luồng là rất ngắn, chỉ bao gồm một vài gói, cho dù phần lớn các gói đều thuộc về một số ít luồng (kích thước luồng dài hơn). Do đó, hầu hết trong các luồng, phần mào đầu của tín hiệu có thể vượt quá phần thông tin người sử dụng được gửi. IP xử lý điều này một cách linh hoạt: nó cung cấp một dịch vụ phi kết nối giữa những người sử dụng kết cuối bằng cách các đơn vị dữ liệu liên tiếp có thể truyền theo những đường khác nhau. Tại một bộ định tuyến, mỗi gói được xử lý độc lập liên quan tới quyết định tuyến đường (dựa trên cơ sở địa chỉ đích trong tiêu đề gói IP) cho bước nhảy kế tiếp theo hướng tới đích. Đây là ý tưởng cho sự truyền dẫn dữ liệu trên các luồng với số lượng gói nhỏ, và cũng hoạt động tốt đối với số lượng gói lớn. Vì vậy, các gói được gửi từ cùng một nguồn tới cùng một đích có thể theo nhiều đường đi khác nhau từ nguồn tới đích. Các tuyến đường trong IP có thể thích ứng nhanh chóng với tình trạng tắc nghẽn và các hỏng hóc thiết bị. Mặc dù nếu quan sát từ phía mỗi gói, dịch vụ thực sự không tin cậy, với sự truyền thông giữa những người sử dụng đầu cuối IP là rất mạnh. Có các giao thức của lớp giao vận, như giao thức điều khiển truyền dẫn (TCP), điều chỉnh sự thiếu tin cậy vốn có của gói truyền trong IP. TCP sắp xếp lại những gói không theo thứ tự, phát hiện và khôi phục lại các gói đã mất (hay trễ quá mức) qua một hệ thống các định thời, các đáp ứng và các chỉ số chuỗi. Nó cũng cung cấp một phương thức điều khiển luồng trên cơ sở tin cậy mà làm biến đổi những sự tắc nghẽn của mạng bằng cách giảm tốc độ tại thời điểm gói được gửi đi. Điều này hiệu quả với lưu lượng thích ứng, tức là lưu lượng như truyền tải thư điện tử hoặc file có thể điều chỉnh với những thay đổi rộng về độ trễ và thông lượng (như dữ liệu cuối cùng mang lại), nhưng không hiệu quả với các luồng lưu lượng, tức là lưu lượng không thích ứng. Dạng lưu lượng thứ hai này đòi hỏi ít nhất một tốc độ bit tối thiểu qua mạng cho bởi giá trị bất kỳ. Âm thoại, tại một tốc độ trung bình 64 kbit/s là một ví dụ (trừ khi có thêm một sự phức tạp khác) đây là tốc độ phải được hỗ trợ nếu không tín hiệu sẽ chịu nhiều mất mát để đáp lại sự khó hiểu (và do vậy mà vô nghĩa) của nó. Những yêu cầu cho lưu lượng không thích ứng là rất khó gặp, và không thể đảm bảo, trong một môi trường có biến động trễ, thông lượng và tắc nghẽn cao. Đây là lý do vì sao chúng thường được mang đi bằng các công nghệ hướng kết nối. Vậy, làm thế nào để một mạng IP có thể xử lý với cả hai loại hình lưu lượng, thích ứng và không thích ứng. Yêu cầu thứ nhất là phải phân vùng lưu lượng vào các nhóm để có thể đưa ra các phương pháp xử lý khác nhau thích hợp cho những đòi hỏi hiệu năng của chúng. Yêu cầu thứ hai là cung cấp các phương thức để thiết lập trạng thái cho các nhu cầu của chúng, và các phương thức để dự phòng tài nguyên riêng biệt cho các nhóm lưu lượng khác nhau đó. Kiến trúc dịch vụ tích hợp (ISA – Intergrated Services Architecture), Giao thức dự phòng tài nguyên (RSVP – Resource Reservation Protocol), Các dịch vụ phân biệt (DiffServ – Differentiated Services), và Chuyển mạch nhãn đa giao thức (MPLS – Multiprotocol Label Switching) là những phương thức khác nhau nhằm đạt được mục tiêu đó. 1.4. LƯU ĐỆM VÀ QUẢN LÝ BỘ ĐỆM TRONG IP 1.4.1. Lưu đệm trong các bộ định tuyến IP Các mạng IP chuyển dữ liệu dưới dạng những đơn vị riêng biệt. Các nút mạng, quản lý những gói IP, kết hợp các luồng lưu lượng từ những nguồn khác nhau và hướng chúng tới các đích khác nhau qua những liên kết truyền dẫn mà lưu lượng chia sẻ cho từng phần của chặng đường. Quá trình xử lý này bao hàm việc lưu trữ tạm thời dữ liệu trong những bộ đệm có kích cỡ giới hạn, kiểu đi đến thực tế của các gói gây lên những hàng đợi làm tăng và giảm bớt kích thước hàng đợi. Do vậy, trong công nghệ mạng IP, các đơn vị dữ liệu cạnh tranh dung lượng truyền dẫn đầu ra, và tạo thành các kiểu hàng đợi trong bộ đệm. Trong thực tế, các bộ đệm này có thể được đặt tại những vị trí khác nhau tuỳ theo các dịch vụ (ví dụ tại các lối vào, các lối ra hay các điểm chuyển mạch) nhưng đây không phải là điều quan trọng nhất. Thời điểm các hàng đợi được định dạng là khi số lượng gói đi đến qua một chu kỳ đã vượt quá con số khởi hành, và do đó nó là mẫu thực tế của các gói đi đến của hầu hết các thông số. Lưu đệm, khi đó, là phương thức thực tế trong IP. Tuy nhiên, những bộ đệm được cung cấp đơn giản lại không phải là một giải pháp đủ tốt; cần phải cung cấp chất lượng dịch vụ (QoS – Quality of Service) mà người sử dụng yêu cầu (và phải trả tiền). Để chắc chắn đảm bảo QoS, các bộ đệm này phải được sử dụng một cách thông minh, và những dự định này cung cấp ra Quản lý bộ đệm. 1.4.2. Quản lý bộ đệm Phương thức quản lý bộ đệm theo đặc trưng IP được thiết kế để nâng cao dung lượng của các mạng. Thực chất, những phương thức này giải quyết việc các gói tăng cường truy cập vào vùng đợi giới hạn của bộ đệm như thế nào, và khi ở trong vùng đợi thì chúng tăng cường truy cập như thế nào vào bộ phục vụ cho quá trình truyền dẫn hướng tới. Trước hết giải quyết cách thức phân vùng không gian bộ đệm, và các chính sách loại bỏ trong hoạt động. Cuối cùng là giải quyết cách thức các gói được sắp xếp và lập lịch cho quá trình phục vụ, và việc phân vùng dung lượng phục vụ. Yêu cầu then chốt là cung cấp các phân vùng, nói cách khác là các bộ đệm ảo, qua những nhóm dung lượng khác nhau có thể được truyền đi. Ở mức độ cao nhất, một bộ đệm ảo được cung cấp cho mỗi luồng IP, và nó có sự cấp phát không gian bộ đệm cùng dung lượng phục vụ của chính nó. Điều này được gọi là xếp hàng theo luồng. Điển hình, những sự xem xét về phương diện ý nghĩa thì lưu lượng, các luồng, phải được quản lý trong tổng số các bộ đệm ảo đi qua, đặc biệt là trong mạng lõi. Thuật ngữ có thể thay đổi (ví dụ, tổng hợp hoạt động trong DiffServ, đường trung kế lưu lượng trong MPLS), nhưng việc nhóm lại có xu hướng tuỳ theo loại lưu lượng, nói cách khác chúng có những yêu cầu về hiệu năng và các đặc trưng lưu lượng tương tự nhau. Các chính sách loại bỏ cung cấp biện pháp để phân biệt giữa các mức độ mất mát gói tương đối và phạm vi cũng như tác động của mất mát trong các luồng của lưu lượng tổng. Trong IP, trường kiểu dịch vụ (ToS) trong IPv4 và trường độ ưu tiên trong IPv6 có các mã chỉ ra các mức khác nhau trong cách xử lý mất mát dùng để phân biệt giữa các mức của “độ ưu tiên không gian”. Một bộ đệm ảo được cho rằng toàn các gói có độ ưu tiên thấp có thể vẫn cho phép các gói có độ ưu tiên cao hơn được truy cập. Hiệu ứng này là để gia tăng khả năng mất mát của các gói có độ ưu tiên thấp so với các gói có độ ưu tiên cao hơn. Thêm vào đó, trong IP có một phương thức loại bỏ gọi là phát hiện sớm ngẫu nhiên (RED – Random Early Detection) giải quyết trước tình trạng tắc nghẽn bằng cách loại bỏ những gói có khả năng trước khi bộ đệm đầy. Các gói bị loại bỏ với xác suất tăng lên khi kích thước hàng đợi trung bình vượt quá một ngưỡng cấu hình. Lý do cơ bản phía sau phương thức RED bắt nguồn từ thách thức đặc biệt của lưu lượng gói nỗ lực tốt nhất trải qua: TCP, trường hợp cụ thể, có thể đưa ra hoạt động không mong muốn khi mạng (hoặc một phần của nó) bị tắc nghẽn. Khi một bộ đệm đầy và phải loại bỏ các gói đi tới từ nhiều kết nối TCP, tất cả chúng sẽ truy cập các pha khởi đầu chậm của chúng. Điều này làm giảm lượng tải trọng qua bộ đệm, nhưng do nó ảnh hưởng nhiều kết nối nên dẫn đến một chu kỳ dưới sử dụng. Khi tất cả các kết nối TCP đó thoát ra khỏi khởi đầu chậm tại cùng thời điểm, thì lưu lượng sẽ bị gia tăng đáng kể, gây ra tình trạng tắc nghẽn trong bộ đệm và nhiều gói bị loại bỏ hơn. Nguyên lý bên dưới RED là nó ứng dụng cách ngăn cản một cách từ từ: trong những tầng trước của tình trạng tắc nghẽn, chỉ một vài kết nối TCP bị ảnh hưởng, và điều này có thể đủ để giảm tải và tránh được bất kỳ sự gia tăng nào được trình bày. Nếu kích cỡ hàng đợi trung bình tiếp tục tăng, thì các gói bị loại bỏ với xác suất tăng lên, và do đó có nhiều kết nối TCP bị ảnh hưởng hơn. Khi kích cỡ hàng đợi trung bình vượt quá một ngưỡng trên, tất cả các gói đi đến đều bị loại bỏ. Ngoài sự chấp nhận điều khiển cho các bộ đệm, IP còn nêu bật khả năng để điều khiển quá trình xử lý dữ liệu của các lối ra đó từ những bộ đệm – phương thức lập lịch bộ đệm. Điều này cung cấp một biện pháp để phân biệt giữa độ trễ, cũng như tốc độ bit, do đó một số cần dung lượng truyền dẫn lớn hơn. Trong IP, các bộ định tuyến có thể thực hiện việc sắp xếp độ ưu tiên thời gian (hàng đợi thứ tự) và các phương pháp như hàng đợi công bằng hoặc hàng đợi round robin, để phân vùng dung lượng dịch vụ giữa các bộ đệm ảo. Chương 2: ĐIỀU KHIỂN LƯU LƯỢNG VÀ KỸ THUẬT HÀNG ĐỢI 2.1. ĐIỀU KHIỂN LƯU LƯỢNG IP cung cấp khả năng lưu trữ tạm thời các gói trong những bộ đệm qua mạng, mô tả các biến động độ trễ, và trong từng thời điểm, là mất mát. Những bộ đệm này bao gồm các phương thức khác nhau để đảm bảo các mạng phục vụ cho những kiểu lưu lượng khác nhau - cả thích ứng và không thích ứng. Như đã lưu ý, một phần của giải pháp cho vấn đề này là sử dụng các chiến lược quản lý bộ đệm: phân vùng và dự phòng thích hợp các tài nguyên - cả không gian bộ đệm và dung lượng dịch vụ. Tuy nhiên, có những phần khác để giải quyết tất cả: điều khiển lưu lượng. Điều này cho phép những người sử dụng xác định trạng thái các nhu cầu truyền thông của họ, và đảm bảo mạng phối hợp cũng như giám sát được quá trình cung cấp tương ứng của nó. Việc thu nhận nhanh chóng một yêu cầu dự phòng (cho một luồng IP), một mạng đánh giá xem nó có thể quản lý được lưu lượng không, thêm vào những gì đã được chấp nhận trong mạng. Quá trình này phức tạp hơn so với chuyển mạch kênh, vì một số yêu cầu dự phòng sẽ đến từ các dịch vụ có tốc độ bit thay đổi (VBR – Variable bit-rate), làm cho tốc độ bit tức thời được đòi hỏi sẽ biến đổi ngẫu nhiên theo thời gian, khi thực sự sẽ có thể thay đổi dung lượng, và khả năng biến đổi dung lượng cũng biến thiên theo thời gian, thì việc quyết định luồng sẽ được chấp nhận không phải là một vấn đề đáng kể. Trong thực tế một hệ thống làm việc theo con đường sau: người sử dụng thông báo các giá trị với một số thông số mô tả hoạt động lưu lượng của luồng được yêu cầu, cũng như yêu cầu hiệu năng trễ và mất mát; mạng khi đó sử dụng các giá trị lưu lượng và hiệu năng này để đưa tới một quyết định chấp nhận/từ chối, và hồi âm cho người sử dụng. Nếu chấp nhận, mạng phải đảm bảo rằng chuỗi các gói tương ứng với các giá trị lưu lượng được thông báo. Toàn bộ quá trình này thực hiện tại tình trạng tắc nghẽn phòng ngừa trong mạng và đảm bảo rằng những yêu cầu hiệu năng được nhìn thấy cho tất cả lưu lượng được mang. Các giá trị lưu lượng và hiệu năng được đồng ý bởi người sử dụng và mạng tạo thành một hợp đồng lưu lượng. Phương thức tạo quyết định chấp nhận/từ chối là khả năng điều khiển chấp nhận, và điều này tập trung trong các bộ định tuyến IP trong mạng. Cần thiết có một phương thức để đảm bảo tuân theo hợp đồng lưu lượng, nói cách khác người sử dụng không nên vượt quá tốc độ đỉnh (hoặc có nghĩa, hoặc tốc độ) đã được đồng ý cho luồng. Phương thức này được gọi là điều khiển thông số sử dụng (UPC – Usage Parameter Control) [TK1.trang 167], và nó thực hiện đo, đánh dấu và huỷ gói. 2.2. CÁC VẤN ĐỀ VỚI MẠNG IP 2.2.1. Trễ và mất mát Trong các mạng gói, hoạt động cơ bản ảnh hưởng đến hiệu năng là hoạt động xếp hàng của các gói truyền qua các bộ đệm trong các router trên đường truyền từ nguồn đến đích qua mạng. Hoạt động xếp hàng này có nghĩa là các gói phải trải qua những biến thiên độ trễ qua một bộ đệm và, nếu độ trễ đó quá lớn, thì sẽ bị mất. Trường hợp đơn giản nhất, một bộ đệm có tốc độ phục vụ cố định, một dung lượng cho việc lưu trữ tạm thời các gói đang chờ được phục vụ, và một quy tắc phục vụ FIFO. Ngay cả trong trường hợp đơn giản này, hoạt động xếp hàng cũng tuỳ thuộc vào kiểu và hỗn hợp lưu lượng đang được ghép qua bộ đệm. 2.2.2. Các yêu cầu đa dịch vụ: đòi hỏi những hiệu năng khác nhau Một nguyên tắc FIFO không cho phép mạng đảm bảo những đòi hỏi hiệu năng khác nhau – trong IP nỗ lực tốt nhất tất cả lưu lượng đều phải trải qua độ trễ và mất mát như nhau. Giải pháp cho vấn đề này là quản lý bộ đệm, cả lối vào và lối ra – điều này bao hàm các chính sách phân vùng và chia sẻ không gian bộ đệm cũng như dung lượng phục vụ (ví dụ như xếp hàng theo luồng), các phương thức loại bỏ gói, và lập lịch hàng đợi (như xếp hàng theo quyền ưu tiên và xếp hàng trọng số hợp lý). Chia sẻ và phân vùng bộ đệm: Với xếp hàng theo luồng và xếp hàng trọng số hợp lý, mỗi bộ đệm ảo có thể được thiết lập mô hình như là có dung lượng phục vụ và không gian bộ đệm của riêng nó – do đó bất kỳ phương thức phân tích cho các hàng đợi FIFO nào cũng có thể được áp dụng, như thích hợp với bối cảnh ghép, và các nguồn lưu lượng. Điển hình, điều này sẽ đưa ra một tốc độ phân rã cho mỗi bộ đệm ảo, khi đó có thể được sử dụng, cùng với yêu cầu hiệu năng, để đánh giá quá trình phân vùng không gian bộ đệm. Việc phân vùng có một ưu điểm rõ ràng là duy trì những đảm bảo hiệu năng khác nhau với các loại hình dịch vụ phong phú đang chia sẻ một cổng lối ra. Tuy nhiên, cái giá của quá trình phân vùng là nó không tối ưu khi xem xét tình trạng mất mát tổng tại một cổng đầu ra: sự mất mát của một gói từ bộ đệm ảo đầy có thể không cần thiết nếu không gian bộ đệm được chia sẻ. Thực sự, không gian bộ đệm có thể được chia sẻ qua nhiều cổng đầu ra. Các phương thức loại bỏ gói: Trong IP, RED cung cấp một phương thức loại bỏ mang tính xác suất với mục đích là làm dịu bớt tình trạng tắc nghẽn, và ngăn ngừa nó nếu có thể – xác định các vấn đề đồng bộ toàn thể kết hợp với các kết nối TCP. RED còn sử dụng một phương thức ngưỡng làm việc kết hợp với kích cỡ hàng đợi trung bình. Các phương thức lập lịch hàng đợi: Trong IP, các phương thức lập lịch hàng đợi bao gồm việc phân vùng dung lượng phục vụ của bộ đệm đầu ra. Xếp hàng trọng số hợp lý chỉ định từng phần bộ phục vụ cụ thể cho mỗi bộ đệm ảo – để phân tích điều này, mỗi bộ đệm có thể được xem xét như một hàng đợi FIFO độc lập với một dung lượng phục vụ cố định bằng với dung lượng được chỉ định của nó. Do vậy bất kỳ phương pháp phân tích nào với các hàng đợi FIFO đều có thể được áp dụng. Xếp hàng theo quyền ưu tiên, tức là ưu tiên thời gian, yêu cầu phân tích cụ thể, bởi vì các phần dung lượng phục vụ giữa những mức ưu tiên khác nhau là không cố định. Dung lượng phục vụ dành cho các mức ưu tiên thấp sẽ phụ thuộc vào việc đã có bao nhiêu dung lượng phục vụ được sử dụng cho các lưu lượng ưu tiên cao hơn. 2.2.3. Vấn đề nhiều loại hình lưu lượng Để cung cấp những đảm bảo hiệu năng end-to-end, các hợp đồng lưu lượng phải được thiết lập, dự phòng tài nguyên, và giám sát các luồng lưu lượng để đảm bảo theo đúng hợp đồng. Tại trung tâm của những chức năng này là sự quyết định kết quả hiệu năng từ những luồng lưu lượng qua các tài nguyên mạng, tức là những định dạng phân tích xếp hàng khác nhau. Các phương thức điều khiển truy cập: Trong IP, một chức năng điều khiển truy cập phải quyết định xem một luồng mới có được truy nhập hay không. Chức năng này phải ghi chép những lời cam kết rằng mạng hiện đang hỗ trợ và các tài nguyên hợp lệ với các luồng mới bất kỳ. Để làm được điều này, cần phải hiểu kiến trúc và cấu hình của các bộ đệm (tức là các phương thức lập lịch loại bỏ và phân vùng), và tạo ra một sự quyết định thích hợp có đảm bảo hiệu năng được yêu cầu hay không. Điều này đòi hỏi phân tích xếp hàng. Các phương thức lập chính sách: Mỗi lần truy nhập, luồng các gói sẽ được giám sát (để đảm bảo theo đúng hợp đồng lưu lượng) bằng chức năng lập chính sách, thường là một gáo dấu hiệu, hoặc gáo rò [TK1.trang 172]. Trong IP, gáo dấu hiệu được tích hợp một cách đặc trưng vào trong phương thức lập lịch hàng đợi. Nó có thể được đánh giá bằng cách sử dụng những kiểu phân tích xếp hàng phong phú, để biết cách thức cấu hình các gáo thích hợp. Quá trình xác định kích thước và cấu hình: Trên phương diện thời gian dài hơn, việc dự phòng, xác định kích thước và cấu hình các tài nguyên mạng (những liên kết truyền dẫn, phân vùng bộ đệm, dung lượng chuyển mạch,…) đều cần thiết để tương thích yêu cầu mà người sử dụng mong muốn. Điều này cũng tạo ra việc sử dụng phân tích xếp hàng để quyết định xác suất nghẽn và tắc tại mức kết nối, hoặc mức kết hợp. 2.3. NGUYÊN TẮC XẾP HÀNG Những phân tích về quá trình xếp hàng là một phần cơ bản của đánh giá hiệu năng, bởi vì các hàng đợi (hay “các đường đợi”) hình thành trong các hệ thống viễn thông mỗi khi các khách hàng tranh chấp những nguồn tài nguyên giới hạn. Trong mạng IP không chỉ thực hiện tranh chấp các kết nối, và có thể tạo ra hàng đợi, mà mỗi kết nối được chấp nhận bao gồm một dòng các gói và chúng còn phải đợi tại những bộ định tuyến khi chúng đi ngang qua mạng. Chúng ta sẽ sử dụng một hàng đợi như một quá trình xử lý toán học nhanh ý tưởng của sự tranh chấp tài nguyên (Hình 2.1): các khách hàng đi đến một hệ thống xếp hàng cần một số lượng dịch vụ xác định, nếu nó không được phép ngay thì chúng sẽ đợi được phục vụ, trong một khu vực lưu giữ (được gọi là một “bộ đệm”, “hàng đợi” hay “đường đợi”); và chờ đợi một khoảng thời gian xác định, chúng được phục vụ và rời khỏi hệ thống. Chú ý rằng thuật ngữ “khách hàng” là sự mô tả chung mà chúng ta sẽ bắt gặp trong vấn đề nguyên tắc xếp hàng và nó được sử dụng để giải nghĩa “các đường đợi bất kỳ đó”; trong IP, khách hàng có thể là các gói, các cụm, các luồng hoặc các kết nối. Một hệ thống xếp hàng bất kỳ được mô tả bởi những kiểu đi đến của khách hàng, những kiểu dịch vụ của khách hàng, số lượng kênh phục vụ, và dung lượng phục vụ. Kiểu đi đến của các khách hàng là đầu vào tới một hệ thống xếp hàng và đôi khi có thể được chỉ rõ như số lượng trung bình của các gói đi đến trên một đơn vị thời gian (nghĩa là thời gian liên đi đến). Đầu vào đơn giản nhất cho hệ thống xếp hàng bất kỳ có thể có là “quyết định” (deterministic), trong kiểu đi đến là một khách hàng trên mọi t đơn vị thời gian, nói cách khác, tốc độ đi đến là 1/t. Không mất tính tổng quát, chúng ta xem xét một kích cỡ gói IP bằng với một tế bào ATM. Như vậy, với dịch vụ tốc độ bit cố định (CBR) 64 kb/s, khi đó tốc độ gói là 167 gói/s, và thời gian liên đi đến là 6 ms. Nếu kiểu đi đến là “ngẫu nhiên” (tức là nó biến đổi trong một số kiểu ngẫu nhiên theo thời gian), thì yêu cầu một quá trình mô tả sâu hơn, ví dụ sự phân bố xác suất của thời gian giữa những lần đi đến. Những lần đi đến có thể là một nhóm thay vì đơn lẻ, và kích cỡ của những nhóm này có thể biến đổi. Kiểu dịch vụ của khách hàng, như với các kiểu đi đến, có thể được mô tả như tốc độ, µ, của các khách hàng đang được phục vụ, hoặc như một thời gian, s, đòi hỏi để phục vụ một khách hàng. Có một điểm khác biệt quan trọng: thời gian phục vụ hoặc tốc độ phục vụ được đặt điều kiện trên hệ thống là không rỗng. Nếu nó rỗng, trạng thái dịch vụ được gọi là “rỗi”. Tuy nhiên, khi một bộ đệm IP rỗng, một dòng kế tiếp của khe gói rỗng được xuất phát. Do đó, sự phục vụ được đồng bộ và quyết định. Trong phân tích toán học của một bộ đệm IP, quá trình đồng bộ thường bị bỏ quên – do đó một gói được cho rằng truy cập dịch vụ ngay lập tức nhanh chóng tới truy cập vào một bộ đệm rỗng. Đối với một liên kết 155.52 Mb/s, tốc độ khe gói là 366792 gói/s và thời gian phục vụ mỗi gói là 2.726 µs. Tuy nhiên, một trong tổng số 27 khe gói được sử dụng cho vận hành và bảo dưỡng (OAM) các gói cho những nhiệm vụ hiển thị và đo đạc phong phú. Bởi vậy tốc độ khe gói có giá trị cho lưu lượng là gói/s Có thể được lấy gần đúng như một thời gian phục vụ cho mỗi gói bằng 2.831 µs. Số lượng kênh phục vụ nói đến số lượng bộ phục vụ có thể phục vụ lần lượt khách hàng. Những hệ thống đa kênh có thể khác tuỳ theo sự tổ chức của hàng đợi: mỗi bộ phục vụ có thể có hàng đợi riêng, hoặc có thể chỉ một hàng đợi cho tất cả các bộ phục vụ. Đây là trường hợp thú vị đặc biệt khi phân tích các thiết kế chuyển mạch IP khác nhau. Dung lượng hệ thống bao gồm khu vực chờ đợi và số lượng kênh phục vụ, và có thể là giới hạn hoặc vô hạn. Rõ ràng trong một hệ thống thực tế, dung lượng phải là giới hạn. Tuy nhiên giả thiết dung lượng vô hạn có thể đơn giản hoá được quá trình phân tích và vẫn có giá trị trong mô tả hoạt động xếp hàng IP. 2.3.1. Hệ thống ký hiệu Hệ thống ký hiệu Kendall, A/B/X/Y/Z được sử dụng rộng rãi để mô tả các hệ thống xếp hàng: A chỉ ra phân bố thời gian liên đi đến B chỉ ra phân bố thời gian phục vụ X chỉ ra số lượng kênh phục vụ Y chỉ ra dung lượng hệ thống, và Z chỉ ra nguyên tắc hàng đợi Một ví dụ là hàng đợi M/D/1. Ở đây “M” nói đến một quá trình không nhớ (memoryless), hay Markov [TK2.trang 28], nói cách khác là những thời gian liên đi đến với phân bố số mũ âm. “D” nghĩa là thời gian phục vụ luôn tương đương: cố định hoặc “quyết định” (từ giờ là D), và “1” nói đến phục vụ riêng lẻ. Phần Y/Z của hệ thống ký hiệu được bỏ qua khi dung lượng hệ thống bị hạn chế và nguyên tắc hàng đợi là vào trước-phục vụ trước 2.3.2. Những mối quan hệ cơ bản Bảng 3.1 tóm tắt hệ thống ký hiệu được sử dụng chung cho những thành phần khác nhau của tiến trình xếp hàng. Hệ thống ký hiệu này không được chuẩn hoá, vậy cần chú ý… ví dụ, q có thể được sử dụng, hoặc theo nghĩa là số lượng khách hàng trung bình của hệ thống, hoặc là số lượng khách hàng trung bình chờ đợi phục vụ (trừ các trạng thái khác, chúng ta sẽ sử dụng nó theo nghĩa là số lượng khách hàng trung bình trong hệ thống). Thực tế có một số mối quan hệ xếp hàng cơ bản, giả thiết rằng dung lượng hệ thống là “vô hạn”, nhưng không quan tâm tới những kiểu đi đến hay kiểu phục vụ và số lượng kênh hay nguyên tắc hàng đợi. Độ sử dụng, r, là kết quả của tốc độ đi đến có nghĩa và thời gian phục vụ trung bình, tức là r = l. s cho một hàng đợi với bộ phục vụ đơn lẻ. Với 1000 nguồn CBR 64 kb/s, tốc độ đi đến là 166 667 gói/s. Chúng ta đã tính toán được rằng thời gian phục vụ của một gói là 2.831 µs, vậy độ sử dụng, r, là 0.472. Số lượng khách hàng trung bình trong hàng đợi được liên hệ với thời gian trung bình bỏ ra để chờ đợi trong hàng đợi theo một công thức được gọi là công thức của Little (thường viết tắt là L = l.W ) [TK2.trang 43]. Trong bảng ký hiệu của chúng ta, đây là Vậy, nếu thời gian chờ trung bình là 50 µs, thì chiều dài hàng đợi trung bình là 8.333 gói. Quan hệ này cũng áp dụng cho số lượng khách hàng trung bình trong hệ thống Thời gian trung bình trong hệ thống đơn giản bằng tổng của thời gian phục vụ trung bình và thời gian chờ trung bình, tức là Trong thí dụ này, đưa ra một giá trị là 52.831 µs. Số lượng khách hàng trung bình trong một hệ thống bộ phục vụ đơn lẻ được tính bằng đưa ra một giá trị là 8.805 gói. 2.3.3. Hàng đợi M/M/1 Chúng ta có thể tiếp tục với ví dụ của N nguồn CBR cung cấp một bộ đệm IP bằng cách tạo ra hai giả định, nhưng ví dụ ít nhất sẽ đưa ra cho chúng ta một bối cảnh để lựa chọn những giá trị thông số biến đổi. Giả định thứ nhất là kiểu đi đến của gói từ N nguồn CBR có thể được lấy gần đúng bằng những thời gian liên đi đến với số mũ âm. Điều này cũng tương tự khi nói rằng những lần đi đến được mô tả bởi quá trình Poisson [TK2.trang 20]. Quá trình này đã nhìn vào kiểu đi đến từ một bối cảnh khác. Thay vì chỉ rõ một khoảng thời gian, phân bố Poisson đếm số lần đi đến trong một khoảng thời gian. Giả định thứ hai là những thời gian phục vụ của các gói này được mô tả bằng một phân bố số mũ âm. Trong mạng IP với những gói