Routing

라우터를 통한 패킷의 전달

Source routing과 Next-Hop routring

Fowarding 라우터는 패킷을 받았을 때 목적지로 이 패킷을 보내기 위해서 라우팅 테이블의 정보를 조사하여 이 패킷의 다음 라우터(next hop)를 결정하고 이 패킷을 포워딩한다.

R1의 라우팅 테이블

라우팅 테이블 예

Linux에서의 예

앞의 예의 실제 망 구성

라우팅 프로토콜 정적 라우팅(static routing) 동적 라우팅(dynamic routing) 라우팅 프로토콜 라우팅 테이블의 정보는 변하지 않는다. 동적 라우팅(dynamic routing) 라우팅 테이블의 정보는 망의 상황에 따라서 변한다. 라우터들은 라우팅 정보를 주고 받으면서 이에 따라 라우팅 테이블을 구성한다. 라우팅 프로토콜 라우터들 간에 라우팅 정보를 주고 받는 방식을 규정한 것

라우팅 관점에서 인터넷 망 구성 AS(Autonomous System) 하나의 관리 기관에 소속된 라우터들의 집합 AS내의 라우터 간에는 동일한 라우팅 프로토콜이 동작한다.(IGP) 각 AS는 border router가 존재하면 border router 간에는 각 AS 간의 라우팅 정보를 주고 받는다.(EGP)

Autonomous System 1 Autonomous System 2 Subnet 1.2 Subnet 2.1 R3 R2 R6 LEGEND: Interior Gateway Protocol Exterior Gateway Protocol

라우팅 프로토콜의 분류 Exterior Gateway Protocol (EGP) Interior Gateway Protocol (IGP)

IGP Routing protocol Shortest path algorithm algorithm RIP IGRP Bellman-Ford algorithm Distance Vector algorithm OSPF IS-IS Dijstra algorithm Link State algorithm

Distance Vector Algorithm (경로 계산을 위한 측정치는 시간이라고 가정) 1단계: 각 라우터는 ECHO 패킷을 이웃하는 라우터에 전송하여 링크의 시간 을 측정한다. 2단계: 각 라우터는 자신의 정보를 이웃하는 라우터에게 주기적으로 전송한다. 이 정보는 모든 라우터에 도달하기 위한 시간을 포함한다. 3단계 : 각 라우터는 이웃 라우터의 정보를 이용하여 모든 라우터에 이르는 시간을 계산 하여 자신의 정보를 갱신한다.

각 라우터에 이르는 시간의 계산 B Echo 패킷 A C J Ti sec m sec D E (TAB, TAC, TAD, TAE) D TB = m + TAB TC = m + TAC TD = m + TAD TE = m + TAE E

Distance Vector Algorithm의 예

Updating routing table

Link state Routing Algorithm 이웃 라우터를 찾는다. (주기적으로 Hello message 를 보낸다.) 각 이웃 라우터와의 링크 비용(link cost)를 계산한다. Link cost는 여러가지가 될 수 있다.(시간, 대역폭, 트래픽 양 등등) Link State packet을 구성한다. Link State packet을 망의 모든 라우터에게 전송한다. (broadcast) 모든 라우터로부터 받은 Link State Packet을 사용하여 link state database를 구성한다. Link state database를 사용하여 모든 라우터에 이르는 최단 경로(shortest paths)를 계산한다.

Link State Packet의 구성

Link state routing의 예(1) Step1: 이웃 노드로부터 링크 상태 정보(link state information)를 모아서 링크 상태 패킷(link state packet)들을 만든다. 5 B C 1 3 F 3 2 2 1 3 A 2 1 D E Link state packets Meet Neighbors 노드(여기서는 라우터라고 부른다)는 처음 booting했을 때 자신과 이웃하고 있는 라우터가 누구인지 찾는다. 그 방법으로는 Hello packet을 각 link에 전송하여 응답을 통해서 알아낸다. 그리고, 이웃하는 라우터까지 이르는 link의 cost를 계산하다. 한 방법으로는 Echo packet을 전송하는 것이다. A seq# age B 2 C 5 D 2 B seq# age A 2 C 3 D 2 C seq# age A 5 B 3 D 3 E 1 F 1 D seq# age A 2 B 2 C 3 E 1 E seq# age C 1 D 1 F 1 F seq# age C 1 E 1

