헤드 오브 라인 블로킹

Head-of-line blocking

컴퓨터 네트워킹에서의 Head-of-Line Blocking(HOL 블로킹)은 패킷의 행이 첫 번째 패킷에 의해 큐 내에서 지연될 때 발생하는 성능 제한 현상입니다.예를 들어 입력 버퍼링된 네트워크 스위치, 순서가 잘못된 전달, HTTP 파이프라인에서의 여러 요청 등이 있습니다.

네트워크 스위치

헤드 오브 라인 블로킹의 예:첫 번째 및 세 번째 입력 플로우는 같은 출력 인터페이스에 패킷을 송신하기 위해 경합하고 있습니다.이 경우 스위칭패브릭이 세 번째 입력 플로우로부터의 패킷을 전송하기로 결정했을 경우 첫 번째 입력 플로우는 같은 타임슬롯으로 처리할 수 없습니다.첫 번째 입력 플로우는 처리에 사용할 수 있는 출력 인터페이스3 의 패킷을 블록 하고 있는 것에 주의해 주세요.

스위치는 버퍼링된 입력 포트, 스위치패브릭 및 버퍼링된 출력 포트로 구성할 수 있습니다.First-In First-Out(FIFO; 선입선출) 입력 버퍼를 사용하는 경우 전송에 사용할 수 있는 것은 가장 오래된 패킷뿐입니다.행선지 출력이 비지이기 때문에, 가장 오래된 패킷을 전송 할 수 없는 경우는, 보다 최근의 착신은 전송 할 수 없습니다.출력 경합이 있는 경우 출력이 비지 상태일 수 있습니다.

HOL 블로킹이 없는 경우, 신규 착신은, 스택 된 가장 오래된 패킷을 개입시켜 각각의 행선지에 전송 될 가능성이 있습니다.HOL 블로킹은 입력 버퍼 시스템에서 성능 저하 효과를 가져올 수 있습니다.

이 현상에 의해 스위치의 throughput이 제한됩니다.FIFO 입력 버퍼에서는, 고정 사이즈의 셀을 균등하게 분산된 행선지에 심플하게 배치하는 모델이기 때문에, 링크의 수가 [1]증가하면 throughput이 전체의 58.6%로 제한됩니다.

이 제한을 극복하는 방법 중 하나는 가상 출력 [2]큐를 사용하는 것입니다.

HOL 블로킹을 받을 수 있는 것은 입력 버퍼링이 있는 스위치뿐입니다.내부 대역폭이 충분하면 입력 버퍼링은 불필요합니다.모든 버퍼링은 출력으로 처리되며 HOL 블로킹은 회피됩니다.이 no-input-buffering 아키텍처는 중소형 이더넷스위치로 일반적입니다.

순서가 잘못된 배송

순서가 잘못된 전달은 시퀀싱된 패킷이 도착했을 때 발생합니다.이 문제는 패킷에 의해 다른 경로가 선택되거나 패킷이 폐기되어 재발송신되기 때문에 발생할 수 있습니다.HOL 블로킹은 패킷 [3][4]순서 변경을 크게 증가시킬 수 있습니다.

다수의 피어 간에 손실 네트워크를 통해 메시지를 확실하게 브로드캐스트하는 것은 어려운 문제입니다.아토믹 브로드캐스트알고리즘은 집중형 서버의 싱글포인트 장애 문제를 해결하는데, 이러한 알고리즘은 헤드오브라인 블로킹 [5]문제를 일으킵니다.가십 프로토콜을 사용하는 랜덤화 알고리즘인 바이모달 멀티캐스트알고리즘은 [6]일부 메시지를 순서대로 수신할 수 있도록 함으로써 라인 선두 차단을 회피합니다.

HTTP의 경우

HTTP/1.1에서의 HOL 블로킹의 1가지 형식은 브라우저에서 허용되는 병렬 요구의 수가 모두 사용되고 후속 요구는 이전 요구가 완료될 때까지 기다려야 하는 경우입니다.HTTP/2는 요구 멀티플렉싱을 통해 이 문제에 대처합니다.이것에 의해, 애플리케이션층에서는 HOL 블로킹이 불필요하게 됩니다만, HOL은 트랜스포트(TCP)[7][8]층에서는 아직 존재합니다.HTTP/3는 TCP 대신 QUIC를 사용하여 트랜스포트 레이어 내의 HOL 블로킹을 삭제합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ M. Karo; M. Hluchyj; S. Morgan (December 1987). "Input Versus Output Queuing on a Space-Division Packet Switch". IEEE Transactions on Communications. 35 (12): 1347–1356. doi:10.1109/TCOM.1987.1096719.
  2. ^ Nick McKeown; Adisak Mekkittikul; Venkat Anantharam; Jean Walrand (August 1999). "Achieving 100% Throughput in an Input-Queued Switch" (PDF). IEEE Transactions on Communications. 47 (8): 1260–1267. CiteSeerX 10.1.1.18.7529. doi:10.1109/26.780463.
  3. ^ Jon C. R. Bennett; Craig Partridge; Nicholas Shectman (December 1999). "Packet reordering is not pathological network behavior". IEEE/ACM Transactions on Networking. 7 (6): 789–798. CiteSeerX 10.1.1.461.7629. doi:10.1109/90.811445. S2CID 26573611.
  4. ^ Bennett, J. C. R.; Partridge, C.; Shectman, N. (April 2000). Sarisky, Dan (ed.). "Packet Reordering is Not Pathological Network Behavior [Slides]" (PDF). SC N Research. Archived from the original (PDF) on 2017-08-20. Retrieved 2017-08-19.
  5. ^ Defago, X.; Schiper; A., Urban, P. (2004). "Total order broadcast and multicast algorithms: taxonomy and survey" (PDF). ACM Computing Surveys. 36 (4): 372-421. doi:10.1145/1041680.1041682. S2CID 207155989.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  6. ^ Tyler McMullen (2015). "It Probably Works". ACM Queue.
  7. ^ Grigorik, Ilya (October 2013). "Making the Web Faster with HTTP 2.0". ACM Queue. 11 (10): 40. doi:10.1145/2542661.2555617. S2CID 34623442. Retrieved 10 June 2019.
  8. ^ Javier Garza (October 2017). "How does HTTP/2 solve the Head of Line blocking (HOL) issue".