[데이터 통신] 8. Switching

physical layer의 switching에 대해서 자세히 다루고 data-link나 network layer 에서도 switching이 존재하긴 하지만 조금만 다룰 것이다.

8.1 Switching

mesh topology와 같이 dedicated link가 있는 경우 굳이 switching이 없어도 된다. 그러나 넓은 망의 네트워크를 구축하는 경우 mesh로 구축하기는 굉장히 힘들 것이다.(impractical and wasteful)

• Switches are devices capable of creating temporary connections between two or more devices linked to the switch by switches(통신이 필요할 때마다 임시적인 연결을 만들어 줌)

Taxonomy of Switched Networks

• message switching은 packet switching의 일환으로 보기 때문에 generally switching에는 circuit switching과 packet switching이 있다고 본다.
  • message switching은 보통 application layer에서 사용된다.
• circuit switching: physical layer
• packet switching: data-link layer, network layer

physical layer: circuit switching(no packet exchanged)

data-link layer: packet switching - virtual circuit approach

network layer: packet switching - datagram approach

 

8.2 Circuit-switched Network

• A circuit-switched network consists of a set of switches connected by physical links, in which each link is divided into n channels
• In circuit switching, the resources need to be reserved during the setup phase;
  • the resources remain dedicated for the entire duration of data transfer until the teardown phase.
  • resources가 remain dedicated 라는 것이 핵심 keyword
• A에서 M 사이의 physical path가 필요에 의해 임시적으로 만들어졌다가 사라진다.

Example 8.1: Circuit-Switched Network

• 8 대의 telephone이 연결된 상태
• 4kHz voice channels
• each link uses FDM
• 1번이 7번과 연결,2번이 5번과 연결
• data(목소리)를 주고 받기 전에 setup을 통해서 circuit을 형성하고 다 끝나고 나서는 teardown을 통해서 끊어버리는 방식.

 

Example 8.2: Circuit-Switched Network

• TDM
• four output ports are folded into the input ports to allow communication between computers in the same office.
• Four other output ports allow communication between the two offices. Figure 8.5 shows the situation.

 

Circuit Switching

In physical layer, 전화망

• Three phases
  • Setup phase, Data transfer phase, Teardown phase

Delay in a circuit-switched network

• low efficiency
• data transfer 동안에는 data가 각 switch에서 delay 되지 않는다.
  • resources are allocated for the duration of the connection
  • 연결된 기간 동안에는 resource가 할당되어 있기 때문에
• propagation delay, transmission delay 말고는 데이터가 쭉 전달된다. (setup time동안 미리 만들어진 path를 통해서)

• no waiting time at each switch
• create connection + transfer data + disconnect the circuit
  • the delay caused by the setup
    • propagation time of the source computer request(slope of the first yellow box)
    • the request signal transfer time(height of the first yellow box)
    • propagation time of the acknowledgement from the destination computer(slope of the second yellow bow)
    • signal transfer time of the acknowledgement(height of the second yellox box)
  • the delay caused by the data transfer
    • propagation time (slope of the blue colored box)
    • data transfer time (height of the blue colored box)

이미 circuit setup이 되었기 때문에 전달이 될 때는 마치 pipeline을 통과하는 것과 같이 물 흐르듯 전달되지만 setup time이 길다.

 

8.3 Packet Switching

circuit switch 방식은 사용하고 있지 않은 상태에서도 계속해서 자원이 사용되고 있는 상태이다.

• 전화할 때 수화기를 들면 말을 하지 않더라도 계속 이어지는 것처럼

 

• In a packet-switched network, there is no resource reservation; resources are allocated on demand.

 

• In a datagram network, each packet is treated independently of all others. Sometimes referred to as connectionless networks.
  • 마치 packet이 여러개 여도 혼자 존재하는 것처럼 한다.
  • 이 때의 packet을 datagram이라고 한다.

• network layer
• conectionless network라고 불리기도 함(information을 계속해서 유지하지 않기 때문에)

1번이 저렇게 돌아가는 것처럼 보이는 이유는 모종의 이유로 저 경로가 제일 빨랐기 때문이다.

그래서 반드시 모든 packet의 경로가 같지 않아도 되고 반대로 같아도 상관이 없는 것이다. 각자가 다 빠른 길을 목적지를 보고 독립적으로 정하여 가는 것.

