요약

  • 비례 공정성은 실현 가능한 전체 속도 벡터의 반사실적 성질이다. 선택된 속도들로부터 상대적 변화량의 합이 양수가 되는 다른 배분이 존재하는지를 묻는다. 단일 흐름의 처리량만으로는 이 질문에 답할 수 없다.
  • Frank Kelly의 1997년 모델은 사용자 효용을 네트워크의 용량 제약 하 배분과 분리했다. Aman Maulloo, David Tan과 함께 쓴 1998년 논문은 가중 로그 목적 함수를 분산형 원시(primal)·쌍대(dual) 속도 제어 알고리즘과 연결했다.
  • 섀도 가격과 리아푸노프 안정성은 엄밀한 모델 증거이지 배치 완료의 영수증이 아니다. 그 의미는 흐름 식별, 가중치, 경로와 용량 가정, 피드백 함수, 지연과 확률적 거동에 따라 달라진다. 그중 어느 것도 소매 요금, 낮은 지연 또는 인터넷 전반의 채택을 자동으로 증명하지 않는다.

공정성은 어느 흐름에도 기록되어 있지 않다

하나의 병목을 공유하는 두 개의 탄력적 전송을 상상해 보라. 하나는 6단위의 속도를 받고 다른 하나는 4단위를 받는다. 첫째는 6을 보고할 수 있고, 둘째는 4를 보고할 수 있다. 어느 관측도, 상대적 이득과 손실의 총 균형을 개선하는 또 다른 실현 가능한 배분이 존재하는지를 밝혀 주지 않는다.

비례 공정성은 바로 그 빠져 있는 비교에서 시작한다. 선택된 배분에 대해 임의의 다른 실현 가능한 배분을 생각한다. 모든 흐름에 대해 제안된 변화를 선택된 속도에 대한 비율로 측정하고, 그 비율들을 더한다. 그 합이 결코 양수가 될 수 없을 때 선택된 벡터는 비례적으로 공정하다. 이 판정은 하나의 흐름이 만족하는지를 묻지 않는다. 대안 배분의 총 백분율 이득이 양수가 되어 전체 벡터가 흔들릴 수 있는지를 묻는다.

단일 병목에서 가중치가 같고 그 밖의 조건이 단순하다면, 결과는 실제로 동일한 속도를 줄 수 있다. 이 익숙한 사례를 정의로 오해하기 쉽다. 그러나 그렇지 않다. 경로가 서로 다른 자원을 지나거나, 가중치가 다르거나, 실현 가능 영역이 바뀌면 비례적으로 공정한 배분이 등분처럼 보이지 않을 수 있다. ‘비례적’이라는 말은 비교되는 변화량을 가리킬 뿐, 용량이 눈에 띄게 맞아떨어지는 몫으로 나뉜다는 약속이 아니다.

이 때문에 하나의 속도는 공정성을 증명할 수 없다. 증거 대상에는 관련된 모든 속도, 실현 가능한 대안들, 경로-자원 행렬, 그리고 ‘실현 가능’이 무엇을 뜻하는지 정의하는 용량들이 포함된다. 흐름 식별을 바꾸거나 한 사용자가 여러 개의 겉보기 흐름으로 자신을 분할하도록 허용하면, 알고리즘이 작동하기 전에 최적화 문제 자체가 바뀐다.

1997년 모델은 수요와 용량을 분리했다

Kelly가 수정한 1997년 논문 「Charging and rate control for elastic traffic」는 사용자에 대한 증가하고 엄격히 오목한 효용 함수와 네트워크 자원의 유한 용량에서 출발한다. 사용자의 가치가 조절 가능한 속도의 함수로 표현될 때 그 트래픽을 탄력적이라고 부른다. 이어서 경로와 링크 용량 제약 하에서 총 효용을 최대화한다.

이 정식화는 의도적으로 추상적이다. 제안된 분해에서 네트워크는 각 효용 함수를 알 필요가 없다. 사용자는 국소 문제를 풀고, 네트워크는 용량 제약 하의 배분 문제를 푼다. 라그랑주 승수가 둘을 연결한다. 제약된 링크의 승수는 흐름 한 단위 추가의 함축적 비용, 혹은 추가 용량의 섀도 가격으로 해석될 수 있다.

논문은 또한 사용자가 단위시간당 요금을 선택하고 네트워크가 단위 요금당 속도가 비례적으로 공정하도록 속도를 배정하는 선호 버전을 다룬다. 사용자 선택과 네트워크 배분이 균형에서 만나면 시스템 최적이 나타날 수 있다. 이 결과는 1997년 가입자들이 실제로 자신의 효용을 선언하거나 그런 청구서를 받았다는 사실 주장이 아니다. 사적 선호와 공유 제약을 모든 효용 함수를 중앙 행위자에게 넘기지 않고 분해할 수 있는 방식의 모델이다.

