MBone

MBone은 멀티캐스트 백본(Multicast Backbone)의 약자로, 인터넷 프로토콜 위에 세운 가상 네트워크이다. 한 명의 수신자에게만 데이터를 보내는 연결 지향 전송(유니캐스트), 그리고 한 송신자가 네트워크의 모든 호스트에게 보내는 방식(브로드캐스트)과 달리, MBone은 멀티캐스트 기능을 제공한다. 멀티캐스트란 특정 멀티캐스트 그룹에 가입한 호스트들에게만 데이터를 보내는 방식이다. 그룹의 모든 구성원은 그룹으로 데이터를 보낼 수도 있고 그룹으로부터 데이터를 받을 수도 있다.

이 문제에서는 단순화한 MBone을 시뮬레이션한다.

네트워크는 멀티캐스트 라우터들과 호스트들로 이루어지며, 각 호스트는 정확히 하나의 라우터에 속한다. 하나의 라우터와 그 라우터에 속한 호스트들을 묶어 섬(island)이라고 부른다. 라우터들은 터널로 연결되는데, 터널은 단방향 통신 채널이다. 즉 터널의 한쪽 끝으로 보낸 패킷은 반대쪽 끝으로 나온다.

• 호스트가 멀티캐스트 그룹에 가입하려면 자신이 속한 라우터에게 그룹을 지정하여 요청을 보낸다. 그 후로 그 호스트는 해당 그룹으로 전송되는 모든 패킷을 받는다.
• 호스트가 그룹으로 패킷을 전송하려면 자신이 속한 섬의 라우터에게 패킷을 넘긴다. 패킷을 받은 모든 라우터는 그 패킷을 복제하여 자신의 나가는 터널마다 한 부씩 내보내고, 이어서 자신의 섬에 있는 호스트 중 그 패킷의 그룹에 가입한 모든 호스트(송신자 자신이 구성원이라면 송신자 포함)에게 한 부씩 전달한다.

패킷에는 전파 범위를 제한하는 정수 TTL(Time To Live)이 붙어 있다. 패킷이 터널을 통과하여 전달될 때마다 TTL은 그 터널의 임계값(threshold, 정수)만큼 줄어든다. 현재 TTL이 터널의 임계값보다 작으면 그 터널로는 패킷을 내보내지 않는다.

한 호스트가 서로 다른 경로를 통해 같은 패킷을 여러 번 받게 되는 경우, 남은 TTL이 가장 큰 사본(가장 짧은 경로로 도달한 사본)만 남긴다.

입력은 여러 개의 네트워크 설명으로 이루어진다. 각 설명은 두 부분, 즉 먼저 위상(topology), 그다음 활동(activity)으로 구성된다.

• 각 설명의 첫 줄은 정수 m (1 ≤ m ≤ 10)이며 섬의 개수를 나타낸다. 0만 적힌 줄은 입력의 끝을 의미한다.

• 이어지는 줄들은 m개의 섬을 설명한다. 각 섬은 다음 형식의 줄로 시작한다.

  <라우터 이름> <개수>

  여기서 라우터 이름은 공백이 없는 20자 이하의 문자열이고, 개수는 뒤따르는 설명 줄의 수이다. 그 각 줄은 다음 중 하나이다.

  • H <호스트 주소> — 이 섬에 속한 호스트.
  • T <임계값> <목적지 라우터 이름> — 다른 라우터(현재 라우터와 항상 다름)로 향하는 나가는 터널.

  <호스트 주소>와 <임계값>은 양의 정수이다.

• 섬 설명이 모두 끝나면, 뒤따르는 활동 줄의 개수를 나타내는 정수(최대 1000)가 한 줄에 주어진다. 각 활동 줄은 다음 중 하나이다.

  • J <호스트 주소> <그룹 주소> — 호스트가 그룹에 가입한다.
  • L <호스트 주소> <그룹 주소> — 호스트가 그룹에서 탈퇴한다.
  • S <호스트 주소> <그룹 주소> <패킷 ID> <TTL> — 호스트가 그룹으로 패킷을 전송한다.

  <그룹 주소>, <패킷 ID>, <TTL>은 양의 정수이며, 모든 TTL은 1000 이하이다.

하나의 시나리오 안에서 모든 라우터 이름, 모든 호스트 주소, 모든 패킷 ID는 서로 다르다. 어느 시점에서든 호스트는 최대 50개, 터널은 최대 100개, 활성 그룹(구성원이 한 명 이상인 그룹)은 최대 20개이다. 어떤 호스트도 가입하지 않은 그룹에서 탈퇴하거나 이미 가입한 그룹에 다시 가입하지 않는다.

각 네트워크에 대해, 호스트들이 받은 모든 패킷을 출력한다.

먼저 Network #k 줄을 출력한다. 여기서 k는 네트워크 번호이며 첫 번째 네트워크가 1이다. 그다음 받은 패킷마다 한 줄씩 다음 형식으로 출력한다.

<호스트 주소> <패킷 ID> <남은 TTL>

세 항목은 하나의 공백으로 구분한다. 한 호스트가 같은 패킷의 사본을 여러 개 받았다면 남은 TTL이 가장 큰 사본만 출력한다. 출력 줄은 오름차순으로 정렬하되, 먼저 호스트 주소로, 그다음 패킷 ID로 정렬한다.

연속한 네트워크의 출력 사이에는 빈 줄 하나를 넣어 구분한다.