Link state routing의 예(2) Step 2: 링크 상태 정보를 모든 노드들에 전달한다. link state packet을 만든다. 모든 노드에 flooding한다. Step 3: 최단 경로를 계산한다. 전달받은 링크 상태 정보에 기초하여 각 노드는 링크 상태 DB(link state database)를 만든다. Dijkstra algorithm을 사용하여 최단 경로를 계산한다. Link State 정보를 전파 각 라우터는 이웃하는 라우터의 link state를 네트워크의 다른 라우터에 알려준다. 먼저 자신의 link state packet을 구성한다. 위의 그림은 초기 상태에서 각 라우터의 link state packet을 보여 주고 있다. distributing하는 방법으로는 sequence number를 이용한 flooding을 사용한다.

Link State Database B C F A D E Link # Cost 5 1 3 3 2 2 1 3 2 1 A-B A-C A-D B-A B-C B-D C-A 2 5 3 D-E E-C E-D E-F E-E 1 C-B C-D C-E C-F D-A D-B D-C

AS 간(inter-AS) 라우팅: BGP (Border Gateway Protocol) BGP를 통해서 각 AS는 이웃 AS로부터 서브넷 도달 정보(subnet reachability information)를 얻는다. AS내의 모든 라우터에 이 도달 정보(reachability information)를 전달한다. 도달 정보와 정책(policy)에 근거하여 목적지 서브넷에 도달하기 위한 “good” 경로를 결정한다.

BGP 메시지 OPEN: TCP 연결 설정하고 인증 UPDATE: 새로운 경로를 알려줌 BGP 메시지는 TCP를 사용. BGP 메시지: OPEN: TCP 연결 설정하고 인증 UPDATE: 새로운 경로를 알려줌 KEEPALIVE: UPDATE 메시지를 보내지 않을 경우 상대방의 상태를 확인 NOTIFICATION: 에러를 보고하거나 연결을 종료

BGP 예(1) AS 1 N1 AS 2 N2 R1 1 N3 R2 1 R51 AS 3 R3 AS 5 R52 R4 AS 4

BGP 예(2) R1(AS1의 BGP 라우터) R2, R3(AS2와 AS3의 BGP 라우터) IGP를 통해서 AS1 내의 네트워크 정보를 수집 R1은 BGP UPDATE 메시지를 모든 이웃 BGP 라우터에 보낸다. The UPDATE message에는 다음의 정보 포함: AS_Path: {AS1} Next_Hop: {R1’s IP address} NLRI: {N1, N2, N3} R2, R3(AS2와 AS3의 BGP 라우터) R1으로부터 UPDATE 메시지를 받은 R2과 R3는 R1을 통해서 도달 가능한 AS1 내의 네트워크가 무엇인지 알게 된다.

BGP 예(3) AS 1 N1 AS 2 N2 R1 N3 R2 2 R51 AS 3 R3 AS 5 2 R52 R4 AS 4

BGP 예(4) R2은 R51에게 다음의 정보를 포함한 UPDATE message를 보낸다. AS_Path: {AS1, AS2} Next_Hop : {R2’s IP address} NLRI: {N1, N2, N3} R3는 R4에게 다음의 정보를 포함한 UPDATE message를 보낸다. AS_Path: {AS1, AS3} Next_Hop : {R3’s IP address}

BGP 예(5) AS 1 N1 AS 2 N2 R1 N3 R2 R51 AS 3 R3 AS 5 3 R52 R4 AS 4

BGP 예(6) R4는 R52에게 다음의 UPDATE message를 보낸다. AS_Path: {AS1, AS3, AS4} Next_Hop : {R3’s IP address} NLRI: {N1, N2, N3}

BGP 예(7) AS 1 N1 AS 2 N2 R1 N3 R2 R51 AS 3 R3 AS 5 R52 R4 AS 4

BGP 예(8) R51와 R52(AS5의 BGP 라우터들) R2로부터 UPDATE 메시지를 받은 R51은 다음의 사실을 알게 된다. AS1의 네트워크들은 R2를 통해서 도달 가능하다. 그 경로는 {AS2, AS1}이다. R4로부터 UPDATE 메시지를 받은 R52은 다음의 사실을 알게 된다. AS1의 네트워크들은 R4를 통해서 도달 가능하다. 그 경로는 {AS4, AS3, AS1}이다. R51와 R52는 BGP UPDATE 메시지를 교환한다. 이들은 더 좋은 경로를 선택한다. 경로를 선택할 때 UPDATE 메시지에 있는 AS-path list를 참조하여 다음의 사항을 결정한다. 경로에 순환이 있는가?(Route loop) 최단 경로에 근거한 경로의 선택(shortest path vector) AS policy에 근거한 경로 선택(policy routing)