[네트워크] 20. Unicasting Routing

routing에서 forwarding table을 통해 forwarding이 어떤 방식(protocol)에 의해서 이루어지는가?

An Internet as a Graph

• To find the best route, an internet can be modeled as a graph

• 경로의 edge의 cost를 모두 더했을 때 가장 적은 cost가 드는 길(path)을 찾는 과정 -> routing 방법
• What is cost?
  • distance
  • 몇 차선
  • 도로 요금
  • 등등... 으로 생각

 

Least-Cost Trees

• 가장 cost가 적게 드는 tree
• 7개의 노드 * 각 노드에서 다른 모든 노드로 가는 경로 6개
  • N(N-1) 개의 path를 찾는다.
  • Root node가

 

Routing Algorithms

• Several routing algorithms have been designed
• The differences between these methods are in the way they interpret the least cost and the way they create the lease-cost tree for each node
  • Distance-Vector (DV) Routing
  • Link-State (LS) Routing
  • Path Vector (PV) Routing
• DV and LS routing are based on the least-cost goal.
  • However, PV routing is based on the policy, such as safety, security, and reachability
• PV routing is mostly designed to route a packet between ISPs
  • DV, LS는 하나의 도메인 내에서

 

Distance-Vector Routing

• The first thing each node creates is its own least-cost tree with the rudimentary(기초적인, 완성되지 않은) information it has about its immediate neighbors.
  • The incomplete trees are exchanged between immediate neighbors to make the trees more and more complete and to represent the whole internet.
• In distance-vector routing, a router continuously tells all of its neighbors what it knows about the whole internet (although the knowledge can be incomplete)
• Two important topics: Bellman-Ford equation and the concept of distance vectors

다음 그림에 대해서 한번 생각해 보자.

• A라는 Router는 바로 인접한 B와 D에 대한 정보만 가지고 있는데 이를 그 인접한 애들에게 알려준다(propagation).
• 그러면 또 B라는 router는 본인과 인접한 C,A,E routers에게 A 정보를 포함한 정보를 알려준다.
• 그렇게 모든 노드에게 propagation이 진행되면 이 graph에서 모든 노드는 모든 정보를 알게된다.

 

Bellman-Ford Equation

• To find the least cost (shortest distance) between a source, x, and a destination node, y, through some intermediary nodes (a, b, c, …) when the costs between the source and the intermediary nodes and the least costs between intermediary nodes and the destination are given. Where D_ij is the shortest distance and c_ij is the cost between nodes i and j

• Bellman-Ford equation enables us to build a new least-cost path from previously established least-cost paths

• 새로운 path가 생기더라도 그 전에 값과 recursively 그 경로와 비교하여 최소 cost 경로를 선택하게 된다.

 

Distance Vectors(1st Method)

• A least-cost tree is combination of least-cost paths from the root of the trees to all the destinations. These are graphically glued together to form the tree.
• Distance vector routing unglues theses paths and creates a distance vector, a one dimensional array to represent the tree.
• Distance vector corresponding to a tree
  • 노드 별로 vector 가 존재 - 본인 노드가 root 노드로 간주
  • index: 목적지 노드
  • value: 해당 노드까지의 cost
    • A에서 A까지는 0 (A: 0)

• The fist distance vector for an internet

• Updating distance vectors

B와 인접한 노드로부터 정보를 얻어와서 원래 없던 정보를 채우는데 그 방식은

• B vector에서 새로 update 할 노드의 value(A로부터 온 D(3)) + B vector에서 해당 노드(A)의 value(2)
• 3+2 = 5

 

Distance-Vector Routing Algorithm

Problems in Distance-Vector Routing

• Count to infinity : Two-node loop example
  • (그림에서 16을 infinity로 바꾼다.)

a.

b. 만약 중간에 X에서 A로 가는 길이 failure가 발생하면 X에서 A까지 가는 cost는 무한대가 되는데 B에 있는 vector 내용은 A까지 2 distance면 갈 수 있다고 되어 있어서 B에서 A에게 주는 정보는 3인데 3은 무한대보다 작기 때문에 update가 된다.