이 구분은 두 가지 흔한 오류를 막는다. 섀도 가격은 반드시 징수된 돈이 아니다. 우선은 제약된 문제 안에서 희소성을 표시하는 최적화 변수이다. 그리고 ‘지불 의사’는 식별 중립적 사실이 아니다. 가중치가 지불, 우선순위 또는 다른 권리를 부호화한다면, 가중치를 정의하는 자가 이미 무엇이 계수되는지에 대한 거버넌스 결정을 내린 것이다.

Kelly, Maulloo, Tan는 목적 함수에 두 가지 국소 메커니즘을 부여했다

1998년 논문 「Rate control for communication networks: shadow prices, proportional fairness and stability」는 Frank Kelly, Aman Maulloo, David Tan이 공동 집필했다. 통신 자체가 지연과 장애에 노출되는 신뢰할 수 있는 중앙 솔버 없이, 대규모 네트워크에서 비례 공정성에 어떻게 접근할 수 있는지를 묻는다.

이 네트워크 문제는 용량 제약 하에서 로그 속도의 가중 합을 최대화한다. 로그가 중요한 이유는 그 도함수가 절대적 속도 변화를 상대적 변화로 바꾸기 때문이다. 라그랑지안은 전역 제약을 자원과 경로에 연관된 국소 항들로 분해한다.

원시(primal) 관점에서는 평균화의 상당 부분이 단말에 남는다. 자원은 부하가 올라가며 혼잡 표시를 만들어 내고, 소스는 꾸준히 늘어나다가 받은 피드백에 반응해 줄인다. 논문은 이 계열을 증가-가산·감소-승제 방식의 사고와 연관 짓되, 실제 모든 TCP 인스턴스가 이 수학적 체계를 정확히 구현한다고 주장하지는 않는다.

쌍대(dual) 관점에서는 자원의 희소성 신호가 더 명시적이다. 자원은 초과 수요에 따라 섀도 가격을 조정하고, 경로의 속도는 그 경로상 자원 가격들의 합에 반응한다. 경제학자는 타토누망(tâtonnement) 과정을, 운영자는 피드백 루프를 떠올릴 수 있다. 어느 어휘로 보든 어떤 노드도 전체 배분을 계산하지 않는다. 국소 측정과 반응이 모여 벡터를 움직인다.

이 둘은 하나의 목적 함수에 붙은 두 메커니즘이지, 서로 교환 가능한 패킷 형식이 아니다. 원시 영수증은 어떤 혼잡 표시가 어느 소스에 도달했고 소스가 어떻게 반응했는지를 보여야 한다. 쌍대 영수증은 어떤 자원 가격이 계산되었고, 경로상에서 어떻게 결합되었으며, 어떤 명시적 속도가 뒤따랐는지를 보여야 한다. 최종 처리량만 관측하면 배분이 선택된 경로가 가려진다.

증명은 드러난 모델 경계에 의존했다

명시된 정칙성 가정 하에서 Kelly, Maulloo, Tan은 자신들의 미분방정식 계통에 리아푸노프 함수 역할을 하는 함수를 구성한다. 이 함수는 안정점을 향해 증가하고 국소 속도 갱신의 거동을 네트워크 최적화 문제의 완화 버전과 연결한다. 이는 강력한 증거다. 분산 과정이 전역적으로 그렇게 작동할 것이라고 막연히 바라는 것이 아니라, 모델이 수렴의 수학적 증인을 제공한다.

논문은 감추지 않은 점에서도 똑같이 가치 있다. 첫 연속 계통은 확률적 교란과 시간 지연을 생략한다. 저자들은 이어서 작은 무작위 교란과 지연된 피드백을 살핀다. 이득이 빠르면 수렴은 빨라지지만 평형 주변 변동은 커진다. 지연이 있을 때는 더 가파른 반응이 한 측면을 개선하는 대신 안정성을 해칠 수 있다. 가격 함수가 증가하지 않으면 내부 최대점이 사라지거나 여러 정상점이 나타날 수 있다.

Frank Kelly의 이후 리뷰는 경계를 더 분명히 한다. 개별 흐름은 자신의 혼잡 경험과 피드백 지연은 알지만, 경쟁 흐름 수도 자신의 경로상 모든 자원도 알지 못한다. 지연 불안정성과 확률적 불안정성은 서로 다른 제약을 부과한다. 원시 방식과 쌍대 방식은 공정성과 이용률을 맞바꿀 수 있고, 이후 결과들은 훨씬 넓은 연구 공동체의 것이다.

