혼잡한 경로에서 나올 수 있도록 남겨 두는 대기열

어느 출력이 덜 막혔는지 보고 패킷의 경로를 바꾸고 싶다. 그러나 당장 비어 있는 방향을 고르는 결정들이 네트워크 전체에서는 서로 기다리는 고리를 만들 수도 있다. escape channel은 적응적으로 고른 길이 막혔을 때 사용할 수 있는 안전한 자원 경로를 남기는 방법이다. 이름보다 중요한 것은 그 경로로 들어가는 규칙과 들어간 뒤의 행동이다.

다른 전선보다 다른 대기열이 필요하다

여기서 escape channel은 별도로 늘린 물리 전선이라는 뜻이 아니다. 같은 전선에 연결된 논리 대기열을 나누고, 일부 자원에는 제한된 경로 규칙을 적용할 수 있다. 적응 경로의 패킷이 막혀도 안전 경로가 사용하는 저장 공간을 모두 함께 붙잡지 못하도록 구별하는 것이다.

구체적인 모델로 래핑 없는 2차원 mesh에 E라는 탈출 VC와 A라는 적응 VC를 두자. A에서는 목적지로 가까워지는 X 또는 Y 이동을 고를 수 있다. E에서는 현재 위치부터 X 좌표를 먼저 맞추고 Y 좌표를 맞춘다. A→E 이동은 허용하지만 E→A 이동은 금지한다. 목적지가 계속 수신하고, 준비된 요청은 중재에서 결국 선택된다고 가정한다. 패킷은 유한하며 시작한 패킷의 나머지 flit도 계속 공급된다.

BookSim의 min_adapt_mesh도 탈출 대기열의 차원 순서 경로와 나머지 대기열의 적응 후보를 구별한다. 이 글은 하나의 traffic class에서 VC 범위가 0부터 시작하는 구성을 기준으로 읽는다. 공식 구현의 min_adapt_mesh

어느 위치에서도 마지막 경로가 남아 있어야 한다

(0,0)에서 (2,2)로 가는 패킷이 처음에 A를 사용하여 북쪽으로 한 번 이동했다고 하자. 현재 위치는 (0,1)이다. 다시 북쪽으로 가는 A 자원이 막혀도 E를 사용할 수 있다면 (0,1)→(1,1)→(2,1)→(2,2)의 경로가 남는다. 출발점에서 계획했던 X 우선 경로로 되돌아가려고 남쪽으로 이동할 필요는 없다.

E의 안전성은 지금 위치와 최종 목적지에서 새로 정해지는 경로에 적용한다. 특정 출발지에만 E 진입을 허용하거나, 적응 경로의 중간 위치에서 목적지에 도달할 방법이 없다면 ‘탈출 채널이 존재한다’는 문장만으로 보장을 얻지 못한다.

이 모델에서는 A가 네 라우터에 걸쳐 서로 기다리는 고리를 만들더라도, 그 고리의 head가 요구할 E 자원은 별도로 남는다. E에서 기다리는 패킷은 더 뒤의 E 자원 또는 목적지로 진행하고 A를 다시 요구하지 않는다. E의 의존 관계가 순환하지 않고 소비와 중재가 진행된다면 E 자원은 결국 풀릴 수 있다. A의 고리를 구성한 패킷도 차례로 그 경로를 얻을 수 있다.

이는 매 cycle 즉시 탈출한다는 약속이 아니다. E에도 다른 패킷이 대기할 수 있다. 다만 적응 자원의 고리가 E를 포함한 닫힌 대기로 확장되지 않도록 전이를 제한하는 논증이다.

돌아가는 한 번의 전이가 논증을 바꾼다

E에 들어간 뒤에도 혼잡을 피하려고 다시 A로 갈 수 있도록 바꾸면 어떨까. A 자원을 가진 패킷이 E를 기다리고, E 자원을 가진 패킷이 다시 A를 기다리는 관계를 허용할 수 있다. 두 자원의 내부 경로만 각각 읽어서는 이 연결을 놓친다.

설명용으로 A0→E0과 E0→A0의 두 전이를 모두 허용하자. P가 A0을 붙잡고 E0을, Q가 E0을 붙잡고 A0을 기다리며 각 대기열이 가득 차면 진행할 수 없다. 작은 반례지만 ‘안전 대기열도 적응 대기열과 자유롭게 섞으면 된다’는 해석을 깨뜨린다. 실제 경로에서 이런 점유 조합이 가능한지는 전체 전이 규칙으로 확인해야 한다.

따라서 이 글의 단방향 A→E 규칙은 특정한 충분 조건을 설명하기 위한 설계다. 모든 적응형 라우팅이 같은 제한을 요구한다거나 다른 탈출 이론의 전이를 모두 금지한다고 확대하지 않는다.

안전한 후보와 실제 전송 기회는 다르다

경로 후보에 E를 적었지만 할당기가 항상 A만 고른다면, 혼잡한 패킷은 E에 진입하지 못할 수 있다. 또한 E에 들어온 패킷이 물리 링크 중재에서 영원히 밀리면 대기열의 순환이 없어도 전달은 끝나지 않는다. 낮은 우선순위를 두는 정책과 유한 시간 안에 기회를 준다는 보장을 구별해야 한다.

E의 버퍼를 적응 트래픽이 제한 없이 빌려 쓰도록 바꾸는 경우에도 진입 공간이 유지되는지 살펴야 한다. 물리 전선의 대역폭은 공유할 수 있지만, 어떤 저장 자원을 누가 점유하는지가 안전 경로의 논증을 결정한다. 요청을 받은 목적지가 응답을 기다리느라 수신을 막는 경우에는 시스템 프로토콜의 의존 관계도 별도로 남는다.

escape channel의 역할은 적응 경로를 무조건 빠르게 만드는 데 있지 않다. 선택의 자유를 사용하면서도 결국 목적지로 나갈 수 있는 자원 경로를 보존하는 것이다. 어느 위치에서 진입할 수 있는지, 이후 무엇을 다시 요구하지 않는지, 그 요청이 실제로 선택되는지까지 정하면 혼잡 회피와 전달의 보장을 함께 검토할 수 있다.