CHAP 5. The Network Layer: Part 1

강의내용 - Stalling책

• Chap 10. WAN 기술과 프로토콜 (패킷교환)

• Chap 19. 라우팅 (경로배정)

• 강의 내용

- Network Layer의 개념.

⇒ Network 전체를 관리하여 "Host-to-Host" data comm.을 제공.

- 기능

① Routing

② Congestion Control (혼잡제어)

③ Internetworking: IP

(Stallings 10th ed.) p.611/p.653/p.441

• Network layer (Internet layer in TCP/IP)

Topics

• Computer Network

S

S

R

R

R

R

R

R

S

S

S

S

KNUE

충북대

KORNet

& BoraNet

leased line

NSFNet

U. C. at

Berkeley

U. C. at

L. A.

210.93.99.64

Network Layer

- host-host comm.

① Routing

② Congestion Control

③ Internetworking

211.34.193.6

*KNUE: KORNet(KT)/BoraNet(LG U+)에 각각 연결

• Purpose: Getting packets from the source host "all the way to" the dest. host.

(즉, Network 전체를 관리하여 "Host-to-Host" comm.을 제공)

Network

Layer

TCP

UDP

H/W

interface

IP

process

host

H/W

interface

H/W

interface

IP

gateway/router

H/W

interface

H/W

interface

IP

gateway/router

TCP

UDP

H/W

interface

IP

process

host

WAN

Ethernet

Ethernet

• Functions

① Routing: "Delivering" packets from source to dest.

② Congestion Control: Preventing from "overloading" some nodes in the network.

③ Internetworking: A packet may go across several "different" subnets with "different connection types" to reach its dest.

⇒ 패킷들은 서로 다른 구조의 네트워크들을 거쳐가야 함

LAN: IEEE 802.3, 802.4, 802.5, ATM

WAN: Frame Relay, ATM

Packet Switching Technique

• History

- Developed for long-distance digital "data" comm. in the early 70's.

⇒ Computer network(ARPANet)에서 digital data의 전달 방식.

⇒ 패킷들이 어떻게 목적지에 도달하는가?

• Two methods: application을 위한 ‘전송/수송(transport) 계층’의 service

① Virtual circuit: ‘Connection-oriented’ service

② Datagram: ‘Connectionless’ service

⇒ process 간의 데이터 전송/수송

(Stallings 10th ed.) p.294 Fig.9.11, p.295 Fig.9.12

(Stallings 7th ed.) p.380 Fig. 10.12, p.381 Fig. 10.13

1. Virtual Circuit

- A 'preplaned' route is established before any packets are sent by sending a "special control" packet, a Call Request Packet.

⇒ A routing decision is made only "once".

- Once the 'logical' connection (virtual circuit) is set up, all packets follow that route.

⇒ All packets for that virtual circuit follow the same route and arrive "in sequence"

⇒ TCP (Transmission Control Protocol)

- Characteristics

□Appropriate for "long" duration of transmission.

⇒ routing이 시작할 때 한 번만 설정됨

□Packets arrive in the "original" order.

2. Datagram

- Each packet is routed "independently".

- The packets, each with the same dest. addr., may NOT follow the same route.

⇒ UDP (User Datagram Protocol)

- Characteristics

□For "only one" or "a few" packets.

⇒ 각 패킷이 독립적으로 각각 routing됨

□If congestion develops in one part of the network, incoming datagrams can be routed "away" from the congestion.

⇒ "adaptive"

• Comparison of VC and Datagram:

- transport layer 서비스를 위해 하위계층인 network layer에서 패킷들을 전달하는 ‘routing’이 필요

(Stallings 10th ed.) p.300 Tab. 9.1	(Stallings 7th ed.) p.386 Tab. 10.2

Routing

• Mail System: 각 우체국에서 목적지 주소를 보고 “다음 해당” 우체국으로 넘김.

서울 중앙

신사동

신촌

압구정

대전 중앙

청주 중앙

교원대

가경동

건물

건물

우체통

우체통

우체통

To: 서울시 서대문구

신촌 33-5

서울시 서대문구

신촌 33-5

목적지만 표시

• Computer Network: Router에서 dest. addr.를 보고 “다음 해당” Router로 넘김.

⇒ Router에 있는 ‘routing table’을 참조

e.g., bridge의 routing table

S

S

R

R

R

R

R

R

SS

S

S

S

KNUE

충북대

KREN

(서울대)

NSFNet

U. C. at

Berkeley

U. C. at

L. A.

210.93.99.64

