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

không thực tế trên một mạng với 16 triệu host. Giải pháp thực tế duy nhất là phân chia không gian địa chỉ nào đó bên dưới mức định danh mạng để các host và các router có thể dựa trên địa chỉ IP để cho biết đoạn mạng nào có thể nhận phân phối. Các công nghệ trong mạng IP cung cấp một cấp tổ chức luận lý thứ hai bên dưới định danh mạng thông qua một khái niệm được gọi là subnet. Một subnet (mạng con) là một phân chia luận lý không gian địa chỉ mạng. Các router có thể phân phối một datagram đến một địa chỉ subnet trong mạng (thường tương ứng với một đoạn mạng), và một khi datagram đến subnet, nó có thể được phân giả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 có độ dài không cố định, chúng ta có thể sử dụng ví dụ này để minh hoạ một số điểm quan trọng về các hệ thống xếp hàng. Như vậy, chúng ta nên tạo ra bộ đệm IP lớn như thế nào. Nhớ lại rằng hệ thống xếp hàng M/M/1 giả thiết không gian bộ đệm là vô hạn, nhưng chúng ta có thể có một số ý tưởng bằng cách xem xét số lượng gói trung bình trong hệ thống, được tính bằng Trong ví dụ của chúng ta, kết quả độ sử dụng từ 1000 nguồn CBR là 0.472 đưa ra một kích cỡ hệ thống trung bình là 0.894 gói. Trừ đi độ sử dụng từ đây cho ta không gian đợi trung bình được sử dụng, 0.422 gói. Đây không phải là kết quả quá hữu ích cho việc xác định kích thước của một bộ đệm IP; chúng ta sẽ mong muốn cung cấp không gian chờ vượt quá tối thiểu một gói. Nhưng nếu chúng ta nhìn vào đồ thị (Hình 2.2) của q và r, khi r biến thiên từ 0 đến 1, thì chúng ta có thể vẽ một kết quả rất hữu ích. Đặc trưng then chốt là đoạn uốn cong quanh độ sử dụng 80% đến 90%, đưa ra rằng tốt nhất là vận hành hệ thống dưới 80% (độ sử dụng) để ngăn ngừa những hàng đợi rộng lên. Nhưng chúng ta vẫn chưa có bất kỳ ý tưởng gì về độ rộng của bộ đệm IP. Bước kế tiếp là xem xét sự phân bố của kích cỡ hệ thống như được tính: Pr{kích cỡ hệ thống = x} = (1 – r).rx Hình 2.3 chỉ ra phân bố này cho một phạm vi các giá trị độ sử dụng khác nhau, bao gồm giá trị 0.472 trong ví dụ riêng của chúng ta. Trong trường hợp này chúng ta có thể đọc ra từ đồ thị xác suất được liên kết với một kích cỡ hệ thống 10 gói là 0.0003. Từ đây chúng ta có thể kết luận rằng một độ dài bộ đệm 10 gói sẽ không đủ để đạt được những yêu cầu xác suất mất gói của IP ở mức 10-8. Cho xác suất kích cỡ hệ thống xuống dưới 10-8, kích cỡ hệ thống cần thiết là 24 gói; xác suất thực sự là 7.89 × 10-9. Trong quá trình đưa ra sự diễn dịch này, chúng ta đã tính gần đúng xác suất mất gói bằng xác suất để bộ đệm đạt đến một giới hạn đặc biệt trong kiểu bộ đệm vô hạn của chúng ta. Điều này giả thiết rằng một mẫu bộ đệm vô hạn là một kiểu thích hợp của bộ đệm giới hạn, và Pr{kích cỡ hệ thống = x) là một xấp xỉ hợp lý cho sự mất mát từ một hàng đợi giới hạn có kích cỡ x. Trước khi rời khỏi M/M/1, chúng ta nhìn vào một sự xấp xỉ khác cho tính tổng các xác suất có thể xảy ra cho đến và bao gồm giá trị x, và khi đó lấy 1 trừ đi tổng này (đây là công việc đơn giản hơn so với tính tổng từ x +1 đến ∞). Phương trình cho nó rất đơn giản Pr{kích cỡ hệ thống > x} = rx + 1 Khi x = 24, và r = 0.472, phương trình này sẽ đưa ra kết quả 7.06 × 10-9 rất gần với ước lượng trước đó. Bây giờ nhìn Hình 2.4 so sánh kết quả hai phương pháp xấp xỉ. Pr{kích cỡ hệ thống = x} và Pr{kích cỡ hệ thống ≥ x}, với xác suất mất mát thực tế từ hệ thống M/M/1/K, cho kích cỡ hệ thống là 24 gói, với độ sử dụng biến thiên từ 0 đến 1. Cái chúng ta tìm thấy là tất cả ba phương pháp đưa ra những kết quả giống nhau theo hầu hết các giá trị độ sử dụng là 47.2% (0.472), thì sự khác nhau thực tế là rất ít. Điểm chính cần chú ý ở đây là một hàng đợi vô hạn có thể cung cấp một phương pháp lấy xấp xỉ hiệu quả cho một hàng đợi giới hạn. 2.3.4. Hàng đợi M/D/1/K Vậy bây giờ để chỉnh sửa giả định thứ hai, về những thời gian phục vụ, và thay vì được mô tả bởi một phân bố số mũ âm, chúng ta sẽ xây dựng mô hình các gói. Giả thiết duy nhất chúng ta sẽ đưa ra bây giờ là chúng truy nhập dịch vụ bất cứ khi nào bộ phục vụ rỗi, tốt hơn là chờ đến khe gói tiếp theo. Giả định đầu tiên, về những thời gian đi đến, giữ tương tự như trước. Chúng ta sẽ xử lý trực tiếp với một hàng đợi giới hạn, hơn là coi gần đúng nó như một hàng đợi vô hạn. Điều này, khi đó, được gọi là hệ thống xếp hàng M/D/1/K. Hình 2.5 so sánh độ mất mát gói từ M/D/1/K với ước lượng xác suất mất gói M/M/1, Pr{kích cỡ hệ thống = x}, khi kích cỡ hệ thống là 10. Như trước, phạm vi của độ sử dụng là từ 0 đến 1. Tại độ sử dụng thích hợp, 0.472, sự khác biệt giữa kết quả mất gói là về hai sự sắp xếp mức độ quan trọng. Như vậy chúng ta cần nhớ rằng “những câu trả lời” đánh giá hiệu năng có thể nhạy cảm hơn để lựa chọn mẫu, và biện pháp chúng ta sẽ luôn luôn, với một số phạm vi, mở ra thảo luận. Với xác suất mất gói trong M/D/1/K nhỏ hơn 10-8, kích cỡ hệ thống cần phải ít nhất là 15 gói, và xác suất mất gói thực tế (nếu là 15 gói) bằng 4.34 × 10-9. Vậy, bằng cách sử dụng mẫu hệ thống chính xác hơn (so với M/M/1), chúng ta có thể tiết kiệm được không gian bộ nhớ thiết kế, hoặc như một sự lựa chọn, nếu chúng ta sử dụng một kích cỡ hệ thống là 24 gói, thì độ sử dụng có thể được tăng lên 66.8%, chính xác hơn so với 47.3%. Sự gia tăng này tương ứng với thêm lần lượt là 415 kết nối CBR 64 kb/s. Nó cũng có một chú ý không được tốt trong Hình 2.5 là các xác suất mất gói rất gần nhau khi độ sử dụng cao, có nghĩa là sự khác biệt giữa hai kiểu, với những giả thiết thời gian phục vụ rất khác nhau của chúng trở nên hầu như không đáng kể dưới những điều kiện lưu lượng nghiêm ngặt. 2.3.5. Trễ trong các hệ thống xếp hàng M/M/1 và M/D/1 IP nêu bật cả mất mát gói và trễ gói như những phép đo hiệu năng then chốt, và cho đến nay chúng ta chỉ xem xét được mất mát. Tuy nhiên, độ trễ quan trọng đặc biệt cho các dịch vụ thời gian thực, ví dụ như thoại và video. Kết quả của Little cho phép chúng ta tính toán thời gian chờ trung bình từ số lượng trung bình đang chờ trong hàng đợi và tốc độ đi đến. Nếu chúng ta ứng dụng phân tích này cho ví dụ với 1000 kết nối CBR được ghép cùng nhau, chúng ta sẽ đạt được: Thời gian trung bình trong hệ thống là tq = tw + s = 2.532 + 2.831 = 5.363 µs Cách khác để đạt được cùng kết quả là sử dụng công thức thời gian chờ đợi cho hàng đợi M/M/1. Đó là tw = Với hàng đợi M/D/1, có một công thức thời gian chờ tương tự tw = Trong cả hai trường hợp chúng ta đều cần cộng thêm thời gian phục vụ (thời gian truyền dẫn gói) để đạt được độ trễ tổng qua hệ thống. Nhưng điều chỉnh cần chú ý là thời gian chờ trung bình trong hàng đợi M/D/1 (làm việc ngoài như 1.265 µs trong ví dụ của chúng ta) là bằng “một nửa” của hàng đợi M/M/1. Hình 2.6 chỉ ra thời gian chờ trung bình theo độ sử dụng cho cả hai kiểu hàng đợi. Đường thẳng chỉ ra thời gian phục vụ trung bình. Chú ý cách thức nó vượt độ trễ với độ sử dụng 60%. Chúng ta có thể giữ như một “quy luật lật trang sách” hữu ích mà trễ trung bình phát sinh từ việc xếp hàng qua một mạng sẽ được tính xấp xỉ hai lần tổng của các thời gian phục vụ. Điều này giả thiết, tất nhiên, rằng độ sử dụng trong bất kỳ hàng đợi nào sẽ không lớn hơn 60%. Đối với độ trễ end-to-end cuối cùng, chúng ta phải cộng thêm thời gian nhân lên ở những liên kết truyền dẫn. Những thông số này có giá trị, nhưng nếu giữ ở một mình, thì chúng sẽ là không đầy đủ. Chúng ta nên nhớ rằng chúng là những giá trị trung bình, và các gói sẽ ảnh hưởng trễ thực sự cả lớn hơn và nhỏ hơn. Trễ là đặc biệt quan trọng khi chúng ta xem xét các đặc trưng end-to-end của các kết nối; tất cả các gói trong một kết nối sẽ phải đi qua một chuỗi bộ đệm, mỗi bộ đệm sẽ làm trễ chúng bằng một số ngẫu nhiên tuỳ số lượng gói đã ở trong bộ đệm đi đến. Điều này chắc chắn sẽ làm các gói bị trễ hơn, do đó có thể gọi là trượt trễ, hay biến động trễ. Minh hoạ bằng hình vẽ được chỉ ra ở Hình 2.7. Ở đây, chúng ta chỉ đưa ra các gói của kết nối mà chúng ta giám sát; tất nhiên cũng có lưu lượng khác được đóng góp vào bộ đệm. Gói thứ hai trải qua độ trễ ngắn hơn so với gói đầu tiên và gói thứ ba. Điều này cung cấp một kích thước nhỏ hơn giữa gói 1 và 2, và dài hơn giữa gói 2 và 3. Sự biến thiên độ trễ có thể là một vấn đề đặc biệt cho điều khiển thông số sử dụng [TK1.trang 167]. Vậy để minh hoạ, cho một ví dụ cụ thể. Nếu chúng ta lại sử dụng ví dụ CBR (1000 nguồn CBR 64 kb/s được ghép với nhau), chúng ta có thể sử dụng nhiều nguyên tắc hơn kết hợp với hàng đợi M/D/1 để dự đoán kết quả đi qua của dòng gói này qua một sự thành công của các hàng đợi tương đương, và vẽ đồ thị phân bố thời gian chờ kết quả. Các xác suất kết hợp với một gói trong luồng sẽ bị trễ x khe thời gian đã truyền qua 1, 2, 3 và 10 bộ đệm tương tự được chỉ ra trong Hình 2.8. Để đưa ra được những kết quả này, chúng ta giả thiết rằng mỗi bộ đệm là độc lập với tất cả các bộ đệm còn lại, và chúng được tải tại 0.472. Các kết quả được chỉ ra rõ ràng có xu hướng cho phân bố trễ sẽ san bằng khi số lượng các bộ đệm tăng như bạn có thể mong đợi. Nhiều bộ đệm hơn và nhiều gói đi qua hơn, thì xác suất liên kết với thời gian chờ dài và thời gian chờ ngắn có chiều hướng bằng nhau. 2.4. CÁC THÔNG SỐ LƯU LƯỢNG 2.4.1. Các mức của hoạt động lưu lượng Vậy thì loại hình hoạt động lưu lượng nào mà chúng ta sẽ quan tâm trong IP. Chúng ta có thể thấy trong một mạng IP, thời gian giữa những “gói đi đến” được đưa ra như một phân bố số mũ âm: điều đó để nói rằng, những sự đi đến đã định dạng một quá trình Poisson [TK2.trang 20]. Tuy nhiên mặc dù cùng một mẫu nguồn được sử dụng, nhưng có thể lại là các loại hoạt động khác nhau đang được sử dụng. Người ta xem xét các kiểu hoạt động khác nhau này thông qua bốn khía cạnh thời gian khác nhau của hoạt động được chỉ ra trên Hình 2.9. Calendar (lịch): những sự biến đổi hàng ngày, hàng tuần và theo mùa. Connection (kết nối): thiết lập và giải quyết những sự kiện quy định trong phạm vi khoảng thời gian kết nối, điển hình là trong khoảng 100 đến 1000 giây. Burst (cụm): hoạt động của một người sử dụng phát, điển hình như một tốc độ luồng gói, qua một khoảng thời gian giới hạn từ một phần nhỏ của giây đến một vài giây. Packet (gói): hoạt động của việc phát gói tại mức thấp nhất, liên quan đến khoảng thời gian giữa những sự đi đến. Phân tích hoạt động lưu lượng này giúp ích trong việc phân biệt những mục tiêu chủ yếu của quá trình xác định kích thước và thiết kế hiệu năng. Xác định kích thước tập trung vào việc tổ chức và cung cấp đầy đủ thiết bị trong mạng để thấy sự cần thiết trong các dịch vụ được sử dụng bởi thuê bao (tức là các mức lịch và kết nối); nó đòi hỏi hiểu biết về những đặc trưng dịch vụ, nhưng điều này là trong định dạng tổng và không cần thiết một mức độ chi tiết cao. Thiết kế hiệu năng, tuy nhiên, lại tập trung chi tiết vào các giới hạn của hiệu năng, điều này đòi hỏi quá trình xem xét chi tiết các thông số đặc trưng dịch vụ (chủ yếu tại các mức gói và cụm), cũng như thông tin về hỗn hợp dịch vụ điển hình – bao nhiêu lưu lượng thoại, video và dữ liệu đang được vận chuyển trong liên kết bất kỳ (mà sẽ đạt được từ việc nghiên cứu các dịch vụ sử dụng). Thông tin định thời trong các mẫu nguồn Một mẫu nguồn mô tả cách thức lưu lượng, hoặc các gói, các cụm hoặc các kết nối, xuất phát từ một người sử dụng. Như chúng ta đã thấy, cùng một mẫu nguồn có thể được áp dụng cho những khía cạnh thời gian khác nhau của hoạt động, nhưng quá trình Poisson không chỉ được áp dụng cho IP. Các mẫu nguồn có thể được xếp lớp theo những cách khác nhau: thời gian liên tục hoặc thời gian riêng, thời gian liên đi đến hoặc quá trình đếm, dựa trên trạng thái hoặc dựa theo phân bố. Có một điều đáng chú ý là một số mẫu được liên kết với một phương pháp xây dựng hàng đợi đặc biệt, một ví dụ đang được phân tích luồng không cố định. Một đặc trưng để phân biệt các nguồn là cách trình diễn thông tin định thời. Hình 2.10 chỉ ra ba cách khác nhau với ví dụ một luồng gói IP: như là số lượng khe gói giữa những sự đi đến (những thời gian liên đi đến là 5, 7, 3 và 5 khe trong ví dụ này); như là một quá trình đếm số lượng gói đi đến trong vòng một chu kỳ điển hình (ở đây, là 5 gói trong 25 khe gói); và như một tốc độ gói, trong trường hợp này là 20% của tốc độ khe gói. 2.4.3. Thời gian giữa những lần đi đến Những thời gian liên đi đến có thể được chỉ rõ bằng một giá trị cố định, hoặc một số giá trị phân bố xác suất tuỳ ý, cho thời gian giữa những lần đi đến thành công (các kết nối). Những giá trị này có thể trong thời gian liên tục, tạo ra bất kỳ giá trị thực tế nào, hoặc trong thời gian riêng, ví dụ như một tổ hợp ghép số tự nhiên của một chu kỳ thời gian riêng như thời gian truyền dẫn của một gói, ví dụ 2.831 µs. Một phân bố số mũ âm của thời gian liên đi đến là ví dụ căn bản của một quá trình thời gian liên tục do thuộc tính không nhớ [TK2.trang 28]. Cái tên này xuất hiện từ thực tế rằng, nếu thời gian từ t1 ® t2 là không phụ thuộc vào khoảng cách, dt, từ lần đi đến cuối cùng (Hình 2.11). Thuộc tính này cho phép phát triển một số công thức đơn giản cho hàng đợi. Xác suất để thời gian liên đi đến nhỏ hơn hoặc bằng t được tính theo công thức: Pr{thời gian liên đi đến ≤ t) = F(t) = 1 – e–λ.t với tốc độ đi đến là l. Phân bố này, F(t), được chỉ ra ở Hình 2.12 cho một tải trọng bằng 47.2% (tức là ví dụ nguồn CBR 1000). Tốc độ đi đến là 166 667 gói/s tương ứng với một thời gian liên đi đến bằng 6 µs. Khe gói đi đến còn được chỉ ra tất cả 2.831 µs trên trục thời gian. Thời gian riêng [TK2.trang 275] tương đương với việc có một số phân bố hình học của các khe thời gian giữa những lần đi đến (Hình 2.13), với số lượng đó được đếm từ điểm cuối của gói đầu tiên đến điểm cuối của gói đi đến tiếp theo. Rõ ràng một tốc độ gói bằng 1 gói/khe thời gian có một thời gian liên đi đến là một khe gói, tức là không có khe gói rỗng giữa những lần đi đến. Xác suất để một khe gói chứa một gói là không đổi, và chúng ta có thể gọi là p. Từ đó một khe gói rỗng với xác suất 1 – p. Xác suất để có k khe thời gian giữa những lần đi đến được tính: Pr{k khe thời gian giữa những lần đi đến} = (1 – p)k-1.p tức là k – 1 khe thời gian rỗng, sau đó là một khe thời gian đầy. Đây là phân bố hình học, thời gian riêng tương đương với phân bố số mũ âm. Phân bố hình học [TK2.trang 282] thường được giới thiệu trong những cuốn sách theo kiểu tung súc sắc hay đồng tiền, từ đó nó được nghĩa rằng như có k – 1 “thất bại” (những khe thời gian rỗng), sau đó đến một “thành công” (một lần đi đến của gói). Phân bố có nghĩa là nghịch đảo xác suất thành công, tức là 1/p. Lưu ý rằng phân bố hình học còn có một thuộc tính không nhớ trong đó giá trị p cho khe thời gian n được giữ không đổi tuy có rất nhiều sự đi đến trong n – 1 khe thời gian trước. Hình 2.14 so sánh phân bố hình học và phân bố số mũ âm với tải trọng 47.2% (có nghĩa là cho phân bố hình học, ρ = 0.472, với một cơ sở thời gian bằng 2.831 µs; và cho phân bố số mũ âm, l = 166 667 gói/s, như trước). Chúng sẽ là những phân bố tích luỹ (Hình 2.12), và chúng đưa ra xác suất để thời gian liên đi đến nhỏ hơn hoặc bằng với giá trị xác định trước trên trục thời gian. Trục thời gian này được chia nhỏ vào các khe gói với sự so sánh đơn giản. Phân bố hình học tích luỹ ban đầu tại khe thời gian k = 1 và cộng thêm Pr{k khe thời gian giữa những lần đi đến} cho mỗi giá trị tiếp theo của liên kết Pr{≤ k khe thời gian giữa những lần đi đến} = 1 – (1 – p)k 2.4.4. Đếm số lần đi đến Một cách lựa chọn trình diễn thông tin định thời về một quá trình đi đến là bằng cách đếm số lần đi đến trong một khoảng thời gian được định nghĩa. Ở đây có một sự tương đương với phương thức thời gian liên đi đến trong thời gian liên tục: những thời gian liên đi đến được phân bố số mũ âm tạo thành một quá trình Poisson: Pr{k lần đi đến trong thời gian T} = với l là tốc độ đi đến. Trong thời gian riêng, những thời điểm liên đi đến hình học định dạng một quá trình Bernoulli [TK2.trang 280], với xác suất để một lần đi đến trong một khe thời gian là p và xác suất để không có sự đi đến nào trong khe thời gian là 1 – p. Nếu chúng ta xem xét nhiều hơn một khe thời gian, thì số lượng đi đến trong N khe thời gian được phân bố nhị thức [TK2.trang 284]. Pr{k lần đi đến trong N khe thời gian} = và p là số lần đi đến trung bình trên khe thời gian. Vậy những phân bố này được sử dụng để hình thành các hệ thống IP như thế nào. Xem xét ví dụ về một nguồn IP đang phát những gói đến như một quá trình Poisson; các gói khi đó được lưu đệm, và được phát một cách thường xuyên cho IP – như một dòng gói trong các khe đồng bộ (xem Hình 2.15). Quá trình Poisson trình diễn những gói đi đến từ nguồn tới bộ đệm, tại tốc độ gói là l gói/khe thời gian. Tại đầu ra của bộ đệm, một gói chiếm khe thời gian i với xác suất p như chúng ta đã định nghĩa trước đó cho quá trình Bernoulli. Bây giờ nếu l là tốc độ gói đi đến và p là tốc độ gói đi ra, (cả hai đều trong giới hạn bởi số gói trên khe thời gian), và nếu chúng ta không mất bất kỳ gói nào trong bộ đệm (vô hạn), thì chúng ta phải có l = p. Lưu ý rằng quá trình đầu ra của một bộ đệm IP với độ dài vô hạn, được cung cấp bởi nguồn Poisson “không” thực sự là một quá trình Bernoulli. Nguyên nhân là hàng đợi trình bày phụ thuộc lần lượt từng khe. Nếu như có các gói trong bộ đệm, thì xác suất để không có gói nào được phục vụ tại khe gói kế tiếp là 0, trong khi đối với quá trình Bernoulli nó là 1 – p. Như vậy, mặc dù dòng gói đầu ra không phải là một quá trình không nhớ, quá trình Bernoulli vẫn là một mẫu xấp xỉ hiệu quả, những sự biến đổi được bắt gặp thường xuyên trong kỹ thuật lưu lượng từ xa [TK1.trang 45] cho IP. Hạn chế của những quá trình liên đi đến theo số mũ âm và hình học là chúng không bao gồm tất cả các thông số đặc trưng quan trọng của lưu lượng điển hình. Những dạng cụ thể của phân tích chuyển mạch giả thiết quá trình “đi đến theo nhóm”: ở đây, thay vì một sự đi đến đơn lẻ với xác suất p, chúng ta sẽ có một nhóm, và số lượng trong nhóm có thể có một phân bố bất kỳ. Dạng quá trình đi đến này có thể còn được xem xét trong phạm trù đếm số lần đi đến này. Ví dụ, tại một bộ đệm trong mạng IP, một nhóm đi đến lên tới một vài giá trị cực đại, M, đến từ những phần khác nhau của chuyển mạch trong khoảng một khe thời gian. Điều này có thể được xem xét khi đếm số lần đi đến tương tự như các gói trong nhóm trong khe thời gian đó. Quá trình Bernoulli với đi đến theo nhóm được đặc trưng bởi một số lần đi đến được phân bố độc lập và giống nhau theo chu kỳ thời gian riêng. Điều này được định nghĩa theo hai phần: sự hiện diện của nhóm Pr{có một nhóm đi đến trong một khe thời gian} = p hoặc sự vắng mặt của nhóm Pr{không có sự đi đến nào trong một khe thời gian} = 1 – p Và sự phân bố của số gói trong nhóm: b(k) = Pr{có k gói trong một nhóm được tính ra khi có một nhóm trong x khe thời gian} Lưu ý rằng k > 0. Sự mô tả quá trình đi đến này có thể được sắp xếp lại để đưa ra phân bố tổng của số lần đi đến trên khe, a(k), như sau: a(0) = 1 – p a(1) = p.b(1) a(2) = p.b(2) … a(k) = p.b(k) … a(M) = p.b(M) Trong trường hợp một phân bố đầu vào Poisson, khoảng thời gian T là một khe thời gian, khi đó Với phân bố nhị thức, bây giờ chúng ta mong muốn xác suất có k lần đi đến từ M lối vào mà mỗi đầu vào có một xác suất, p, của quá trình cung cấp một gói đi đến trong khe thời gian bất kỳ. Bởi vậy Và tốc độ đi đến cuối cùng là M.p gói/khe thời gian. Hình 2.16 trình bày điều gì xảy ra khi tốc độ đi đến cuối cùng được cố định tại 0.95 gói/khe thời gian và những số lượng lối vào 10, 20 và 100 (và như vậy p lần lượt là 0.095, 0.045, 0.0095). Phân bố nhị thức có xu hướng gần với phân bố Poisson, và thực tế trong giới hạn khi N ® ∞ và p ® 0 các phân bố là tương tự. 2.4.5. Các tốc độ luồng Dạng nguồn đơn giản nhất sử dụng một sự mô tả tốc độ là dòng đi đến theo chu kỳ. Chúng ta thấy một ví dụ của dạng này trong điện thoại 64 kbit/s, có tốc độ gói là 167 gói/s. Bước tiếp theo là xem xét một nguồn Bật-Tắt, nơi mà quá trình chuyển mạch giữa một trạng thái im lặng, không tạo ra gói, và một trạng thái cung cấp một tốc độ cố định riêng của gói. Những nguồn với những khoảng thời gian (trong các trạng thái Bật và Tắt) được phân bố như số mũ âm được nghiên cứu thường xuyên nhất, và được áp dụng cho lưu lượng dữ liệu, cho lưu lượng thoại gói, và như một mẫu chung cho lưu lượng theo nhóm trong một bộ ghép IP. Hình 2.17 đưa ra một mẫu lưu lượng từ xa điển hình cho một nguồn Bật-Tắt. Trong khoảng thời gian nguồn bật (gọi là “thời gian lưu lại trong trạng thái hoạt động), nguồn phát các gói với tốc độ R. Sau mỗi gói, gói khác được phát với xác suất a, hoặc nguồn chuyển sang trạng thái tắt với xác suất 1 – a. Tương tự, trong trạng thái tắt, nguồn phát khe thời gian rỗng khác với xác suất s hoặc chuyển sang trạng thái hoạt động với xác suất 1 – s. Kiểu nguồn này phát các gói trong những mẫu giống như trong Hình 2.18. Đối với mẫu này, R bằng một nửa của tốc độ khe gói. Lưu ý rằng có các khe rỗng trong khoảng thời gian trạng thái hoạt động; chúng xuất hiện nếu tốc độ đi đến của gói, R, nhỏ hơn tốc độ khe gói, C. Chúng ta có thể quan sát nguồn Bật-Tắt theo cách khác. Thay vì đưa ra quá trình phát gói và quá trình khe thời gian rỗng rõ ràng như quá trình Bernoulli, chúng ta có thể mô tả đơn giản trạng thái hoạt động giống như có một phân bố hình học với số lần đi đến của gói, và trạng thái tắt như có một phân bố hình học số các khe gói. Số các gói có nghĩa là một trạng thái hoạt động, E[on], bằng nghịch đảo của xác suất để thoát khỏi trạng thái hoạt động, tức là 1/(1 – a) gói. Số khe gói có nghĩa là trạng thái im lặng, E[off], bằng 1/(1 – s) khe gói. Tại điểm cuối của một chu kỳ lưu lại trong trạng thái, quá trình chuyển mạch đến một trạng thái khác với xác suất bằng 1. Hình 2.19 chỉ ra sự trình diễn lựa chọn này của mẫu nguồn Bật-Tắt. Một lưu ý quan trọng là các phân bố hình học cho những trạng thái hoạt động và tắt có cơ sở thời gian khác nhau. Đối với trạng thái hoạt động đơn vị thời gian là 1/R, tức là thời gian liên đi đến của một gói. Do vậy khoảng thời gian có nghĩa trong trạng thái hoạt động là Đối với trạng thái tắt, đơn vị thời gian là 1/C, với C là tốc độ khe gói; bởi vậy khoảng thời gian có nghĩa trong trạng thái tắt là Trình diễn lựa chọn của Hình 2.19 khi đó có thể được khái quát hoá bằng cách cho phép các phân bố tuỳ ý đối với các gói được phát trong một chu kỳ hoạt động, và còn đối với số những khe rỗng được phát trong một chu kỳ tắt. Trước khi rời nguồn Bật-Tắt, chúng ta sẽ áp dụng nó vào một ví dụ thực tế: thoại tránh im lặng (không phát gói trong những chu kỳ mà người nói im lặng). Các con số điển hình (tìm được bằng phép đo) đối với những chu kỳ Bật và Tắt có nghĩa lần lượt là 0.96s và 1.69s. Các gói được phát từ nguồn thoại 64 kbit/s tại tốc độ R = 167 gói/s và tốc độ khe gói của một liên kết là 155.52 Mb/s là C = 353208 gói/s. Do đó số gói có nghĩa được cung cấp trong một trạng thái hoạt động là E[on] = R × 0.96 = 160 gói Và số các khe rỗng có nghĩa trong một trạng thái im lặng là E[off] = C × 1.69 = 596921 khe gói Điều này đưa đến mẫu được chỉ ra trong Hình 2.20 Chúng ta còn có thể tính toán các giá trị của những thông số a và s đối với mẫu ở Hình 2.17. Chúng ta biết rằng vậy Và vậy Nguồn Bật-Tắt là một ví dụ cụ thể của một mẫu trên cơ sở trạng thái mà tốc độ đi đến trong một trạng thái là cố định, có hai trạng thái, và chu kỳ thời gian bỏ ra trong một trạng thái (thời gian lưu lại) là phân bố số mũ âm, hình học hoặc tuỳ ý. Chúng ta có thể khái quát hoá điều này tới N trạng thái, với các tốc độ cố định trong mỗi trạng thái. Các mẫu đa trạng thái này (được gọi là “các quá trình quyết định điều chế”) rất hữu ích cho việc tạo ra một số nguồn Bật-Tắt được ghép cùng nhau, hoặc một nguồn lưu lượng đơn lẻ, phức tạp hơn, như video. Nếu chúng ta cho phép thời gian lưu lại có phân bố tuỳ ý, quá trình kết quả sẽ được gọi là một Quá trình Quyết định Điều chế Chung (GMDP – Generally Modulated Deterministic Process). Nếu khoảng thời gian trong trạng thái được phân bố theo số mũ thì quá trình được gọi là Quá trình Quyết định Điều chế Markov (MMDP). Trong trường hợp này, mỗi trạng thái tạo ra một phân bố hình học cho số các gói trong chu kỳ lưu lại bất kỳ. Đó là do, khi đã có phát sự đi đến i, nó phát sự đi đến i + 1 với một xác suất được tính bằng xác suất để thời gian lưu lại không kết thúc trước thời điểm của lần đi đến kế tiếp. Xác suất này không đổi nếu các chu kỳ thời gian lưu lại được phân bố theo số mũ âm bởi vì thuộc tính “không nhớ” của phân bố số mũ âm. Chúng ta không cần hạn chế mẫu để có một tốc độ đi đến không đổi trong mỗi trạng thái: nếu quá trình đi đến trên trạng thái là một quá trình Poisson, và ý nghĩa của phân bố Poisson được quyết định bằng trạng thái của mẫu trong đó, thì chúng ta có một MMDP hữu ích đối với việc trình diễn một quá trình đi đến tổng của gói. Đối với tất cả quá trình trạng thái này, tại điểm cuối của một sự lưu lại trong trạng thái i, tạo ra một sự quá độ sang trạng thái khác j; sự quá độ này được chi phối bởi một ma trận N×N của các xác suất quá độ, p(i,j) i ¹ j. Hình 2.21 minh hoạ một mẫu đa trạng thái, với ba trạng thái, và với các xác suất quá độ từ trạng thái i sang trạng thái j chỉ ra như p(i,j).