c. A가 또 다시 update 될 것인데 3으로 update 될 것이다.

d. 그러면 B는 또 4로 update 될 것이고 빙빙빙 돌다가

e. 나중에는 둘 다 무한대가 되어버릴 것이다.

 

Solutions to Two-Node Loop

• Defining infinity: To redefine infinity to a smaller number, such as 100
  • infinity의 값을 한정된 값으로 정해 놓고 해당 값 도달 시 사실상 무한대로 간주해 버리는 것
• Split horizon: Instead of flooding the table through each interface, each node sends only part of its table through each interface. Node B eliminates the last line of its routing table before it sends it to A
  • A로부터 온 정보를 다시 A로 update하지 않는 것
• Split horizon and poison reverse: Node B can still advertise the value for X, but if the source of information is A, it can replace the distance with infinity as a warning: “Do not use this value, what I know about this route comes from you.”
  • cost 값을 infinity로 하여 너로 부터 온 것을 알게끔 하는 것
• Still three node-instability problem

 

Link-State Routing(2nd Method)

• To use “link-state” to define the characteristic of a link (an edge) that represents a network in the internet.
  • link state: 링크의 특성을 define(연결 정보)
• The cost associated with an edge defines the state of the link. Links with lower costs are preferred to links with higher costs; if the cost of a link is infinity, it means that the link does not exist or has been broken.
• Each router tells the whole internet what it knows about its neighbors
• Link State Database (LSDB): Collection of states for all links
• Distance vector Router vs. Link State Router

• Each node can create the LSDB for whole internet by flooding(홍수)
• LSP (LS Packet: the identity of the node and the cost of the link) is sent out of each interface
  • 본인이 가진 정보들을 다른 노드들에게 packet 형태로 보내는데 이를 LS packet이라고 한다.

Formation of Least-Cost Trees

Least-Cost Tree

• 전제 조건: 예제로 A를 기준(root node)으로 둠
• potential path에서 least cost tree로 유망하다 판단되면 실선인 path로 결정된다.

<과정>

• 노드 별로 돌면서 점선을 만들고 해당 경로가 예전의 길과 비교했을 때 가장 작은 길이면 해당 cost로 하는 path(실선)을 결정한다.
• 때로는 똑같은 값 중에 결정해야 하는 상황이 올 수도 있는데 그 때는 그냥 둘 중 선택을 하면 된다.

 

Path-Vector Routing(3th Method)

• ISP 간의 route에 사용
  • LS와 DV는 하나의 단위 안에서 사용하는 거라면 PV는 단위끼리 사용
• The least-cost goal, applied by LS or DV routing, does not allow a sender to apply specific policies to the route a packet may take.
  • To respond to these demands, a third routing algorithm, called path-vector (PV) routing has been devised.
  • 북한을 통해 러시아를 가는 것이 더 shortest path일 지라도 해당 경로로는 가기 힘들기 때문에 특정 poilicy 들에 기반하여 다른 path로 갈 수 있도록 routing을 해 준다.
• Spanning trees in path-vector routing

• 위 예제에서 D는 해당 노드까지는 갈 수 있는 종단의 역할은 하지만 해당 노드를 거쳐서 갈 수 있는 매개체로써는 역할을 하지 않는 것을 볼 수 있다.(특정 policy에 의해)

 

Creation of Spanning Trees

