=== Network Layer ===

1. Network Layer

• Transports segments from sending to receiving host : sending 부터 receiving host까지 segment를 전달해주는 역활
• On sending side, encapsulates segments into datagrams : segment를 transport에서 받아서 datagram을 만든다.
• On receiving side, delivers segments to transport layer : receiving쪽에서 datagram에서 header를 떼고 segment를 transport로 보내준다.
• Network layer protocols in every host, router : 네트워크 레이어는 라우터에도 구현되어 있는 중요한 레이어
• Router examines header fields in all IP datagrams passing : 라우터가 header를 보고 필요한 처리를 하고 그 다음 라우터로 전달해주는 방식

라우터에도 네트워크 레이어가 존재하여서 경로를 따라 가다가 receiver에게 전달해준다.

Network Layer Functions

하는 일 크게 2가지는 Forwarding, Routing이 존재한다.

• Forwarding: move packets from router's input to appropriate router output : router에 input쪽으로 패킷이 들어오면 어떤 outer로 갈지를 결정하고 전달해주는 기능이다.
  • analogy: process of getting through a single interchange
  • DATA PLANE : Forwarding을 담당하는 부분
    http://egloos.zum.com/mcchae/v/11161822
• Routing: determine route taken by packets from source to destination : 목적지까지가는 경로를 어떻게 설정할 것인가를 결정하는 것
  • analogy: process of planning trip from source to destination
  • CONTROL PLANE : 이러한 경로를 설정하는 것을 CONTROL PLANE이라고 부른다.

---

(요약)
network-layer function

• forwarding : router에 input쪽으로 패킷이 들어오면 어떤 outer로 갈지를 결정하고 전달해주는 기능이다.
  • DATA PLANE : Forwarding을 담당하는 부분 -> 완전 하드웨어적인 부분
• routing : 목적지까지가는 경로를 어떻게 설정할 것인가를 결정하는 것
  • CONTROL PLANE : 이러한 경로를 설정하는 것을 CONTROL PLANE이라고 부른다. -> 데이터그램이 src에서 dest까지의 어떤 경로를 갈지 선택하는 것

---

Network Layer: Data Plane

• Local, per-router function
• Determines how datagram arriving on router input is forwarded to router output port
• Forwarding function

Network Layer: Control Plane

Data Plane을 어떻게 보낼지를 결정하는 것을 Control Plane에서 결정하게 된다.

• Network-wide logic : 라우터끼리 정보를 교환해서 어떤 경로를 선택할지 결정한다.
• Determines how datagram is routed among routers along end-to-end path from source host to destination host
• Two control-plane approaches
  • traditional routing algorithms: implemented in routers : 라우터끼리 메세지를 주고받아서 경로를 설정하는 알고리즘
  • software-defined networking (SDN): implemented in (remote) servers : 서버에서 자체적으로 여러 라우터들에 대해서 계산하고 라우터는 서버의 지시에 따라서 데이터를 forwarding하는 방식

---

(요약)
1. traditional routing
2. software-defined networking(SDN)

---

Pre-Router Control Plane

• Individual routing algorithm components in each and every router interact in the control plane

각 라우터에 control plane에서 데이터끼리 메세지를 전달받아 경로를 학습하고 그것을 forwarding table형태로 data plane에 넘기어 주어서 data plane에서 forwarding table을 보고 패킷 header에 따라 어떤 output으로 보낼지를 결정한다.

---

(요약)
traditional : 각각의 라우터에 라우팅 알고리즘이 구현되어 있고 상호 통신하는 것이다.
문제점 : 각각의 라우터에 라우팅 알고리즘이 구현되어 있어야 한다. 프로그램이 설치되어 있어야 한다. 새로운 라우팅 프로토콜이 나오면 적용하기 어렵다

---

Logically Centralized Control Plane

• A distinct (typically remote) controller interacts with local control agents (CAs)

control plane부분이 remote controller에 있어서 그 서버하고 메세지를 주고 받으면서 그곳의 지시에 따라서 CA(Control Agent)가 Forwarding table을 control plane에서 받아서 data plane에서 데이터를 forwarding해주는 형태

