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