그때 그때 마다 빠른 길로

Routing Table

• A switch in a datagram networks uses a routing table that is based on the destination address.
• The destination address in the header of a packet in a datagram network remains the same during the entire journey of the packet.
  • datagram network에서, packet의 head에 있는 the destination address는 목적지에 도달할 때까지 그 전달 여정 중에 절대로 바뀌지 않는다.
• routing table은 주기적으로 이벤트가 발생할 때마다 스스로 update된다.(by routing protocol)
  • routing table은 고정된 값이 아니다,
  • 상황(traffic)에 따라서 그 당시 가장 좋은 길(link address)로 설정
    • 도로와 같이 상황에 따라 더 빠른 길이 달라질 수 있는 것이다.

In a datagram network, the destination address remains the same from the source to the destination

In a datagram network, the data link layer address changes

 

Delay in a Datagram Network

Ex) In Internet

• Datagram network may have greater delay than a virtual-circuit network even though no setup and teardown phase
  • virtual circuit = circuit switching
  • datagram network는 circuit switch network와 다르게 setup과 teardown phase가 없는 대신에 더 많은 delay를 갖는다.
• Delay is not uniform
• Total delay = 3T + 3τ + w₁ + w₂ (ignoring the processing)
• ​ = transmission time + propagation delay(보내는 delay) + two waiting times

waiting time = packet header에 있는 destination address를 보고 목적지를 routing table에서 찾아서 전송하는데 걸리는 시간

• 장점
  • setup과 teardown 시간이 필요없기 때문에 그 시간을 절약할 수 있지만
• 단점
  • 패킷을 전달하는 과정에서 not uniformed delay(매번 경로가 다르기 때문에)

 

Virtual-Circuit Networks

• Setup, data transfer, and teardown phases as in a circuit-switched network (CSN)
• Resource allocated during setup phase, as in a CSN,
• or on demand as in a datagram network (DN)
  • CSN에서는 전화를 예로 들어서, circuit이 한 번 연결되면 말 한마디 안 해도 그 circuit은 teardown 되기 전까지 계속 연결되어 있다. 즉, resource가 완전히 장악된 것임.
  • DN은 그때 그때 필요할 때마다 사용한다.
• As in DN, data are packetized and each packet carries an address in the header. The address has local jurisdiction, not end-to-end jurisdiction(관할권).
  • jurisdiction: what the next switch should be and the channel on which the packet is being carried.
  • end-to-end: 우리가 일반적으로 사용하는 전화 번호(02-940-5134)
  • local : 회사내 전화 번호(예. 5123로만 걸면 local에서 그 번호를 가진 부서로 전화 연결이 됨)
• As in CSN, all packets follow the same path established during the connection.
  • VCN도 CSN처럼 same path를 따라가지만, resource 사용 측면에서는 다른 것이다.
• VCN is normally implemented in the data link layer, while CSN is in physical layer and DN in the network layer.
  • VCN network에서도 쓰긴 씀.

 

CSN:

• 동창들 20명끼리 등산을 간다. 한 사람이 선발대로 circuit을 형성하기 위해 먼저 좋은 길로 가면서 그 길에 깃대를 꽂는다. 그러고서 정상을 찍고 다시 돌아온다. 그러면 circuit이 하나 만들어진 것이다. 그럼 나머지 19명은 그 길(circuit)을 따라 순서대로 정상까지 올라간다. 하지만 그 사람들을 제외한 일반 사람 즉, 어떠한 등산객들도 그 길로 갈 수가 없다. (완전히 resource를 장악한 것이기 때문에)

VCN:

• 20명이 갈 길에 대한 virtual circuit을 설정한다. 그러면 20명이 전부 다 똑같은 길로 올라가게 된다. 그러나 그 길에 깃발을 꼽아놓은 것일뿐 다른 사람들이 그 길을 가지 못하는 것은 아니다. 그 길을 가는 가상적인 circuit을 하나 설정해 놓고 모두가 그 길을 따라 같은 길로 가고 한 번 설정된 길은 깃발을 뽑아 teardown 할 때까지 그 길로만 가야한다. (On - demand)

DN:

• 첫 번째 사람이 올라가고 두 번째 사람이 따라서 올라가는데 뒤에 따라가는 사람이 굳이 그 길로 가지 않고 다른 더 좋은 길로 갈 수 있는 방식이다. (서로서로가 independent 하게)

 

• A가 B랑 주고 받을 정보가 있다면 가장 먼저 가상적인 circuit을 설정하고 virtual circuit을 setup한다. 그 이후부터는 Datagram처럼 그 길을 따라 계속해서 전달을 한다. 이 길은 끝날 때(teardown)까지 고정되며, 더 좋은 길이 있다 하더라도 반드시 이 길로만 가야한다.
• 쉽게 말해서 A에서 B로 가는 길을 각 switch에서 기억해 놨다가 그 길로 가는 data에 대해서는 switch가 기억에 따라서 동작하는 것이다.
• 하지만 CSN처럼 A와 B 사이에 dedicated link가 physical하게 생겨서 두 개만 전용으로 이동할 수 있는 것은 아니다.
• 맨 처음에 A와 B사이에 virtual circuit을 형성하기 위해선 A의 full 주소(global)와 B의 주소가 있어야 한다.
  • 이 때 이 주소를 따라서 가지만 switch에서는 몇 번에서 몇 번으로 가고를 number로 저장을 하는데 global한 주소가 있을 수도, local 주소가 있을 수도 있다.
• 초기에 setup 단계에서 거친 switch에서 지나간 데이터가 기억이 되어(flag) circuit이 형성되는 것이다.

In virtual-circuit switching, all packets belonging to the same source and destination travel the same path,

but the packets may arrive at the destination with different delays if resource allocation is on demand.

 

Addressing

• Two types of addressing in a virtual-circuit network: global and local(virtual-circuit identifier)
• Global address is used only to create a VCI
  • 처음에 circuit을 형성할 때만 필요함
  • global address is used only to create a virtual-circuit identifier
• Virtual Circuit Identifier (VCI), or label
  • 즉, local address
  • circuit이 형성된 이후부터 device간 연결을 위해 계속해서 사용하는 number.
  • frame이 출발하면 VCI를 갖는다.

즉, 처음에 A와 B 사이의 connection을 맺을 때는 A,B의 full 주소 즉, Global address(large number)가 필요하여 각 switch에서는 number가 부여되는데, setup이 된 다음에는 보내고 싶은 data의 VCI, label(number) 값만 가지고 switching이 일어난다.

편지배달망

부산에 있는 친구에게 100통을 전달한다고 하자.

• DN의 경우 편지 봉투에 적혀있는 목적지만 보고 충실하게 그때 그때 가장 좋은 길로 그 목적지로 편지를 계속 보내는 것이다. 그 때 마다의 길을 따로 기록 하진 않는다.
• VCN의 경우 편지를 보내면 편지를 받자마자 광운우체국부터 시작하여 혜화우체국, 부산 우체국을 통해 전달되는데 이 때 한 번 경로를 설정하는 단계를 setup이라고 하며 이 이후부터는 각 우체국을 거치면서 받은 local 번호인 (VCI)를 받아 이 번호를 통해 그 다음 편지부터는 이 번호를 통해서만 전달이 되게 된다.
  • 즉 처음에는 완전한 full주소가 필요했는데 그 이후부터는 우체국 번호로만 전달이 가능해 진 것

 

Three Phases

• Data transfer phase, setup phase, teardown phase
  • setup phase를 통해 VCI 정보가 담긴 table이 만들어진다.
• Switch and tables in a virtual-circuit network

Data Transfer Phases

• Source-to-destination data transfer in a virtual-circuit network

• 처음에는 source와 destination의 full 주소를 통해 frame을 보냄으로써 circuit을 형성하고 그 이후부터는 local한 주소만을 이용하여 빠르게 보낼 수 있다.
• 이로써 매번 받는 사람과 보내는 사람의 완전한 주소를 쓰지 않아도 되는 것이다.
• 몇 번 포트의 몇 번 value를 몇 번 포트로 보낼 것인지를 기록하여 빠른 속도의 connection을 이룩한다.
• 각각의 data를 나타내는 번호가 VCI이고 이와 연결된 link에 붙여진 number가 Port이다.

 

Setup Phases: Setup Request