211.34.193.6

• Design Criteria: How to make a routing table for each gateway/router?

- Correctness(정확성): 올바른 dest.으로 배달되어야 함

- Simplicity(단순성)

- Robustness(견고성): It must cope with expected/unexpected "changes" in the network due to "expansion" or "failures" (node/link).

- Stability(안정성): Network does NOT crach (deadlock) when "overloaded".

- Fairness(공정성) vs. Optimality(최적성): Often are "conflicting goals"

(ex) A heavy traffic has to "yield" to a light traffic to provide "fair" access to both sides at the cost of throughput loss.

(Stallings 10th ed.) p.611-612

(Stallings 7th ed.) p.439, p.440 Tab. 12.1, p.441 Fig. 12.2

• Routing Methods

- Routing table 갱신 주기에 의한 분류

□static routing: Routing table 정보가 일정 기간동안 ‘고정적’.

□dynamic routing: Routing table 정보가 네트워크 상태에 따라 ‘가변적’.

- Routing table 형태에 의한 분류

□single path routing: Routing path가 하나 - 'shortest path' routing.

□multipath routing: Routing path가 여러 개.

- Routing table 작성 장소에 의한 분류

□centralized routing: Routing table을 하나의 노드에서 작성.

□isolated routing: NO Routing table - 각 노드의 ‘현재 상태’만을 사용.

□distributed routing: Routing table을 각 노드에서 각자 작성.

(Stallings 10th ed.) p.613 Tab.19.1

• Routing table 갱신주기에 의한 분류

1. Static routing: Routing decisions are based on "off-line" and 'in advance' calculated network info.

⇒ 한 번 routing을 결정하면 다음 번 갱신 때까지 계속 사용. (주기적 갱신)

⇒ "Non-adaptive"

2. Dynamic routing: Routing decisions are based on the "current" network state  (traffic and topology).

⇒ Network 상황을 ‘계속’ 탐지하여 현재의 상황에 맞게 routing함.

⇒ "Adaptive"

• Routing table 형태에 의한 분류

1. Shortest Path routing

- Idea

□A "graph" approach: Routers are denoted as 'nodes', and the path bet. two nodes is denoted as an 'arc'.

□The arc bet. two adjacent nodes i, j is labeled with the 'distance' bet. them,	ℓij.

⇒ A function of the geographical distance, bandwidth, avg. traffic, comm. cost, mean queue length, measured delay, and other factors.

□Find "ALL" shortest path starting from the source.

⇒ 한 개의 주어진 소스노드로부터 다른 모든 노드들까지의 ‘최소비용 경로’를 구함.

⇒ Dijksra's (min. spanning tree) algorithm/Bellman-Ford algorithm

- Dijksra's algorithm: Breadth-first search technique - ‘전진탐색’ algorithm

⇒ Needs a table with N and D(v)'s.

① Initialization: N={S}, D(v)=Csv (Csv=∞, if s and v are NOT adjacent.)

N: The set of nodes that a shortest path bet. the source and the nodes has been "found" at current step.

D(v): The "current distance" bet. the source and a node v.

Csv: Cost bet. the source and a node v.

② Loop until 'every' node is in N.

②-1 Find the node w NOT in N, where D(w) is 'min'.

Add w to N. (Tie is broken 'randomly'.)

②-2 Update D(v)'s: D(v)=min{D(v), D(w)+ℓ(w,v)}

source에서 w를 거쳐서

v로 가는 cost

원래 source에서

v로 가는 cost

(ex)

1

2

4

3

5

6

source

2

2

1

5

3

3

1

1

5

2

w

w

w

w

N	D(2)	D(3)	D(4)	D(5)	D(6)
{1}	2	5	1	∞	∞
{1,4}	min(2, 1+2) = 2	min(5, 1+3) = 4	1→4	min(∞, 1+1) = 2	∞
{1,4,5}	min(2, 2+∞) = 2	min(4, 2+1) = 3		1→4→5	min(∞, 2+2) = 4
{1,4,5,2}	1→2	min(3, 2+3) = 3			min(4, 2+∞) = 4
{1,4,5,2,3}		1→4→5→3			min(4, 3+5) = 4
{1,4,5,2,3,6}					1→4→5→6

Find "all" shortest path starting from the source.

1

2

4

3

5

6

source

2

1

1

1

2

Dest.	Next hop
2 3 4 5 6	2 4 4 4 4

⇒ Routing table in node 1

1

2

4

3

5

6

source

2

2

1

3

2

source = 2의 경우

