forwarding: router의 input link에서 output like로 packet을 전달하는 내부 동작.
routing: forwarding + network의 모든 router(between a source and a destination)의 packet path를 결정하는 것.
packet switch: packet header의 내부 field value에 따라 input link interface에서 output link interface로 packet을 전달하는 장비.
- link layer switch: like layer field value에 근거하여 forwarding을 결정
- router같은 packet switch는 network layer field value에 근거하여 forwarding을 결정.
network layer도 transport layer 처럼 connection oriented service와 connectionless service를 제공하는데, connection oriented service를 Virtual-circuit network라 하고, connectionless service를 datagram network 이라고 한다.
transport layer에서의 connection 구현은 오직 host에서만 이루어지지만, network layer에서 connection 구현은 network core의 router에서도 구현된다.
* Virtual Circuit(VC) network의 구성
1. source와 destination간의 path(links and routers)
2. path에 있는 각 link마다 부여되는 virtual numbers
3. path에 있는 각 router forwarding table안의 entry
* 어떤 VC에 속하는 packet은 header안에 virtual number(VC number)를 갖으며, 각 VC는 각 link에서 서로 다른 virtual number를 가지므로, 중간에 있는 router는 전달 packet의 VC number를 새것으로 바꿔줘야 하며, 새 VC number는 forwarding table에서 얻는다.
* VC network에서 network routers는 current connection에 대한 connection state information을 유지해야 한다. (statefull network)
* VC의 동작
1. VC setup: 송신 transport layer는 network layer와 접촉하고, 수신자 주소를 명시하여 network가 VC를 설정할때까지 기다임. network layer는 packet이 이동할 path(links, routers)를 결정하고, 경로상의 각 link에 대해 VC 번호를 결정한다. 마지막에 경로상의 각 router의 forwarding table에 entry를 추가한다.
2. data transmission
3. VC 연결 해제: 송신자 또는 수신자가 network layer에 해제를 알리면 모든 VC setup에서 설정한 것을 해제한다.
* Host가 VC의 시작이나 종료를 알리기 위해 보내는 message와 VC를 setup 하기 위해 routers 사이에서 전달되는 message를 signaling message라고 하고, 이러한 message 교환에 사용되는 protocol을 signaling protocol 이라고 한다.
* Datagram network
host에서 packet을 보낼때 packet에 destination의 address를 찍어 network로 보냄. VC 설정이 아니므로 connection information을 저장할 필요가 없다.
packet은 일련의 router를 지나는데, packet의 목적지 주소를 이용하여 packet을 forwarding 한다. 즉, router는 destination address를 link interface에 대응시킨 forwarding table을 가지고, packet안의 destination address를 이용하여 table에서 적절한 output link interface를 찾아 해당 link의 interface로 packet을 전달한다.
* table에서 적절한 output 의 link를 찾는 것을 lookup 이라고 한다.
이때 사용하는 것이 IP address의 longest prefix matching ruls(최장프리픽스 대응 규칙)이다.
IP address를 보고 가장 긴 매칭을 보이는 output link를 적절한 link라고 생각하여, 그쪽으로 해당 packet을 보냄.
* forwarding table은 routing algorithm에 의해 수정되는데 보통 1~5분마다 갱신된다.
* router의 구조
- input port: router로 들어오는 physical link와 연결. routing protocol 의 정보를 전달하는 control packet은 input port에서 routing processor로 전달된다. 또한 data link layer의 기능을 수행.
routing processor가 forwarding table을 계산하지만 일반적으로 forwarding table의 복사본이 각 input port에 저장되고, 필요시 routing processor에 의해 갱신된다.
따라서, input port의 forwarding 결정은 이 복사된 table을 보고 routing processor가 아닌 각 input port에 의해서 이루어진다.
이러한 distributed forwarding은 router 내부의 병목 현상을 방지한다.
이러한 능력이 제한된 router는 processor가 직접 table을 검색하고, 적절한 output port로 packet을 전달한다. (예: server가 router기능을 한다면, CPU가 routing processor이고, input port는 network interface card(Ethernet card)가 된다.)
forwarding table의 lookup은 table에서 longest prefix matching ruls을 찾으면 된다.
* table search: lookup에 걸리는 시간은 packet을 받는데 걸리는 시간보다 짧아야 한다. backbone network 같은 곳에서는 초당 몇백만개를 검색할지도 모른다. 많은 entry를 가진 forwarding table에서 linear search는 부족하다.
tree 구조: binary tree data 구조에 forwarding table entry를 저장한다. tree의 각 level은 destination address에 대응하는 비트이다. 첫번째 address bit가 0이면 왼쪽 서브트리, 1이면 오른쪽 서브트리.. 이런식으로 하면 N단계(N: address의 bit 수)에서 forwarding table의 entry를 찾을수 있다. 32bit IP address라도 그리 빠르지는 않다고 한다.(각 단계에서의 메모리 접근시간이 필요.)
CAM(content addressable memories): 32bit IP address를 CAM으로 표현하여 forwarding table entry의 내용을 일정 시간 동안 유지한다. - switching 구조: router의 input port를 output port로 연결
이 구조를 통해 packet은 input port에서 output port로 이동한다.
* memory를 이용한 교환: packet이 도착하면 input port는 routing processor에게 interrupt를 보내서 packet을 processor memory에 복사한다. routing processor는 header에서 destination address를 찾고, 다음에 routing table에서 적절한 output port를 탐색하고, output port buffer에 packet을 복사한다. 요즘에도 사용되지만 바뀐점은 input line의 card의 processor가 주소의 탐색과 적절한 메모리 공간으로 packet을 저장한다.
* bus를 통한 교환: input port는 routing processor를 통하지 않고 packet의 공유 bus의 output port로 직접 전달한다. 공유되는 bus로 인해 한번에 한 packet만이 bus를 통해 전달된다. 만약 다른 packet이 bus를 사용중이면 도착한 packet은 input port에서 대기한다.
* intercennection을 통한 교환: crossbar switch라고 하며, n개의 input port와 n개의 output port로 연결된 2n개의 bus들로 구성된 네트워크이다. input port의 packet은 port와 연결된 수평의 bus를 따라 해당되는 output port로 향하는 교차된 수직의 bus를 만날때까지 이동한다. 수직의 bus를 다른 packet이 사용중이라면 해당 packet은 blocking 되거나 input port에서 대기한다. - output port:switching 구조를 통해 전달될 packet을 저장한 다음 output link로 packet을 전송함. data link layer의 역할을 수행. 전형적으로 physical link가 양방향이면 input port와 output port는 한쌍이 된다.
output port의 memory에 있던 packet을 output link로 전달하는 것이다. switch 구조에서 나온 packet은 output port의 buffer에 저장되면 data link layer의 처리를 거쳐 link로 나가게된다. - routing processor: routing protocol을 수행, routing information과 forwarding table을 유지, network 관리기능을 수행.
input port와 output port에는 finite buffer가 존재한다. 따라서 packet의 도착속도가 router의 처리속도보다 크면 buffer가 차기시작하고, 결국 buffer가 꽉차면 packet은 버려지게 된다.
- HOL(head-of-the-line) blocking: input port의 buffer에서 전송되기를 기다리는 packet들은 한번에 하나씩 switch에 의해 output port의 buffer로 이동된다. 따라서 B input port buffer의 packet이 B라는 output port의 buffer로 가려고할때(B의 output port buffer는 비어있음. 가기만 하면 link로 나감. 즉, 바로 전송가능.), switch가 B가 아닌 A 또는 C등의 input port의 buffer의 packet을 선택한다면 B input port의 buffer는 대기해야만한다. B output port가 일을 하지 않는데도 말이다. 이것을 HOL blocking 이라고 한다.
output port의 경우, switch의 처리 속도가 output port가 link로 내보내는 속도보다 크다면, 한 단위시간(router의 내부에서 switch가 packet을 전송하는 시간)에 하나의 packet을 전송하므로, output port의 buffer에 packet이 쌓이면서 결국, packet loss가 발생한다.
연구 결과 필요한 buffer의 양은 B= RTT*C/ root(N)이다. C는 link의 대역폭, N은 TCP의 흐름.
router의 output port의 결정은 output port의 packet scheduler가 전송을 위해 대기하는 packet 중하나를 선택함으로써 이루어진다. FCFS, WFQ(weighted fair queuing) 등을 사용한다. QOS에 영향을 많이 끼친다.
* IP(Internet Protocol): forwarding and address system
- network layer의 packet을 datagram이라고 한다. IPv4의 datagram의 주요 field:version number, header length, TOS(service type), datagram length, fragmentation offset, TTL(Time-to-live, datagram이 network에서 routing loop에 빠지지 않게 한다. router를 거칠때마다 값이 감소하며, TTL field value가 0이 되면 datagram은 폐기된다.), protocol(final destination에 도착히 TCP(6), UDP(17)인지를 알려준다.), header check sum, source address, destination address, data(payload)
- IP datagram의 fragmentation
link layer의 protocol은 경우에 따라 전송가능한 packet의 size가 달라진다. (예를 들면, Ethernet packet은 1500byte이상, 장거리링크는 576byte 이상 전달 할수 없다. )
link layer packet이 전달할 수 있는 최대 양을 MTU(maximum transmission unit)이라하며, 이 MTU에 의해 IP datagram의 길이에 제약이 걸린다.
따라서, output link가 IP datagram의 길이보다 작은 MTU를 갖는다면 IP datagram을 나누어서 여러개의 datagram으로 만들어 link로 내보낸다. 이 fragments는 destination의 transport layer에 도달전 다시 재결합한다.(final destination에서 함.)
따라서, 이러한 fragment를 만들때, source address, destination address 에 추가로 identifier number를 포함시켜, destination에서 재결합하게 한다.
fragment의 loss를 알기위해 마지막 조각은 identifier number가 0이고, 다른 모든 fragment의 identifier number는 1이된다. 또한 재결합을 위해 offset field를 사용한다.
이러한 fragmentation은 network를 혼잡하게하고, router의 구현을 어렵게하며, destination에서 예기치 못한 fragment를 받게 할 수도 있다. - IPv4의 address system
IP address는 32bit, 64bit가 존재하며, 2^32, 2^64개의 사용가능한 IP 주소를 만들어 낸다. 모든 host와 router는 유일한 IP address를 갖는다.
이 IP address는 연결된 subset이 결정하게 된다. hosts와 router interface로 구성된 network를 subnet이라고 보통 말한다. (router 없이 바로 network에 연결되는 경우도 있음. 이런 경우는 잘 모르겠음.)
subnet의 router 주소가 223.1.1.xxx 라면 그 하위의 hosts는 223.1.1.1~223.1.1.225의 주소를 갖게 된다. IP address system에서 subnet에게 할당하는 주소의 형태는 223.1.1.0/24 라는 것이다. 맨 오른쪽 24의 의미는 맨 왼쪽부터 24bit가 subnet address라는 것이다.
한 subnet에서 모든 devices는 같은 subnet address를 갖는다. 그런 subnet이 굉장히 많이 존재하며, 서로 다른 subnet은 다른 subnet address를 가져야 한다.
하지만 실제로 subnet address는 같을 때도 많다.
* Internet address allocation method: CIDR(Classless Interdomain Routing)
subnet address 쳬계 표기를 일반화하고, subnet address체계로서, 32bit IP address를 두부분으로 나누고, 이것을 다시 점으로 된 십진수 형태의 a.b.c.d/x로 만듦. x는 조소 첫 부분의 비트수.
a.b.c.d/x에서 MSB(most significant bit, 최상위 비트)를 의미하는 x는 IP address의 network 부분을 구성. 이것을 prefix or network prefix 라고 함. (보통 한 기관은 공통의 prefix를 갖는 주소 범위를 할당 받음.)
address의 나머지 32 - x bit 들은 기관 내부에 같은 network prefix를 갖는 모든 devices를 구별한다.
CIDR 이전에는 IP address의 network 부분을 8,16,24bit로 제한하여 A, B,C network로 분류하였다.(classful addressing)
broadcast address: 255.255.255.255 인 datagram을 보내면 같은 subnet의 모든 host에게 전달됨. host에서 IP address를 얻기위해, ISP에 접촉하여야 한다.
만약 A가 alpha라는 ISP 업체에 의해 주소를 받고, alpha의 subnet이 200.23.16.0/20 일때, A는 200.23.18.0/23 같은 주소를 얻을수 있을 것이다. 근데 A가 alpha를 사용하다가 beta ISP 업체로 바꾸고 싶은 경우는 어떻게 할까?
A는 계속해서 200.23.18.0/23을 유지하면서, beta 도 200.23.18.0/23을 서비스한다. alpha도 계속해서 서비스를 하지만 longest prefix matching ruls에 의해 beta의 address가 선택되어 사용된다.
한 기관이 ISP로부터 address block을 할당 받아(위의 A의 address와 같은 형태), 기관 내부의 host와 router interface에 이것을 할당할 수 있다. host에 IP를 할당하는 것은 수동으로 가능하지만 현재는 동적 호스트 구성을 더 많이 한다. 이것이 DHCP 이다.
DHCP는 host IP가 고정으로 할당되거나 유동으로 할당되게 할수 있으며, IP address 뿐만 아니라 subnet mask, 첫번째 hop router(default router), local DNS server address 같은 것을 제공한다.
자동으로 host와 network을 연결시켜 주므로, DHCP를 Plug-and-play protocol 이라고도 한다. 무선 LAN에서도 많이 사용된다.
DHCP server는 message를 받고, 응답한다. (이때도, host의 IP가 아직 안정해졌으므로, broadcasting을 한다.) subnet에서 여러 DHCP server가 존재하면 최적의 위치에 있는 DHCP server를 선택한다. 이때, server는 host에게 message를 주는데 여기에는 server에 수신된 message의 트랜잭션 ID, host에 제공된 IP address, network mast, IP address 유효 시간(보통 몇시간~ 며칠) 이다.
DHCP request: host는 받은 message를 보고 자신의 설정을 한 후 DHCP request message로 응답한다.
DHCP ACK: server는 request message에 대해 DHCP ACK message로 응답한다.
* NAT
* ICMP
* IPv6
* routing algorithm
Objective: 최소비용 path를 찾아서 packet을 전달한다.
- Global routing algorithm: network에 대한 완벽한 전체 정보를 가지고 source와 destination 사이의 최소비용경로를 계산.예: Link-state(LS, 링크상태) algorithm
- distributed routing algorithm: 최소비용경로의 계산이 반복적이고, 분산된 방식으로 수행, network의 모든 정보를 갖고 있지 않고, 대신 각 노드는 link에 직접 연결된 link의 cost에 대한 정보만 가진다. 예: Distance-vector(DV, 거리벡터) algorithm
이외에 routing algorithm을 분류할때, static과 dynamic의 형태로 나누기도한다. static은 path가 아주 느리게 변화하는 것이고, dynamic은 network traffic load나 topology의 변화에 따라 routing path를 바꾼다.
또한 하부 link에 혼잡수준이 반영되는 routing algorithm도 있다. 현재 Internet routing algorithm인 RIP, OSPF, BGP 등은 network의 혼잡을 반영하지 않는다.
* Link state(LS) routing algorithm
- network topology 상의 모든 link cost를 이미 알고 있는 상태에서 path를 찾는 것으로 각 노드가 link의 cost와 식별을 포함하는 packet인 link state packet을 network 상의 다른 노드로 broadcasting 함으로써 만들어진다.
- Link state algorithm은 Dijkstra's algorithm이며, 이와 비슷한 prim's algorithm이 존재한다. Dijkstra algorithm은 한 노드에서 다른 모든 노드에 이르는 최소비용경로를 모두 계산한다. (Dijkstra algorithm 하는 방법은 생략.- 어렵지 않음)
- time complexity: 첫번째 iteration에서 shortest path에 들어가있지 않은 노드를 모두 체크하므로 출발지를 뺀 n개의 노드가 있을때, n개의 노드를 모두 체크한다. 두번째 반복에서 n-1개의 노드를 체크한다. 따라서 총 체크하는 노드의 수는 n(n+1)/2 이므로, O(n^2)이 된다.
- problem: 혼잡이나 지연을 기반으로하는 link방식을 기반으로 사용하는 모든 알고리즘에서 진동문제가 발생한다.
즉, time t에 x에서 y로 가는 path가 x-a-b-c-y라면 routing 결과 packet이 그 path를 따라간다. traffic이 어느정도 쌓이면 x에서 y로 가는 path는 다시 x-q-w-e-r-y 같은 방향으로 바뀐다. 이런경우 계속 방향만 바뀌다가 수렴하지 않을 수도 있다. - solution: routing의 Objective는 높은 지연을 가진 혼잡한 link를 피하는 것이므로 traffic은 고려되어야만 한다. 위와 같은 problem을 피하기 위해서는 동시에 모든 router가 LS algorithm을 수행하지 못하게 한다. 웃기게도 router들은 스스로 자기 동기화가 된다고 한다. 따라서, 이러한 문제를 또 막기위해 LS algorithm의 결과를 송신하는 시간을 각 노드가 임의로 처리하도록 한다.
* Distance-Vector algorithm
반복적이고, 비동기적이며 분산적인 algorithm
- 직접 연결된 neighbor가 주는 정보로 계산하고, 결과를 neighbor에게 알린다는 점에서 distributive 이며, neighbor과 정보를 교환하지 않을 때까지 지속한다는 점에서 iterative이며, 모든 노드가 asynchronous 방식으로 동작한다.
- Bellman-Ford equation: 노드 x에서 노드 y로 가는 최소비용경로의 비용을 dx(y)라할때,
dx(y) = min_v{c(x,y) + dv(y)}이다. min_v는 모든 x의 neighbor에 대해 적용됨. x에서 v로 간다음 v에서 y까지의 최소비용경로를 택할떄 최소비용은 c(x,y) + dv(y) 가 된다. - Bellman-Ford equation의 중요성: bellman-Ford의 답은 노드 x의 forwarding table의 entry를 제공한다. v*를 dx(y) = min_v{c(x,y) + dv(y)}에서 최소치의 이웃 노드라고 할때, x가 y에게 packet을 보낼때, 노드 x는 packet을 v*로 전달해야 한다. 그러므로, 노드 x의 forwarding table은 목적지 y에 대한 다음 hop router로 v*를 지정해야 한다.
각 노드가 자신의 neighbor에게 자신의 DV의 복사본을 보낸다. 노드 x가 neighbor v로부터 DB를 수신하면, v의 DB를 저장하고, Bellman-Ford equation을 이용하여 자신의 DV를 수정한다. 수정이 끝나면 노드 x는 수정된 DV를 자신의 neighbor들에게 보내어 그들도 자신의 DV를 수정하게 한다. (최단거리의 값이 바뀔때만 neighbor node에게 정보를 보낸다.) - (알고리즘은 생략 쉬움) - problem: 중간에 이동하는 routing table의 정보들이 잘못된 경우. link cost가 증가된 경우(routing loop가 발생 엄청나게 오랜 시간 후에 loop가 멈춤).(cost가 감소된 경우는 잘 작동함.)
- solution: poison reverse(수정된 경로가 있다면 원래 있던 경로의 cost를 무한대로 설정) 하지만 세 개 혹은 더 많은 노드를 포함한 routing loop는 감지 할 수가 없다.
* DV vs LS
network를 graph로 표현하면, N은 a set of node, E는 a set of edge이다.
- message의 복잡성: LS에서 각 node는 network의 각 link cost에 대해서 O(|N||E|)개 message를 보냄. 각 link cost가 변할때마다 새로운 link cost가 모든 노드에게 전달되여함.
DV에서는 각 노드는 직접 연결된 neighbor와 message를 교환. 단, 알고리즘이 수렴하는데 걸리는 시간이 많이 걸릴수 있다. - 수렴속도: LS의 경우 O(|N|^2) 알고리즘이고, DV는 매우 천천히 수렴하며, routing loop가 발생할 수도 있다.
- robust: LS에서 변질되거나 잘못된 table 정보가 broadcasting 되는 경우 문제가 발생. DV에서는 잘못된 노드 계산이 전체 network에 확산될 우려가 있음. 따라서, 어느것이 더 좋다는 결과는 얻을수 없다.
* router의 수가 증가함에 따라 routing table 정보 계산, 링크 상태 갱신 등에 따른 통신에 관련된 overhead가 증가. 오늘날 Internet은 수백만개 이상의 host로 구성되므로, 각 host의 routing 정보를 저장하려면 엄청난 메모리가 필요. 또한 상태 정보를 갱신하는 packet은 막대한 traffic을 초래한다. 그리고, DV algorithm 은 절대 수렴되지 않을 것. 또한, 외부와 내부 network로 분리하여, 다른 policy로 운영하고자하는 시도도 있다.
* Autonomous system(AS, 자치 시스템)
router를 grouping한다. 같은 AS안에 있는 router는 같은 routing algorithm을 사용한다.
AS 내부에서 동작하는 routing algorithm을 intra-autonomous system routing protocol이라고 한다.
또한 여러 AS를 연결하는데 AS 내부의 하나 이상의 router가 AS 외부 목적지로 packet을 routing 할 책임이 있다. 이러한 역할을 하는 router를 gateway routers라고 한다.
* AS1, AS2가 존재할 때, AS1과 AS2의 routing protocol을 서로 다르게 할 수도 있다. 하지만, AS1의 한 host A 가 AS1 외부 목적지로 packet을 전송할때, host A는 AS1의 gateway routers를 이용하여 보낸다. AS1은 연결된 AS2를 통하여 어느 목적지가 도달가능한지, AS2를 통하여 어느 목적지가 도달가능한지를 배운다. 이 도달성 정보를 AS1 내부의 모든 router들에게 전파하고, 각 router는 외부 AS 목적지들을 처리 할수 있는 forwarding table을 구성할 수 있다. 이러한 것을 위해서는 AS1과 AS2가 같은 intra-AS routing protocol을 수행해야 한다.
* Hot potato routing
AS는 가능하면 빨리(가장 적은 비용) packet(potato)을 처리한다는 의미.
router가 packet을 목적지로 가는 경로의 모든 gateway 중에서 최소의 router-gateway cost를 갖는 gateway router로 보낸다는 것이다.
* ISP 와 AS의 관계
아마도 한 ISP 안의 router과 이를 연결하는 link들이 하나의 AS를 구성한다고 생각해도 될것이다.
오늘날 사용되는 intra-AS routing protocol은 RIP, OSPF, BGP 등이 있다.
intra-AS routing protocol을 interior gateway protocol(내부 게이트웨이 프로토콜) 이라고 하기도 한다.
* RIP(Routing Information Protocol)
DV algorithm을 사용.
cost 측정 방법으로 hop의 수를 사용한다. 즉, 각 link는 1이라는 cost를 갖음.
source router에서 destination subnet까지의 최단 경로를 지나는 subnet의 숫자를 의미하는 hop를 사용함.
최대 경로비용은 15로 제한되며, RIP를 AS에서 사용하는 경우 15hop 이하로 한다.
DV에서는 이웃하는 routers가 routing 정보를 서로 교환한다. 한 router에서의 DV는 AS안에서 그 router로부터 subnet까지의 최단 경로 거리의 현재 예측치인 것이다.
RIP에서 routing table은 RIP 응답 message를 사용하여 약 30초마다 이웃끼리 서로 교환한다. host나 router가 보내는 응답 message는 AS안의 25개 목적지 subnet에 이르기까지 송신자의 routing table entry에 포함되며, 이 응답 message를 RIP Advertisement(RIP 광고)라고 한다.
routing table은 RIP table이라고 불리며, {목적지 서브넷, 다음 router, 목적지까지의 홉 수} 로 구성된다. 즉, 목적지 서브넷 까지 가는데 A 라우터를 통해야 되고, 홉의 수는 x개다 라는 의미이다.
30초뒤에 router는 다른 router로부터 RIP Ad를 받는다. 만약 최소 180초 이상 다른 이웃 router에게 RIP Ad를 받지 못하면, 그 이웃은 죽거나, 연결 link의 고장으로 간주한다. 수신된 RIP Ad에서 최단 경로의 정보를 보고 자신의 RIP table을 수정한다.
router는 RIP request message를 통해 어떤 목적지의 이웃의 cost를 알아낼수도 있다. UDP를 사용한다.
* OSPF
RIP보다 좀더 높은 단계의 ISP들에 의해 사용된다. LS정보를 flooding(어떤 노드에서 온 하나의 패킷을 라우터에 접속되어 있는 다른 모든 노드로 전달하는 것.)시키고, Dijkstra's algorithm을 사용하는 Link State algorithm이다.
router는 자신을 root node로 간주하고, 모든 subnet에 이르는 최단경로 트리를 결정하기 위해 Dijkstra's algorithm을 사용한다. link cost는 network 관리자가 구성할수도 있다.(모든 link cost를 1로 하여 최소 hop routing이 되게 할수도 있고, 낮은 대역폭 link의 사용을 억제하기위해 link cost를 올릴수도 있다. - 이를 위한 매커니즘도 있음)
AS에서 인접한 router뿐만 아니라 다른 모든 router에게 routing information을 link state가 변경될때마다 broadcating하며, link state가 변경되지 않아도 최소 30분 정도 마다 정기적으로 link state를 broadcating한다.
OSPF router 사이에서의 모든 정보 교환은 인증을 받아야 한다. 또한, 동일한 cost를 갖는 목적지까지의 여러 path가 존재할때, OSPF는 여러 경로를 사용할 수 있다.
그리고 AS를 계층적으로 조직화 할 수 있다.
계층적인 조직은 OSPF AS는 area로 구성하고, 각 area는 자신의 OSPF link state routing algorithm을 수행한다. 한 area가 다른 area를 볼수 없다. 각 area에서 하나 혹은 그 이상의 area border router가 외부 area와의 packet routing을 수행한다. AS에서 하나의 OSPF area가 backbone area가 되며 AS area 사이에서의 traffic routing을 담당한다.
* BGP4(Border Gateway Protocol)
- 사실상 표준 inter AS routing protocol. 단순히 BGP 라고함.
- 각 AS에게 이웃 AS들로부터 subnet 도달성 정보를 얻음, AS 내부의 모든 router에게 도달성 정보를 전파, 이 정보를 이용하여 좋은 path를 결정.
- 반영구적인 TCP 연결을 사용한다.
- 서로 다른 AS의 두 router를 연결한는 BGP TCP 연결이 있으며, AS 내부의 routers에서도 TCP 연결이 사용된다. 각 AS안에서 TCP mesh 연결이 생성된다.
TCP 연결에서 양 끝의 두 router를 BGP peer라하고, 그 연결로 BGP message가 보내지는 TCP 연결을 BGP session 이라고 한다. - 두 AS에 걸치는 BGP session을 external BGP(eBGP,외부 BGP) session 이라하며, 같은 AS 내부 router간의 BGP session을 internal BGP(iBGP, 내부 BGP) session 이라한다.
- BGP에서의 destination은 host가 아니고 CIDR된 prefix이다. each prefix는 subnet or a set of subnet이다. AS2에 접속된 138.16.64/24,138.16.65/25,138.16.66/24, 138.16.67/22 가 있을때, AS2는 이것의 prefix를 합하여 BGP를 통해 AS1에게 138.16.64/22로 하나의 prefix를 광고한다.
AS에게 광고한다는 의미는 해당 그 prefix로의 어떤 datagram도 전달한다는 뜻이다. - 도달성 정보분배: 각 AS의 gateway routers는 다른 AS의 gateway routers에게 자신을 통해 도달가능한 prefix의 list를 보낸다. gateway routers가 eBGP session을 통해 prefix list를 받으면 자신의 iBGP session을 사용하여 그 prefix list를 자신의 AS 내부의 다른 모든 routers에게 분배한다.
- ASN(autonomous system number)
BGP에서는 AS number를 통해 각각의 AS를 식별한다.(AS number가 없을 수도 있다.)
router BGP session을 통해 prefix를 광고할때, prefix와 함께 몇개의 BGP attribute가 같이 광고된다. BGP 용어로 이 속성들과 함꼐 광고되는 prefix를 route 라고 한다. 따라서 BGP peer는 서로 route 광고를 하는 것이다.
- AS-PATH attribute: AS간의 광고 경로를 보여주는 속성으로, 한 prefix가 AS2로부터 AS1으로먼저 광고가 되면, AS1이 그 prefix를 AS3로 광고하면 AS-PATH는 AS2 AS1이 된다. 이 속성은 looping 광고를 방지하는데 쓰인다.
- NEXT-HOP attrebute: inter AS와 intra AS routing protocol 사이에 정밀한 link를 제공하기 위해 NEXT-HOP 이 사용된다. NEXT-HOP은 AS-PATH를 시작하는 router interface이다. NEXT-HOP은 AS2에서 AS1로 packet을 보낼때 AS1에서 packet을 받게되는 gateway router의 여러 interface들중 하나의 IP address값이다. AS2의 특정 router가 packet을 AS1로 보낼때, 즉, AS-PATH속성이 forwarding table을 설정하는데 사용된다. AS1의 router는 AS1의 gateway router(NEXT-HOP의 IP address를 갖는 외부 AS의 gateway로 가기전에 거치는 바로전 router)로 가는 최단 경로를 계산한다. - BGP에서 path의 선택은 중간에 지나가는 AS가 제일 적은 것을 선택하든(단, AS안에 router 개수가 몇개인지 모름) 가장 가까운 NEXT-HOP router를 갖는 route가 선택되기도 한다. 여기서 가장 가깝다는 것은 intra AS algorithn에 의해 결정된 최소비용 경로의 비용이 최소인 router이다. 이 것이 hot potato routing 이다.
- 왜 interAS와 intra AS routing이 따로 존재하는가?
AS사이에서의 정책문제, 대형 네트워크에서의 확장성, 성능 문제.
댓글 없음:
댓글 쓰기