• setup phase에서 처음에는 아무것도 적힌 것이 없다.
• A에서 B로 편지를 보내기 전에 setup request packet(setup을 요청하는)을 보낸다.
  • 이 packet에는 주는 사람의 full 주소와 받는 사람의 full 주소가 모두 적혀 있으며, incoming 되는 것들에 대해선 VCI와 같은 number가 주어진다.

여기서 VCI는 switch 내에서만 사용하는 local한 number이다.

 

Setup Phases: Acknowledgement(응답)

Delay in a Virtual-Circuit Network

• In virtual-circuit switching, all packets belonging to the same source and destination travel the same path; but the packets may arrive at the destination with different delays if resource allocation is on demand.
• Total delay = 3T + 3τ + setup delay + teardown delay

waiting time은 ignorable

그래도 여전히 VCN은 setup delay와 teardown delay가 존재하기 때문에 뭐가 더 좋다라고 말할 순 없다.

 

8.4 Structure of Circuit Switches

• Space-division switch or time-division switch
• Space-division: crossbar switch, multistage switch
  • 서로 간에 connection 사이를 공간적으로 분리 시키는 방법

input이 3개고 output이 4개면 total 12개의 cross point 필요

 

Crossbar Switches: Problem

• The number of switches is huge.
  • 요구되는 cross point 갯수 역시 크다.(impractical)
  • connect n inputs by m output → require n x m crosspoint.
  • Ex : 1000 input, 1000 output → 1,000,000 crosspoint

• Inefficient; 비효율적임
  • fewer than 25% of the crosspoints are in use at a given time.
  • 주어진 시간에 25%보다 더 적은 crosspoint들이 사용되기 때문

 

Multi-stage Switch(100% 시험)

crossbar switch의 복잡성과 비효율성 때문에 일반적으로 crossbar switch들은 multistage로 구성된다.

• Solution to the limitation of the crossbar switch, which combines crossbar switches in several stages(three)
•  

Design of a Three-Stage Switch

• Three steps
  • Divide the N input lines into groups, each of n lines. For each group, use one crossbar of size n x k, where k is the number of crossbars in the middle stage
  • Use k crossbars, each of size (N/n) x (N/n) in the middle stage
  • Use N/n crossbars, each of size k x n at the third stage
• N/n(n x k) + k(N/n x N/n) + N/n(k x n) = 2kN + k(N/n)²
• In a three-stage switch, the total number of crosspoints is 2kN + k(N/n)² which is much smaller than the number of crosspoints in a single-stage switch (N²).

Example 8.3: Multistage Switch

• Design a three-stage, 200 × 200 switch (N = 200) with k = 4 and n = 20.

Solution

• In the first stage we have N/n or 10 crossbars, each of size 20 × 4. In the second stage, we have 4 crossbars, each of size 10 × 10. In the third stage, we have 10 crossbars, each of size 4 × 20. The total number of crosspoints is 2kN + k(N/n)², or 2000 crosspoints. This is 5 percent of the number of crosspoints in a single-stage switch (200 × 200 = 40,000).

 

Multistage Swtiches: Blocking(시험)

• multistage 의 전반적인 idea는 middle stage crossbar에서 crosspoints를 공유하는 것인데 이는 동시에 모든 사용자가 연결을 원할 시에는 a lack of availability 문제가 발생할 수 있다.
• Advantage:
  • The number of crosspoints를 대폭 줄일 수 있다.
• Disadvantage:
  • blocking
    • switch를 줄이다 보면 내가 쓰는 switch와 상대방이 쓰는 switch가 서로 충돌을 해서 동시에는 못나가는 blocking이 된다. output이 중복되어지는 것
• Clos criterion: condition of nonblocking
  • n = (N/2)^1/2 and k ≥ 2n – 1
  • Total number of crosspoints ≥ 4N [(2N)^1/2 – 1]

 

Example 8.4: Multistage Switch(중요)

• Redesign the previous three-stage, 200 × 200 switch, using the Clos criteria with a minimum number of crosspoints.

• We let n = (200/2)^1/2, or n = 10. We calculate k = 2n − 1 = 19.
  In the first stage, we have 200/10, or 20, crossbars, each with 10 × 19 crosspoints.
  In the second stage, we have 19 crossbars, each with 20 × 20 crosspoints.
  In the third stage, we have 20 crossbars each with 19 × 10crosspoints.
  The total number of crosspoints is 20(10 × 19) + 19(20 × 20) + 20(19 ×10) = 15,200.