---

(요약)
SDN에서 사용하는 방식이다.
Remote Controller를 담당하는 서버가 존재한다. Remote Controller에서 각각의 forwarding table을 계산해서 라우터들에게 알려준다.

---

Routing

• Deciding path on which packets are forwarded
• Method for routers to construct the forwarding tableIntroduction to Computer Networks : 모든 라우터에는 forwarding table이 존재

Routing
• Delivering a packet from A to F
– Router α sends packet to output port 1
– Router β sends packet to output port 2
– Router δ sends packet to output port 3

예를 들어 A에서 F로 메세지를 보낸다고 하자 sending host는 자기와 연결된 라우터로 데이터를 전달 받한다. 알파 라우터는 어떤 아웃풋으로 보낼지를 테이블을 보고 전송한다.

• How does switch α know that the packet should go through output port 1 to reach F?Introduction to Computer Networks

중요한게 그러면 어떻게 F로 갈때 output port를 1번으로 선택해야하는지 어떻게 알 수 있을까? 실재로 인터넷에서는 경로가 하나만 있는게 아닌 여러 경로가 있어서 목적지에 도달하기 때문에 어떤 경로로 가는것이 가장 적절할지 결정하는 것이 쉽지 않다. 이것을 판단해서 forwarding table을 채우는 것이 routing이 하는 일이고 거기에 들어가는 알고리즘, 프로토콜이다.

• How should we decide our path? : 경로를 선택할때 다양한 조건을 판단한다.
– The fastest : 가장 빠른 경로
– The cheapest : 가장 값싼 경로
– Possibility of getting a seat
– Shortest walking distance
– etc.

• If we choose “the fastest path”, what should we consider? : 가장 빠른 경로를 위해 무엇을 고려해야 하는가?
– Number of stations
– Time duration between stations
– Time for transfer
– ...

2. Routing protocols taxonomy(분류 체계)

도메인간의 통신 RIP, OSPF / 도메인간 데이터 전달 BGP

Intra-domain vs. Inter-domain

Introduction to Computer Networks

Autonomous Systems (AS)

• Internet: Network of Networks : autonomous system의 집합
• Autonomous System: a large network or a group of networks that has a unified routing policy : 한 autonomous system에서는 같은 policy를 사용한다. 즉 어떤 경로를 선택할지에 있어서의 결정방법
• Controlled by ISP or an organization : ISP나 기관에서 운영
• Each AS has a unique ASN (AS number) : 각 AS는 고유한 AS number가 존재

• 100,424 AS in the world
(as of April 2021)
• 1,036 AS in Korea

Intra vs. Inter-domain Routing

• Intra-domain (Intra-AS) routing

  • routing among hosts, routers in same AS ("network") : 같은 AS내에 있는 라우터, 호스트간의 라우팅을 하기 위함(AS를 망이라고 부르기도 한다)
  • all routers in AS must run the same intra-domain protocol
  • routers in different AS can run different intra-domain routing protocol
  • gateway router: at "edge" of its own AS, has link(s) to router(s) in other AS'es : 다른 AS에 있는 라우터와 링크가 있는 라우터들을 gateway router이라고 부른다.

• Inter-domain (Inter-AS) routing

  • routing among AS'es : 라우터간의 어떤 경로를 취해야하는지 결정
  • gateways perform inter-domain routing (as well as intra-domain routing) : gateway 라우터들이 inter-domain routing protocol을 부르게 된다. 또한 intra-domain도 함께 돌아가게 된다.

=== Routing Algorithms & Protocols ===

1. Distance vector routing

• Record the next node for each destination : 테이블에 각 목적지에 대한 다음 노드가 무엇인가(A에서 F가 목적지면 다음 B 라우터로 가라는 식으로 내용이 입력되어 있다.)
• Exchange tables with neighbors, and update my table using exchanged information : 이웃 라우터들하고 table을 교환하게 된다.
• Information stored at routing tables – (destination, distance, next node) -> distance vector : routing table에 필요한 정보 + cost까지 입력이 되어 있다.

