네트워크 혼잡을 완화하는 주요 장애물을 발견
여러 사용자가 네트워크를 공평하게 공유하도록 설계된 알고리즘은 일부 사용자가 모든 대역폭을 사용하는 것을 막을 수 없습니다.
날짜:
2022년 8월 4일
원천:
매사추세츠 공과 대학
요약:
연구원들은 네트워크를 통해 데이터를 전송하는 여러 사용자를 보장하도록 설계된 혼잡 제어 알고리즘이 실제로 일부 사용자가 모든 대역폭을 사용하는 상황을 피할 수 없다는 것을 발견했습니다.
사용자가 네트워크가 처리할 수 있는 것보다 더 빠르게 인터넷을 통해 데이터를 보내려고 할 때 혼잡이 발생할 수 있습니다. 교통 혼잡이 대도시로 아침 출퇴근을 하는 것과 같은 방식입니다.
인터넷을 통해 데이터를 전송하는 컴퓨터 및 장치는 데이터를 더 작은 패킷으로 나누고 특수 알고리즘을 사용하여 해당 패킷을 보내는 속도를 결정합니다. 이러한 혼잡 제어 알고리즘은 사용 가능한 네트워크 용량을 완전히 발견하고 활용하는 동시에 동일한 네트워크를 공유할 수 있는 다른 사용자와 공정하게 공유합니다. 이러한 알고리즘은 네트워크의 대기열에서 대기 중인 데이터로 인한 지연을 최소화하려고 합니다.
지난 10년 동안 산업계와 학계의 연구자들은 지연을 제어하면서 높은 속도를 달성하려고 시도하는 여러 알고리즘을 개발했습니다. Google에서 개발한 BBR 알고리즘과 같은 이들 중 일부는 현재 많은 웹사이트와 애플리케이션에서 널리 사용됩니다.
그러나 MIT 연구원 팀은 이러한 알고리즘이 매우 불공정할 수 있음을 발견했습니다. 새로운 연구에서 그들은 적어도 한 발신자가 다른 발신자에 비해 대역폭을 거의 받지 못하는 네트워크 시나리오가 항상 존재한다는 것을 보여줍니다. 즉, 기아로 알려진 문제를 피할 수 없습니다.
"이 문서와 결과에서 정말 놀라운 점은 네트워크 경로의 실제 복잡성과 데이터 패킷에 대해 수행할 수 있는 모든 작업을 고려할 때 지연 제어 정체 제어 알고리즘이 현재의 방법을 사용한 기아"라고 전기 공학 및 컴퓨터 과학(EECS) 부교수인 Mohammad Alizadeh가 말했습니다.
Alizadeh와 그의 공동 저자들은 기아를 피할 수 있는 기존의 혼잡 제어 알고리즘을 찾을 수 없었지만 이 문제를 방지할 수 있는 다른 클래스의 알고리즘이 있을 수 있습니다. 그들의 분석은 또한 이러한 알고리즘이 작동하는 방식을 변경하여 지연의 더 큰 변화를 허용하면 일부 네트워크 상황에서 기아를 방지하는 데 도움이 될 수 있다고 제안합니다.
Alizadeh는 제1저자이자 EECS 대학원생인 Venkat Arun, 수석 저자인 Hari Balakrishnan, Fujitsu 컴퓨터 과학 및 인공 지능 교수와 함께 논문을 작성했습니다. 이 연구는 ACM 데이터 통신에 관한 특별 관심 그룹(SIGCOMM) 컨퍼런스에서 발표될 예정입니다.
혼잡 통제
혼잡 제어는 연구원들이 1980년대부터 해결하려고 시도한 네트워킹의 근본적인 문제입니다.
사용자의 컴퓨터는 네트워크 연결 품질이나 네트워크를 사용하는 다른 발신자 수와 같은 정보가 부족하기 때문에 네트워크를 통해 데이터 패킷을 얼마나 빨리 보내는지 모릅니다. 패킷을 너무 느리게 전송하면 사용 가능한 대역폭을 제대로 사용하지 못합니다. 그러나 너무 빨리 보내면 네트워크가 압도될 수 있으며 그렇게 하면 패킷이 삭제되기 시작합니다. 이러한 패킷은 재전송되어야 하므로 지연 시간이 길어집니다. 또한 대기열에서 오랫동안 대기 중인 패킷으로 인해 지연이 발생할 수도 있습니다.
혼잡 제어 알고리즘은 패킷 손실 및 지연을 신호로 사용하여 혼잡을 추론하고 데이터 전송 속도를 결정합니다. 그러나 인터넷은 복잡하고 네트워크 혼잡과 관련 없는 이유로 패킷이 지연되거나 손실될 수 있습니다. 예를 들어, 데이터는 도중에 대기열에 보관된 다음 다른 패킷의 버스트와 함께 해제되거나 수신자의 승인이 지연될 수 있습니다. 저자는 혼잡으로 인한 것이 아닌 지연을 "지터"라고 부릅니다.
혼잡 제어 알고리즘이 지연을 완벽하게 측정하더라도 혼잡으로 인한 지연과 지터로 인한 지연을 구분할 수 없습니다. 지터로 인한 지연은 예측할 수 없으며 발신자를 혼란스럽게 합니다. 이러한 모호성 때문에 사용자는 지연을 다르게 추정하기 시작하여 패킷을 다른 속도로 전송하게 됩니다. 결국 이것은 기아가 발생하고 누군가가 완전히 폐쇄되는 상황으로 이어진다고 Arun은 설명합니다.
"우리는 지터가 있는 상태에서 혼잡 제어 동작에 대한 이론적 이해가 부족했기 때문에 프로젝트를 시작했습니다. 이를 보다 확고한 이론적 토대 위에 놓기 위해 우리는 생각할 수 있을 만큼 간단하면서도 일부를 포착할 수 있는 수학적 모델을 구축했습니다. 인터넷의 복잡성. 우리가 몰랐던 사실과 실용적인 관련성을 수학이 알려주는 것은 매우 보람된 일입니다."라고 그는 말합니다.
기아 공부
연구원들은 그들의 수학적 모델을 컴퓨터에 제공하고 일반적으로 사용되는 일련의 혼잡 제어 알고리즘을 제공하고 컴퓨터에 모델을 사용하여 기아를 피할 수 있는 알고리즘을 찾도록 요청했습니다.
"우리는 그것을 할 수 없었습니다. 우리는 우리가 알고 있는 모든 알고리즘과 우리가 만든 몇 가지 새로운 알고리즘을 시도했습니다. 아무 것도 작동하지 않았습니다. 컴퓨터는 항상 어떤 사람들은 모든 대역폭을 얻고 적어도 한 사람은 기본적으로 아무것도 얻지 못하는 상황을 발견했습니다. "라고 아룬은 말합니다.
연구원들은 특히 이러한 알고리즘이 합리적으로 공정하다고 널리 믿어지기 때문에 이 결과에 놀랐습니다. 그들은 극단적인 형태의 불공평인 기아를 피하는 것이 불가능할 수도 있다고 의심하기 시작했습니다. 이것은 그들이 "지연-수렴 알고리즘"이라고 부르는 알고리즘 클래스를 정의하도록 동기를 부여했으며, 이는 네트워크 모델에서 항상 기아로 고통받을 것임을 입증했습니다. 지연을 제어하는 기존의 모든 혼잡 제어 알고리즘(연구원들이 알고 있음)은 지연 수렴형입니다.
널리 사용되는 이러한 알고리즘의 단순 실패 모드가 오랫동안 알려지지 않은 상태로 남아 있다는 사실은 경험적 테스트만으로 알고리즘을 이해하는 것이 얼마나 어려운지를 보여줍니다. 탄탄한 이론적 기초의 중요성을 강조합니다.
그러나 모든 희망이 사라진 것은 아닙니다. 그들이 테스트한 모든 알고리즘이 실패했지만 기아를 피할 수 있는 지연 수렴이 아닌 다른 알고리즘이 있을 수 있습니다. 따라서 범위는 네트워크의 지터로 인해 발생할 수 있는 지연보다 큽니다.
"지연을 제어하기 위해 알고리즘은 원하는 평형에 대한 지연 변동을 제한하려고 시도했지만 혼잡 지연을 더 잘 측정하기 위해 잠재적으로 더 큰 지연 변동을 생성하는 것은 잘못된 것이 아닙니다. 이는 단지 새로운 설계 철학일 뿐입니다. 입양하세요." Balakrishnan이 덧붙입니다.
이제 연구원들은 기아를 제거할 알고리즘을 찾거나 구축할 수 있는지 확인하기 위해 계속 노력하고 있습니다. 그들은 또한 이러한 수학적 모델링 및 계산 증명 접근 방식을 네트워크 시스템에서 해결되지 않은 다른 까다로운 문제에 적용하기를 원합니다.
"우리는 매우 중요한 일에 대해 컴퓨터 시스템에 점점 더 의존하고 있으며 더 확고한 개념적 기반에 신뢰성을 둘 필요가 있습니다. 우리는 시간을 들여 이러한 공식 사양을 제시할 때 발견할 수 있는 놀라운 것들을 보여주었습니다. 문제가 실제로 무엇인지"라고 Alizadeh는 말합니다.