• Path-vector routing, like DV routing, is an asynchronous and distributed algorithm(독립적이고 분산적)
• Path(x,y) = best {Path(x,y), [(x + Path(v,y)]} for all v’s in the internet
• Path vector made at booting time

• Updating path vectors

• Event 1: Old C에서 B table을 통해 알 수 있는 정보와 더하여 New C를 만들어 냄
• Event 2: Old C에서 D table을 통해 알 수 있는 정보와 더하여 New C를 만드려 했으나 딱히 update할 정보가 없어서 그대로 임.

 

Path Vector Algorithm

 

---

Distance Vector vs. Link State vs. Path Vector

• 이 셋은 least cost 를 찾아가는 database
• Distance Vector와 Link State은 둘 다 하나의 domain 안에서 least cost tree를 찾아가는 것과 관련된 알고리즘이다.
  • 둘 간의 차이는 least cost tree를 찾아가는 데이터를 어떻게 모으느냐의 차이가 있다.
  • DV: 내가 알고 있는 모든 정보를 바로 이웃한 노드에게만 전달되는 방식, update 과정에서 시간차이 때문에 어떤 failure가 발생했을 때 엉뚱한 instability가 생기는 단점이 있음
  • LS: 내가 알고 있는 내 이웃에 관한 정보(Link State)를 모든 노드에게 동시에 flooding 하여 모든 노드가 synchronous하게 정보를 모을 수 있다. traffic 이 발생하는 단점이 있음.
• 이와 달리 PV는 주로 interdomain routing algorithm에 사용하는데 policy를 적용하여 특정 network는 bypass할 수 있고 특정 network는 통과하지 않을 수 있는 방식의 routing이다.
  • 기본적인 동작 방식은 DV 유사하다. 자기가 알고 있는 정보를 이웃에게만 propagation해서 순차적으로 update가 되는 asynchronous한 방식으로 동작한다.

---

Unicast Routing Protocols

• Three common protocols used in the Internet:
• Routing Information Protocol (RIP), based on the distance-vector algorithm
• Open Shortest Path First (OSPF), based on the link-state algorithm
• Border Gateway Protocol (BGP), based on the path-vector algorithm.

Hierarchical Routing

• Routing in the Internet cannot be done using a single protocol:
  • Scalability(확장성) Problem and Administrative(관리) Issue
• Hierarchical routing means considering each ISP as an AS(Autonomous System)
• Routing protocol in each AS is referred to as intra-AS routing protocol, intradomain routing protocol, or interior gateway protocol (IGP)
  • 하나의 AS 안에서 돌아가는 protocol들
• Global routing protocol is referred to as inter-AS routing protocol, interdomain routing protocol, or exterior gateway protocol (EGP)
  • 하나의 AS -> other AS
• Two common IGP are RIP and OSPF, the only EGP is BGP
• Autonomous System
  • Stub AS(끝단, single AS connection, customer network),
  • Multihomed AS(다른 AS와 하나 이상의 multi-connection, customer network),
  • and Transient AS(Provider, Backbone)

 

Unicast Routing Protocols

routing protocol: router들이 초기에 갖고 있는 initial 값을 가지고 결국은 router protocol을 통해 내 router에 원래는 없었던 forwarding table의 내용이 점점 만들어 지는 과정이다.

distance vector와 link state의 동작원리를 기반으로(예제를 풀면서)

 

Routing Information Protocol (RIP)

• One of the most widely used intradomain protocols based on the distance-vector routing algorithm
• Hop count
  • 모든 network을 들어가는 cost를 1로 본다. (그래서 거치는 숫자만 센다.)
  • network를 덜 통과하는(통과하는 갯수가 제일 적은) 것이 best route이다.

• Forwarding tables
• RIP implementation by RIP messages

• packet이 오면 forwarding table을 보고 forwarding 될 router와 cost를 알 수 있다.
• tag: AS id
• RIP Message 형태로 다음 router로 보냄.

 

RIP Algorithm

distance vector와는 다른 점은 RIP는 cost가 전부 1이라는 것

• A router needs to send the whole contents of its forwarding table in a response message
• The receiver adds one hop to each cost and changes the next router field to the address of the sending router. The received router selects the old routes as the new ones except the three cases:
  • The received route does not exit in the old forwarding table; it should be added to the route
  • If the cost of received route is lower than the cost of the old one, the received route should be selected as the new one
  • If the cost of received route is higher than the cost of the old one, the value of the next router is the same in both routes, the received route should be selected as the new ones
    • 같은 경로도 값이 바뀌면 그걸로 update 해 주어야 함
• The new forwarding table needs to be sorted according to the destination route.

 

Example Using RIP (1)

초기에는 직접적으로 어디와 연결 되어 있는지의 정보만 담고 있음

 

Example Using RIP (2)

Example Using RIP (3)

Open Shortest Path First Protocol (OSPF)

• One of the most widely used intradomain protocols based on the link-state routing algorithm
• An open protocol, which means that the specification is a public document.
• Metric: each link can be assigned a weight based on throughput, round-trip time, reliability, and so on.

Forwarding tables in OSPF

• To create a forwarding table after finding the shortest-path tree between itself and destination using Dijkstra’s algorithm

Areas in an AS

• OSPF can handle routing in a small or large AS (RIP is normally used in small AS)
• OSPF: all routers flood the whole AS with their LSPs to create the global LSDB
• Need to be divided into small sections called areas

Link-State Advertisement

• Five types of link-state advertisements

a. transient(시작), stub(끝단)

b. 네트워크 자체가 정보를 줄 순 없기 때문에 designated router를 지정하여 해당 router에서 정리하여 보낸다.

c. summary해서 backbone에게 보냄

d. Area0에서 다른 AS로 보낼 때

e. single network이 바깥쪽에 존재할 때 그곳으로 보냄

 

OSPF Messages

• Message Header Format
  • OSPF Common Header (all message)
  • Link State General Header (some message)
• Message Types
  • Hello message (Type 1) : introduce itself to neighbors
  • Database description message (Type 2) : respond to hello message
  • Link state request message (Type 3) - 요청
  • Link state update message (Type 4) : main message for building LSDB
  • Link state acknowledgment message (Type 5)
• Performance
  • Update Message – heavy traffic
  • Convergence of forwarding tables – time for Dijkstra’s algorithm
    • cost가 바뀌면 다시 알고리즘을 돌려 테이블이 업데이트됨
  • Robustness – than RIP
    • 안전성이 있음 (synchronous)

 

OSPF Implementation: Message (1)

중요x

 

OSPF Implementation: Message (2)

 

 

Border Gateway Protocol (BGP)

• The Border Gateway Protocol version 4 (BGP4) is the only interdomain routing protocol used in the Internet today.
• Based on the path-vector algorithm, but it is tailored to provide information about the reachability of networks in the Internet.

External BGP (eBGP)

• The border router(AS와 AS를 이어주는 관문(gateway) router) will be running three protocols (intradomain, eBGP, iBGP);
  • Other routers (intradomain, iBGP)
  • 경계에 있는 router는 3개의 protocol이 있어야 함.

1. border router를 통해 다른 AS의 router에게 우리는 어떤 Area 이고 Next router는 어떤 것이며 연결되어 있는 network은 무엇인지에 대한 정보를 주고 받는다.

 

Internal BGP (iBGP)

• Combination of eBGP and iBGP sessions in our internet

• 즉, iBGP는 eBGP를 통해서 border router가 접속된 다른 AS에 관한 정보를 모은 거를 내부 router들에게 알리는 것.
• AS2, AS3, AS4는 끝단에 있기 때문에 stub AS
• AS1은 transient AS 역할

 

Finalized BGP Path Tables (1)

Finalized BGP Path Tables (2)

Finalized BGP Path Tables (3)

Forwarding Table After Injection (1)

• 흰색 부분: RIP
• Shading(회색) 부분: BGP

만들어진 forwarding table + BGP -> Injection

 

Forwarding Table After Injection (2)

• 단순해짐
  • R5를 예로 들어 보면 N8과 N9를 제외한 나머지 모두는 R1을 통해 외부로 나갈 것이기 때문에 이에 대한 정보는 굳이 다 명시할 필요가 없음

 

이 아래는 중요하지 않음(학부 과정에서는)

BGP의 동작 원리(intradomain + interdomain)

---

Path Attributes

• ORIGIN (type 1), AS-PATH (type 2), NEXT-HOP (type 3),
• MULTI-EXIT-DISC (type 4), LOCAL-PREF (type 5)
• ATPMIC-AGGREGATE (type 6), AGGREGATOR (type 7)

 

Flow Diagram for Route Selection

BGP Message