라우팅을 위해 forwarding table의 entry를 채워야함
Intra-AS Algorithm
목표: 목적지까지 최소 비용의 경로를 찾는 것이 목표
1) 네트워크 상황을 다 아는 경우 : Link-State Algorithm
=> 모든 노드들이 자기의 링크 정보를 네트워크에 브로드캐스트로 뿌려둬야함 => 전체 그래프를 알게됨
-> 각 노드들이 자기 입장에서 다익스트라 돌려서 모든 목적지로 가는 최단거리를 계산하고, 이를 통해 다음에 이동할 라우터를 결정
발생할 수 있는 문제 상황
-> 현실적으로 브로드캐스트의 범위는 같은 도메인에 속한 하나의 네트워크로 한정됨
2) 이웃 라우터와의 부분적 정보만 이용하는 경우 : Distance Vector Algorithm
각 노드가 자기로부터 모든 노드까지의 거리를 vector(list)로 넘겨줌. -> 자기 자신의 distance vector가 업데이트되면 다시 전달.
벨만 포드 알고리즘 이용
문제점
link cost가 낮아져서 그 값을 채택하는 상황이면 괜찮은데, link cost가 높아져서 원래 가진 정보들로 업데이트해야할 경우 문제가 됨 : Count-to-infinity - 노드가 대안으로 생각하는 길이 사실은 재귀적으로 해서 변경된 link를 포함할수도 있는데, 그 사실을 바로 알 수 없기 때문에, 재귀를 타고 타고 들어가야 겨우 알 수 있음
=> 해결 방법: reverse path(갔다가 다시 돌아와서 자기자신을 거쳐가는)는 무한대로 넘겨줘야함. (poison reverse)
-> 이 라우팅 알고리즘도 마찬가지로 같은 도메인에 속한 하나의 네트워크로 한정됨
네트워크 간 라우팅 알고리즘?
밖으로 나가기 위해 게이트웨이 라우터까지는 위의 알고리즘을 사용하고(Autonomous System(자율 시스템), AS-자치권을 가짐 => Intras-AS), 해당 게이트웨이에서 다른 게이트웨이까지는 다른 알고리즘을 사용함.
Inter-AS Algorithm
Intra-AS와 달리 목적이 불분명함. 무조건 최소 비용이 아니라, 꼭 들리거나 들려서는 안될 라우터들이 있음.
모든 AS는 고유의 AS Number(ASNs)가 있음
대학교 AS는 더 큰 AS인 통신사 AS에 돈을 지불하고 인터넷을 제공받는 Provider와 Customer 관계가 존재함(상대적인 개념). Provider끼리는 Peering 관계가 존재함.
이런 관계를 구현하는 것이 BGP라는 프로토콜.
Border Gateway Protocol(BGP)
무조건 최단 거리가 목표 x. policy based(가장 돈이 되는, 경제적인 경로).
각 AS들은 prefix(네트워크 id)로도 대표될 수 있음. 따라서 이것과, AS number를 전달함. 그리고 이걸 전달받은 게이트웨이는 이 prefix에 자신의 prefix를 추가해서 전달해줌.
AS 경로(prefix) 여러가지가 있을 때, 여기에서 보고 저 적은 비용(최소 홉스) or 피해야할 게이트웨이를 선택하지 않는 경로를 선택(정책적으로 경로를 판단).
이 상황에서 홉스 2개, 3개인 경로가 있으니까 당연히 최단 거리면 홉스 2개인 경로를 선택해야하겠지만, BGP에서는 그렇지 않음.
내가 provider인 경로를 최대한 많이 선택하는게 가장 경제적인 경로이므로 3 2 1을 거치는 경로를 선택함.