따라서 리아푸노프 함수는 특정 동역학 계통에 대한 영수증이다. 임의의 큐, RTT, 경로 변경, 단명 흐름, 전략적 송신자, 구현 오류가 같은 거동을 유지한다는 증명이 아니다. 평형으로의 수렴이 이동 과정에서 낮은 지연, 낮은 손실, 애플리케이션 가치를 보증하지도 않는다.

공정성 단위는 통제 결정이기도 했다

논문들의 가중치 구조는 오늘날 시스템도 여전히 직면하는 어려움을 드러낸다. 한 사용자가 여러 사용자로 자신을 내세울 수 있다면 배분자는 그에게 몫을 여럿 줄 수 있다. 운영자가 많은 사용자를 하나의 흐름으로 묶으면 같은 사람들이 몫을 하나만 받을 수도 있다. 식별 경계가 명시되기 전에는 어느 결과도 속도 벡터만으로 판단할 수 없다.

가중치는 문제를 더 날카롭게 한다. 가중치는 선택된 지불, 협력적 자원 권리 또는 다른 정책 변수를 나타낼 수 있다. 서로 다른 해석이 같은 대수와 전혀 다른 제도를 만들어 낼 수 있다. 선언된 가중치에 대해 배분이 비례적으로 공정하면서도, 가중치 설정 과정 자체는 불투명하거나 논쟁 중일 수 있다.

따라서 증거는 수학적 대상과 운영상 주체를 함께 밝혀야 한다. 공정성을 TCP 연결, 5-튜플, 가입자, 애플리케이션, 조직, 경로 중 무엇 사이에서 측정하는가? 한 주체가 저비용으로 더 많은 대상을 만들 수 있는가? 가중치를 누가 정하며, 다른 당사자가 그것을 감사할 수 있는가? 배분을 계산할 때 어떤 용량과 경로를 고정으로 두었는가?

이 질문들은 비례 공정성을 무효로 만들지 않는다. 그 권위의 위치를 밝힌다. 이 기준은 명시된 전제 아래 벡터를 판정할 수 있다. 그러나 전제를 참되게 만드는 정당한 식별과 권리를 선택할 수는 없다.

Frank Kelly는 목적 함수와 작동 중인 반응을 연결했다

Royal Society는 무작위 과정, 네트워크, 최적화, 대형 시스템의 자기규제에 걸친 Kelly의 연구를 기록한다. 그의 네트워크 논문들이 오래 남은 이유는 흔히 따로 놓는 세 언어를 연결하기 때문이다. 효용과 희소성의 경제학적 서술, 제약과 승수의 최적화 서술, 그리고 피드백과 안정성의 공학 서술이다.

이 연결의 공은 신중히 돌려야 한다. 1998년 속도 제어 논문은 Kelly, Maulloo, Tan의 것이다. 그 선행 작업에는 많은 이들의 혼잡 제어와 공정성 연구가 있고, 이후 네트워크 효용 최대화 문헌은 집단적 산물이다. Kelly의 역할을 인정한다고 해서 그가 혼잡 제어의 유일한 발명자이거나 이 틀로 쓰인 모든 알고리즘의 발명자가 되는 것은 아니다.

Lu Heng이 나중에 제안한 Minimum Initial Specification 원칙은 오늘의 유용한 판정 기준이지 역사적 출처가 아니다. 공정성 주장이 국소적으로 검증되려면 참여자들이 무엇을 공유해야 하는가? 흐름 식별, 용량, 피드백, 가중치, 호환성에 대한 공통 의미가 필요하다. 모든 국소 효용을 내놓거나 하나의 보편 제어 법칙을 채택할 필요는 없다. 이후의 변화는 배분이 공정하다는 선언이 아니라, 작동 중인 구현과 관측 가능한 반응을 통해 실현된다.

따라서 남는 교훈은 슬로건보다 엄격하다. 전역 목적은 국소 신호로 접근할 수 있다. 그러나 그 주장은 시스템이 영수증을 보관할 때만 살아남는다. 누구의 흐름이 계수되었는지, 어떤 대안이 실현 가능했는지, 어떤 가중치와 제약이 적용되었는지, 어떤 피드백이 단말을 움직였는지, 평형 전에 동역학이 어떻게 작동했는지. 이것이 없다면 ‘비례적으로 공정하다’는 말은 보이지 않는 실험에 붙은 매력적인 라벨에 지나지 않는다.

출처