(ex) (Stallings 10th ed.) p.613 Fig.19.1, p.641 Fig.19.14

(Stallings 7th ed.) p.458, Tab.12.1, p.459 Fig.12.10

2. Multipath routing

- Idea

□Based on the observation that a network performs better when "splitting" the traffic over "several" paths.

- Method

□A node has several "possible" paths for same dest.'s.

□Each possible path is assigned a different "weight", and the first choice has the "heaviest" weight.

□Each time when a packet arrives at a node, its next hop is chosen "randomly" based on the weights of the different paths.

(ex) J receives a packet whose dest. is A.

⇒ J generates a random no. bet. 0.00 ～ 0.99

① If no.<0.63, deliver a packet to K.

② If 0.63≤no.<0.84, deliver a packet to I.

③ If no.≥0.84, deliver a packet to H.

J

A

I

H

K

- Adv.

□Different "classes" of packets can be sent along different paths.

(ex) short packets → lower bandwidth link

long file transfer → higher bandwidth link

□Reliability: Network failure시 다른 path를 이용.

• Routing table 작성 장소에 의한 분류

⇒ How the routing tables are made for each router?

① Centralized routing: RCC(Routing Control Center)가 전체 network info.을 수집하여 routing table을 작성한 다음, network의 각 node로 table을 전송함.

② Isolated routing: 각 node가 자신이 가진 info.만을 사용하여 routing을 수행.

③ Distributed routing: 각 node가 전체의 network info.를 ‘각자’ 수집하여, 자신의 routing table을 작성.

1. Centralized routing

- Idea: Build the routing tables in a central location called RCC (Routing Control Center)

- Method

① The RCC collects traffic status info. (e.g. amount of traffic, queue length etc.) from routers "periodically".

② The RCC calculate an optimal route from every router to every other router (for example, using the 'shortest path' algorithm).

③ The RCC distribute them to all the router.

RCC

(Stallings 10th ed.) p.616 Fig.19.2	(Stallings 7th ed.) p.444 Fig.12.3

- Adv.

□Use "complete" info.

⇒ Can make "optimal" decisions.

□Relieves the routers of the burden of the routing computation.

- Disadv.

□Global but possibly "aged" status info. is available.

⇒ Can NOT "adapt" to traffic changes. (즉,	network 상황이 변했더라도, RCC가 routing table을 갱신할 때까지는 기존의 table을 계속 써야 함)

⇒ Need to run "frequently" to get up-to-date routing decisions.

□Routing tables are NOT updated at the "same" time.

⇒ The routers that are close to the RCC will get their new tables first and will switch over to the new routes "before" the distance routers have received their tables.

⇒ "Inconsistency" can occur.

2. Isolated routing

- Idea: Each router makes routing decisions totally based on "its own" info. trying to "adapt" to changes in topology and (local) traffic.

⇒ RCC에 의존하지 않고, 자신이 갖고있는 network info.만을 사용하여 network 상황에 적응함.

① Flooding

□Method: "Every incoming" packet is sent out on "every outgoing" link except the one it arrived on.

□Problem: The network can be "overwhelmed" by packets.

⇒ Solution

① Aging:

A packet carries a "counter" with an initial value of k. (홉계수)

The counter is "decreased" by one when it is received by an router.

The packet is discarded when the counter reaches 0.

(Stallings 10th ed.) p.618 Fig.19.3	(Stallings 7th ed.) p.446 Fig.12.4

② Selective Flooding:

A packet is relayed to "only a few" selected links.

□Usage: Seems "unpractical"

∙ Military application: Where large no. of routers may be "blown" at any instant.

⇒ 소스와 목적지 간의 ‘모든 가능한’ 경로를 시도한다. 그러므로, 어떤 노드나 링크의 고장이 났더라도, ‘적어도 하나의’ 경로라도 존재하는 한 패킷은 전송된다.

⇒ 모든 link로 packet을 보내므로, ‘연결되었다면’ path를 찾을 수 있다.

∙ Distributed DB applications: Update ALL the DBs "concurrently".

⇒ 소스 노드에 직접, 혹은 간접적으로 연결된 ‘모든’ 노드들에 패킷을 전달한다.

∙ A "metric" against other routing algorithms.

⇒ 모든 경로가 시도되므로, 목적지에 ‘처음’ 도착한 패킷의 복사판은 적어도 ‘최소’ 수의 hop 경로를 사용할 것이다.

⇒ Always choose the "shortest" path, but with "overhead".

② Hot Potato algorithm

□The router tries to route each packet "as soon as possible".