Distance vector routing

• What is the shortest path from A to C?

• First we need to know the “distance” of each link
– Distance can be physical distance, but it can also mean
other things (e.g. cost)

링크에 있는 cost들을 고려해서 minimum cost한 path를 구하고자 하는것이 distance vector routing의 목적이다.

• In the routing table, a “distance vector” is stored for each destination
– distance vector = (destination, distance, next node)

• Initially, we know the paths to the direct neighbors
– A to B: distance 7: next node B
– A to E: distance 1: next node E
• Store this information in the routing table

• Initial state of routing tables for all routers

초기상태에서는 자기 이웃까지만 정보를 가지고 있다.

• Now, nodes exchange tables with direct neighbors
– Each node sends its routing table to all its direct neighborsIntroduction to Computer Networks : 자기의 직접적인 neighbor하고 table을 교환한다.

• Node D sends its table to node E(중요)
– Information sent: (destination, distance)
– Next node should be the sending node itself

E는 D의 정보를 받아서 C까지 가는 경로를 D를 경유해서 가는 경로로 추가한다.

• On receiving table from D, node E updates its routing table
– E didn’t know the path to C, but now it knows that it can reach C through node D, and the distance will be 4.
• 2 (E->D) + 2 (D->C)Introduction to Computer Networks

현재의 목적지까지의 경로와 라우팅 테이블을 건내준 노드를 통해서 갔을때의 길의 거리를 비교해서 더 짧은 것을 선택한다.

• Node B sends its table to node A

• A updates its routing table – A knows it can reach C through B, with distance 8.

• Node E sends its table to node A

• Node A updates its table
– Since distance from E to C is 4, E can reach C with distance 5.
– Now, node A knows a path to C with distance 8.
– Since the path through E is shorter, node A updates its path to C to go through E.
• If the current path is shorter or equal, it is not updated.

• All nodes exchange tables
– Send my table to all my neighbors
– If my table is updated, send my table again : 테이블이 업데이트되면 내 이웃에게 정보를 전달한다.
– Also, nodes send its table periodically : 주기적으로 라우팅 테이블을 이웃들에게 보낸다.
• node state or link distance might have changed
• After all exchanges have been finished…
이와 같은 과정을 계속 진행하다보면 결국 한 상태로 수렴된다.

• The final state of routing tables

• Suppose the link between D and E breaks
– D and E detect this event

네트워크의 변화가 일어나면 새로운 상태로 수렴하게 된다. 만약 이미 converge된 상태에서 E-D 경로가 사라진 경우를 가정하자. 그러면 E와 D는 이 사실을 알게된다.

• D and E sends the updated routing table to their neighbors, and nodes update their routing table

없어졌으면 없어진대로 새로운 경로로 converge된다.

라우팅 테이블이 converge된 상태에서 변경이 일어나면 그러면 인접한 E와 D는 원래 연결되어 있던 D와 E와 관련된 것들을 모두 infinity로 바꾸어 주어야 한다. 그 상태에서 계속해서 테이블을 교환하면 converge되어 진다.
패킷을 받을 때마다 그 값이 계속해서 바뀔 수가 있다. 패킷을 받은 곳을 기반으로 하는 entry들에 대해서 다시금 살피어봐야 한다.

• Nodes periodically exchange routing tables with direct neighbors : 노드들이 근처 라우터들하고 자주 exchange 한다.
• If there is a change in the network, the routing table will be updated to adopt the change : 만약 네트워크에 변화가 있으면 그 네트워크에 적응을 해서 그 상태에서 가장 효과적인 라우터들을 결정할 것이다.
• Each route information has a timer. If the route is not updated for a certain duration, it is invalidated. : 끊어진것을 타이머를 두고 라우팅테이블이 오는지를 체크한다.
– Suppose A has a route to C via B. If node A does not get periodic updates from B, the route to C will be removed after some time