이를 통해 알 수 있는 것은 40,000개 대신에 15,200개만 써도 blocking 없이 multistage로 crossbar switch의 complexity를 줄일 수 있다는 것을 알 수 있다.

 

TDM, with and without TSI

위의 방법을 사용해도 여전히 많은 crosspoints가 필요하기 때문에 요즘은 TDM을 이용하거나 the combination of space and time-division switches를 사용한다.

기본적으로는 TDM 구조를 갖지만 그대로 전달되는 것이 아니라 switching 과정을 위해서 중간에 TSI(Time slot interchange) 장치로 인해 원하는 곳으로의 switching이 이루어지게 된다.

 

Time-Slot Interchange(TSI)

control unit에 내용에 따라 output 내용을 change하여 꺼내도록 한다.

• 장점
  • crosspoint 가 복잡한 hardware 구성이 필요없다.
• 단점
  • 바로바로 데이터가 나가는 것이 아니라 중간에 저장이 되었다 나가기 때문에 그 때마다 delay가 발생한다.

 

Time- and Space-Division Switch Combination

• Space division:
  • instantaneous
  • crosspoints O
  • complexity
• Time division:
  • no crosspoint
  • processing delay
    • 들어온 데이터를 TSI를 통해 순서를 바꾸는데 드는 과정
• Space-and time-division switching combinations take advantage of the best of both
  • TST(time-space-time)
  • TSST(time-space-space-time)
  • STTS(space-time-time-space)

 

TST Switch

space division는 즉각적이긴 하지만 complexity가 있고

time division의 단점은 input(12개)을 만약 single stage로 묶었다고 치면 다 메모리에 채운 다음에 정해진 룰에 의해서 꺼내 가야 하니까 delay를 줄이기 위해서는 작은 size의 switch를 사용한다.

 

8.5 Structure of Packet Switch

• Four components: input port, output port, routing processor, switching fabric.

routing processor: VSN or DN에서 보면 routing table을 searching하는 것이 있었는데 이런 것들을 담당하는 곳이다.

switching fabric: 결정된 process에 따라 적절한 switch를 진행하는 곳이다.

• simplest type of switching fabric is the crossbar switch

 

Input/Output Port

• physical and data-link functions 가 수행됨.
• input 으로 들어온 것이 router process에서 해석되고 그 해석된 것에 따라 ouput fabric 나가는 것이 되고 순서대로 쌓여있다가 나가게 된다;
• network layer는 routing processor에서 처리

 

Structure of Packet Switch

• Routing processor: network layer functions
  • Table lookup: searching the routing table by destination address
• Switching Fabric
  • Crossbar switch
  • Banyan switch
  • Batcher-Banyan switch

 

Banyan Switch

• Multistage switch with microswitches at each stage that route the packets based on the output port represented as a binary string

micro 단위로 각각의 input에 대해서 특정 control 값을 주면 그 control에 의해서 output 값이 결정 되는 형태로 경로가 설정된 상태로 진행되는 것

 

Example of Routing in a Banyan Switch

각각의 input에 대해서 특정 control 값을 주면 그 control값에 의해서 output이 결정되는 형태로 경로가 설정된 형태로 동작하는 것이 banyan switch

• In part b, a packet has arrived at input port 5 and must go to output port 2 (010 in
  binary).
  The first microswitch (A-2) routes the packet based on the first bit (0),
  the second microswitch (B-2) routes the packet based on the second bit (1), and
  the third microswitch (C-2) routes the packet based on the third bit (0).

 

Batcher-Banyan Switch

• The problem with the banyan switch is the possibility of internal collision even when two packets are not heading for the same output port.
• 충돌을 막기 위한 방법
• Problem in Banyan switch: possibility of internal collision (내부 충돌의 가능성)
  • Solve it by sorting the arriving packets based on their destination port

• 충돌이 최대한 안 생기도록 목적지 주소에 기반해서 input 되는 것들의 순서를 sorting 하는데 그래도 못 피할 때는
• trap module을 통해 duplcated을 방지한다. delay 시킨다.
• 이것들 보다는 crosspoint switch가 더 중요하다.