⇒ When a packet arrives, it is put into the "shortest" output queue.

To K

To H

To A

To I

?

(c.f.) 무작위(random) 라우팅	(Stallings 10th ed.) p.619

3. Distributed routing: Distance Vector routing (거리 벡터 라우팅)

- History

□Used in the ARPANet until 1979 under the name RIP(Routing Info. Protocol)

□Early versions of DECNet, Novell's IPX, AppleTalk, Cisco routers.

- Idea: Each router periodically "exchanges" explicit routing info. with each of its "neighbors".

- Method

① Each router has a routing table containing one entry for each other router ("dest.") with the preferred outgoing link ("neighbor") and estimated "cost" (hops, delay, mean queue length, etc.) to that dest. router.

Destination	Neighbor	Cost

② Routeri periodically probes the network to "sample" the cost Cij to routerj.

(i≠j)

⇒ A table consists of Cij's is sent to 'every other' router.

③ When routeri receives the tables from its "neighbor" routerk, routerl, routerm,

⇒ it calculates its 'best' route to an "dest.", say routerx

⇒ Min{(routeri → routerk → … →routerx), (routeri → routerl → … →routerx), (routeri → routerm → … →routerx)}

⇒ The old routing table is NOT used in the calculation.

④ Entry x in routeri's routing table is "replaced" with the link which has the current estimated "lowest" cost.

(Stallings 10th ed.) p.623 Fig.19.5, Fig.19.6

(Stallings 7th ed.) p.451 Fig.12.7, p.451 Fig.12.6

Internet Routing Protocol

• Packet switching network (ARPANET) 개발 당시 회의론자들은 '네트워크'를 무한하게 순환(cycle)하는 packet이 생길 것이라는 우려를 제기.

- Sink 'tree': The set of ‘optimal’ routes from ALL sources to a given dest. form a "tree" rooted at the dest.

⇒ No "cycles"

⇒ Each packet will be delivered within a "finite" and "bounded" no. of hops.

• Sink tree is NOT necessarily "unique".

⇒ Other trees with the same path length MAY exist.

⇒ The goal of all routing algorithms is to discover and use the "sink trees" for ALL routers.

• Optimality Principle

- IF router J is on the optimal path from router I to router K, THEN the optimal path from J to K also falls along the 'same' route.

(Pf)

I

J

K

r1

r2

r3

(가정) Assume that r1․r2 is optimal.

(모순법) 만약 r3가 r2보다 더 좋은 (cost가 낮은) path라면,

r1․r3는 r1․r2보다 더 좋은 path가 된다.

⇒ r1․r2가 optimal path라는 가정이 모순.

∴만약 I-J-K가 optimal이면 I-J와 J-K도 optimal이다.

- Why NO cycles exist?

Assume that r1․r2 is optimal.

Cycle Case #1:

r1

r2

Source

Sink

(destination)

r1

r2

⇒	r1․r2가 source에서 sink까지 optimal이므로 또 “다른” optimal route가 존재할 수 없음. (같은 length이면 하나만 선택)

Cycle Case #2:

r1

r2

Source

Sink

(destination)

r1

r2

⇒	optimal principle에 의하여 r1이외에 다른 route는 존재할 수 없음.

• 링크 상태(Link State) Routing

- APARNET의 Routing Protocol

① RIP(Routing Information Protocol): "old" routing protocol

② OSPF(Open Shortest Path First): "new" routing protocol

⇒ 링크 상태 알고리듬 사용.

(Stallings 10th ed.) p.629

- 현재 TCP/IP network에서 '내부' router protocol로 가장 널리 사용되고 있음.

(Stallings 10th ed.) p.628 Fig.19.9

(Stallings 7th ed.) p.743 Fig.19.5

- Each router must

① Discover its "neighbors" and learn their network addr.'s.

② Measure the "delay (or cost)" to each of its neighbors.

③ Construct a packet telling "all" info. it has just learned.

④ Send this packet to "all other" routers.

⑤ Compute the Shortest Path "to every other" router.

⇒ ‘Sink Tree’ from every other router

(Stallings 10th ed.) p.637 Fig.19.11, p.638 Fig.19.12, Fig.19.13

(Stallings 7th ed.) p.754 Fig.19.7, p.755 Fig.19.8, p.673 Fig.19.9

- A network and subnetworks

① 비용계산: Router의 출력쪽과 관계가 있음.

② R6를 root로하는 sink tree 계산: e.g. Dijkstra Algorithm 이용.

③ R6의 routing table