Korea Digital Contents Society

Journal Archive

Journal of Digital Contents Society - Vol. 21 , No. 10
[Paper List] [Go to Volume List]

[ Article ]
Journal of Digital Contents Society - Vol. 21, No. 10, pp. 1879-1883
Abbreviation: J. DCS
ISSN: 1598-2009 (Print) 2287-738X (Online)
Print publication date 31 Oct 2020
Received 23 Sep 2020 Revised 08 Oct 2020 Accepted 08 Oct 2020
DOI: https://doi.org/10.9728/dcs.2020.21.10.1879

네트워크 코딩 효율에 기반한 네트워크 코딩 결정 기법
강영명1
1삼성전자 네트워크사업부 책임연구원

Network Coding Decision Algorithm based on Coding Efficiency
Young-Myoung Kang1
1Staff Researcher, Network Division, Samsung Electronics, SUWON 123-456, Korea
Correspondence to : *Young-Myoung Kang E-mail: kang.youngmyoung@gmail.com


Copyright ⓒ 2020 The Digital Contents Society
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-CommercialLicense(http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
초록

네트워크 코딩(Network Coding)은 여러 개의 패킷을 하나로 인코딩 (encoding) 하여 총 전송횟수를 줄이는 방법으로 자원이 매우 제한적인 무선망에서 시스템 성능을 향상시키는 기술로 평가를 받아왔다. 가능한 한 더 많은 패킷을 인코딩하여 전송효율을 높이는 데 집중한 기존 연구와 달리 본 연구에서는 패킷의 길이와 전송 속도 등을 고려해 네트워크 코딩을 할 때와 하지 않을 때의 효율을 분석하고 이 결과에 따라 코딩 여부를 선택할 수 있는 기법을 제시한다. 성능 평가 결과 전송 속도가 빠른 링크로 전송되는 패킷의 사이즈가 전송속도가 느린 패킷의 사이즈보다 작을 때는 항상 네트워크 코딩의 효과가 유효하며, 네트워크 코딩을 적용하는 패킷의 크기가 동일할 때 효율이 가장 좋다는 것을 확인할 수 있었다.

Abstract

Network coding is an advanced technology that improves the system capacity in wireless networks by reducing the total number of transmissions by encoding multiple packets into one. Contrary to the previous studies that focused on increasing the transmission efficiency by encoding as many packets as possible, we take into account the length of the packet and transmission rates to evaluate the efficiency of the network coding for the cases whether the network coding is performed or not. Based on these evaluation results, we can decide whether to conduct the network coding selectively. The extensive analytical evaluations shows that the network coding is always beneficial when the size of a packet transmitted with a higher transmission rate is smaller than that of a packet with a lower transmission rate, and the efficiency is the best when the sizes of the encoded packets are identical.

Keywords: Network Coding, Performance Evaluation, System Throughput, WLAN, Wireless Network, etc
키워드: 네트워크 코딩, 성능 평가, 시스템 처리량, 무선랜, 무선 네트워크
Ⅰ. 서 론

무선망을 사용하는 기기들이 폭발적으로 늘어남에 따라 전송 효율을 높이려는 노력은 지속적으로 확대되어 왔다. 점대점(point-to-point) 방식에 기반을 둔 유선망의 전송방식과 달리 무선망은 한정적인 전송매체를 공유해야 한다는 본질적 한계를 가지고 있다. 본 논문에서는 유선망에서 멀티캐스트 성능을 향상시키기 위해서 제안된 네트워크 코딩 (Network Coding) [1]-[3] 기법이 본질적으로 브로드캐스팅 특성을 가지는 무선망에 결합되어 무선망의 전송 성능을 향상시켜줄 수 있다는 것에 초점을 두고 다양한 관점에서 전송효율을 분석한다.

네트워크 코딩은 2개 이상의 패킷들을 하나의 패킷으로 인코딩 (encoding) 하여 전송하는 방법으로써 전송 횟수대비 전송된 데이터의 량을 증가시켜 시스템 처리량 (Throughput) 측면에서 성능 향상을 기대할 수 있다. 네트워크 코딩은 코딩 방식에 따라 여러 개의 패킷을 선형적으로 코딩한 Random Linear Network Coding [4] 과 단순 XOR 연산을 하는 코딩 방식인 바이너리 네트워크 코딩 [5]로 나눌 수 있다. 한편, 네트워크 코딩을 적용하는 대상이 Flow와 다른 Flow사이의 코딩인지 혹은 하나의 Flow 내에서의 코딩인지에 따라 Inter-flow network coding과 Intra-flow network coding [6]으로 나눌 수 있다. 이 논문에서는 Inter-flow 네트워크 코딩에 대해서 다룬다.

네트워크 코딩을 통해 시스템 성능 향상이 되려면 목적지가 서로 다른 2개 이상의 패킷들을 중간 노드에서 하나의 패킷으로 인코딩하고, 인코딩 된 패킷은 각각의 목적노드로 성공적으로 전송되어야 한다. 그러나 무선 통신 환경에서는 신호감쇄에 영향을 주는 여러 가지 요소들로 인하여 같은 노드에서 전송된 신호라고 하더라도 신호를 수신하는 노드의 환경에 따라서 수신되는 신호의 세기가 달라진다 [7]-[9].

네트워크 코딩을 사용하는 경우에도 인코딩된 패킷이 각각의 수신 노드에서 성공적으로 수신되어 디코딩 (decoding) 되는 것을 보장하기 위해 데이터 전송속도가 가장 낮은 목적지를 기준으로 패킷을 인코딩하여 전송해야 한다. 그렇지 않으면 인코딩된 패킷의 모든 목적 노드들이 성공적으로 패킷을 수신할 확률이 급격히 떨어지게 되며 네트워크 코딩으로 인한 시스템 처리량 향상 효과 역시 보장할 수 없다. 심지어는 더 나쁜 성능을 초래할 수 있다. 추가적으로 네트워크 코딩이 좋은 효과를 보이기 위해서는 인코딩 될 패킷들의 길이가 모두 같거나 비슷해야 한다는 조건이 필요하다. 서로 다른 길이의 패킷을 인코딩하여 네트워크 코딩을 적용하면 작은 길이의 패킷은 긴 패킷의 전송완료까지 같이 기다리는 역효과가 나타나게 된다.

기존의 네트워크 코딩 연구는 패킷의 코딩 기법을 집중적으로 다루었다. 본 연구에서는 무선망의 링크 품질과 패킷의 길이, 전송 속도 그리고 링크의 전송 성공률 등을 고려해 네트워크 코딩을 할 때와 하지 않을 때의 효율을 분석함으로써 선택적으로 코딩 여부를 결정하는 알고리듬을 제안한다.

여러 패킷에 네트워크 코딩을 적용할 경우에 채널 상황을 고려해서 성공적인 전송의 확률을 최대한 보장하기 위해서는 전송속도는 가장 낮은 쪽을 선택하고, 패킷의 길이는 가장 긴 것을 기반으로 네트워크 코딩을 적용해야 한다. 우리는 네트워크 코딩의 효율성을 분석할 수 있는 척도 및 알고리즘을 제시하여 성능 평가를 진행했다. 다양한 파라미터를 적용하여 성능 평가를 진행한 결과 네트워크 코딩의 효율성은 패킷의 사이즈와 전송 속도에 크게 영향을 받으므로 시스템 처리량에 기반하여 네트워크 코딩 적용여부를 결정해야 한다. 전송 성공률 등의 인자들도 네트워크 코딩 효율에 영향을 줄 수 있으나 이 부분은 추가 연구가 필요하다.

논문의 구성은 다음과 같다. 2장에서는 풀고자 하는 문제를 정의하고, 3장에서는 네트워크 코딩 분석을 위한 척도 (Measure) 및 알고리즘을 제안하고 분석 결과를 제시한다. 4장에서는 본 논문의 결론을 맺는다.

Ⅱ. 문제 정의

기존의 네트워크 코딩 연구는 대체로 단일 전송속도 (single rate) 만을 고려하였고 패킷의 길이도 같다는 가정에서 성능평가를 한 경우가 대부분이다. 오늘날 사용되는 대부분의 무선망 장비들은 채널의 상태에 따라 전송속도를 선택적으로 결정할 수 있다. IEEE 802.11b 의 경우 1, 2, 5.5, 11 Mbps의 4가지 전송속도를 지원하고, IEEE 802.11a의 경우에는 6 ~ 54 Mbps까지 9개의 전송속도를 지원한다. IEEE 802.11 무선랜의 PHY (Physical Layers) 기술에 따른 다양한 전송속도는 아래 표 1을 참고한다. 참고로 아래 표에서는 대역폭과 MU-MIMO 적용 등을 고려하지 않아 최대 전송속도는 제한적으로 보일 수 있다.

Table 1. 
802.11 Physical Layers Data Rates (20 MHz)
802.11b 802.11a 802.11n 802.11ac
Data Rates
(Mbps)		 1
2
5.5
11		 6
9
12
18
24
36
48
54		 7.2
14.4
21.7
28.9
43.3
57.8
65
72.2		 7.2
14.4
21.7
28.9
43.3
57.8
65
72.2
86.7

또한 패킷의 길이도 동일하지 않는 경우가 대부분이다. 따라서 다중 전송속도와 다양한 패킷의 길이를 같이 고려해야 기대했던 시스템 성능향상을 확보할 수 있다. 일반적으로 네트워크 코딩을 위해서는 추가적인 헤더가 필요하고 더 많은 연산을 요하는 부분이 있으나 본 논문에서는 네트워크 코딩을 위한 필드 추가 및 컴퓨팅 오버헤드는 없는 것으로 가정한다.

본 논문에서 설명하고자 하는 문제를 쉽게 이해하기 위해 그림 1의 예를 통해 네트워크 코딩의 성능을 비교해 보자. 그림 1에서 N1은 N2에게 중간 노드 R을 통해서 데이터(P2)를 전송하고 N2는 R을 통해서 N1에게 데이터(P1)를 전송한다. 따라서 R에서는 두 개의 다른 패킷이 자신을 교차해서 지나가므로 네트워크 코딩을 적용할 수 있는 기회가 있다. R-N1 링크는 11 Mbps를 지원하고 R-N2 링크는 1 Mbps를 지원한다고 가정해보자. 추가적으로 우리는 이 비교분석에서 패킷의 길이가 동일한 경우와 동일하지 않은 경우를 분리해서 결과를 설명한다.


Fig. 1. 
Multi-rate Network Coding Example

2-1 패킷의 길이가 동일한 경우

패킷이 에러 없이 한 번에 성공적으로 전송된다면 전송속도에 상관없이 네트워크 코딩을 적용한 경우가 적용하지 않을 경우보다 항상 이득을 볼 수 있다. 시간 공정성 (Temporal Fairness) [10] 을 고려하는 모델이라면 속도가 빠른 링크와 속도가 느린 링크가 무선 매체를 점유하는 시간이 같아지도록 유도하여 공평하게 자원을 나누어 쓰도록 한다. 그러나 우리는 이 예에서 단지 두 개의 패킷을 한 번씩 보내야 하는 경우로 한정한다.

2-2 패킷의 길이가 다른 경우

N1에 보내야 하는 패킷의 길이는 50 bytes, N2에게 보내는 패킷의 길이는 500 bytes 라고 가정해보자. 이 경우 네트워크 코딩을 적용하게 되면 전송속도는 둘 중 낮은 전송속도로 둘 중 더 긴 패킷의 길이로 네트워크 코딩이 적용된다. 즉, 길이가 짧은 패킷은 패딩 (padding) 을 하여서 긴 패킷에 XOR 연산을 하게 된다. 따라서 그림 1의 예에서는 네트워크 코딩을 적용하게 되면 500 Bytes 패킷을 1 Mbps의 속도로 보내게 되어 시스템 처리량이 크게 낮아진다. 네트워크 코딩을 하게 되면 네트워크 코딩을 하지 않는 것에 비해 오히려 더 성능이 나빠질 수 있음을 알 수 있다.

Ⅲ. Network Coding Decision Making
3-1 Application Layer Throughput Calculation

본 논문에서는 바이너리 네트워크 코딩을 대상으로 한다. 즉 두 flow 간의 inter-flow 네트워크 코딩의 적용여부를 판단한다. 또한 중간 노드 R은 선입선출 (FIFO Queue) 방식으로 동작한다.

무선랜 전송 시스템의 성능 척도로는 일반적으로 아래 식 (1)로 표현되는 application layer 처리량을 사용한다. 식 (1)은 기본적으로 application data 를 전송하는데 얼마 동안의 시간이 소요되었는지를 보는 것인데 DIFS, SIFS, ACK 은 고정 값이고 BO는 충돌률에 연동되는 값이지만 경쟁에 참여하는 노드 개수에 따라 평균값으로 계산할 수 있다. 수식에서 중점적으로 보아야 할 것은 txdur로 표현되는 전송 속도 (TX rate)와 application message data 의 크기이다. 본 논문에서도 이 두 개의 값에 초점을 맞추어 성능 분석을 진행한다.

Table 2. 
Application Layer T-put Parameters (802.11b)
Type Value
appdata 1460 bytes
UDP header 8 bytes
IP header 20 bytes
LLC/SNAP header 8 bytes
MAC header 24 bytes
PLCP header 48 bytes
PLCP preamble 72 usec
CWmin 31
SIFS 10 usec
Slot 20 usec

app.tput=sizeappdataDIFS+BO+txdur+SIFS+ACK(1) 

여기서, 식 (1)의 txdur 는 아래 식 (2)에 해당한다.

txdur=sizeappdata+UDP/IP/LLC/PLCPHeader+PLCPpreambletxdur(2) 
3-2 Network Coding Decision Algorithm

두 개의 링크 L1과 L2에 대해 각각의 링크는 r1과 r2의 전송속도를 가진다고 하자. 그리고 각 링크로 길이가 X, Y인 패킷이 전송된다고 가정하자. 이 때 중간 노드 R에서 네트워크 코딩의 이득을 계산한다. 먼저 네트워크 코딩을 적용하지 않는 경우에는 X와 Y를 각각 r1과 r2로 전송할 때 걸리는 시간을 구하고, 구해진 시간으로 X와 Y의 합을 나누어 주면 전송 효율에 대한 기대 값을 구할 수 있다. 네트워크 코딩을 적용하는 경우에는 X와 Y 중 더 긴 패킷을 r1과 r2중 더 낮은 전송속도로 나누어준다. 그리고 X와 Y의 합을 구해진 시간으로 나누어주면 네트워크 코딩을 적용할 때의 전송 효율 기대 값이 구해진다. 네트워크 코딩을 할 때와 하지 않을 때는 전송시간이 달라질 수 있으므로 하나의 시간에 대해서 정규화(normalize) 한 다음 성능을 비교해 보고 그 결과에 따라 네트워크 코딩 여부를 결정한다. 아래 그림 2에서는 상기에서 설명한 네트워크 코딩 여부 결정 알고리듬의 의사 코드 (pseudo code)를 보여준다.


Fig. 2. 
Network Coding Decision Algorithm

그림 2의 알고리즘을 예제를 통해 설명한다. 그림 1의 토폴로지에서 L1 링크는 11 Mbps의 전송속도로 X bytes 길이의 패킷을 보내야 하고, L2 링크는 1 Mbps의 속도로 500 bytes를 전송해야 한다고 가정하자. X의 값에 따라 Throughput은 그림 3과 같은 결과를 나타낸다. 우리는 IEEE 802.11b 에 해당하는 값으로 설정하여 분석을 하였다. L1 의 패킷 사이즈가 증가함에 따라 L2의 패킷 사이즈인 500 Bytes에서 네트워크 코딩 성능이 가장 좋았으며 대략 550 Bytes 이상 될 때부터 오히려 네트워크 코딩으로 인해 성능이 저하된다. 한편 전반적으로 전체 시스템 성능이 떨어져 보이는 데, 이 현상에 대한 분석은 이미 [10]에서 설명 되었다. 전송속도 차이가 많이 나는 노드들이 동일한 전송 기회를 받으면, 상대적으로 전송속도가 낮은 노드가 전송시간을 많이 점유하게 되어 전체 시스템 성능은 나빠지게 된다. 이 경우에는 1 Mbps 로 전송하는 노드가 11 Mbps로 전송하는 노드의 전송 기회를 빼앗았기 때문에 전체 시스템 성능이 나빠진 것이다.


Fig. 3. 
Multi-rate Network Coding gain (802.11b)

다음으로 우리는 토폴로지를 그대로 유지한 채 시험 인자들을 IEEE 802.11a 설정으로 변경하였다. L1은 54 Mbps, L2는 6 Mbps 의 전송속도로 설정하였다. 그림 4와 같이 이 실험 결과의 추이는 802.11b와 매우 유사하였다.


Fig. 4. 
Multi-rate Network Coding gain (802.11a)

마지막으로 동일 조건에서 L2의 패킷 사이즈를 500 Bytes 와 1000 Bytes로 변경하여 시험을 진행하였고 그 결과는 그림 5를 통해 확인할 수 있다. 기본적으로는 앞서 진행한 시험결과와 추이는 비슷하였다. 한편 이 결과를 통해 추가 확인할 수 있는 것은 전송 속도가 빠른 링크로 전송되는 패킷의 사이즈가 전송속도가 느린 패킷의 사이즈보다 작을 때는 항상 네트워크 코딩의 효과가 유효하며, 네트워크 코딩을 적용하는 패킷의 크기가 동일할 때 효율이 가장 좋다는 것을 알 수 있다. 반면에 전송속도가 빠른 링크로 전송되는 패킷의 사이즈가 전송속도가 느린 패킷의 사이즈보다 커져갈 때 특정 시점을 기준으로 네트워크 코딩의 효율이 더 저하되는 것을 알 수 있다.


Fig. 5. 
Multi-rate Network Coding gain according to Packet Length (500 bytes vs. 1000 bytes)

따라서 네트워크 코딩은 항상 성능 향상을 보장할 수 없으므로 정교한 모델링과 성능 평가를 통해 실시간으로 적용되는 것이 바람직하다.

Ⅳ. 결 론

본 논문에서는 수학적 분석을 통해 무선 네트워크 코딩의 효과에 대해 성능 평가를 진행하였다. 그리고 네트워크 코딩의 성능 효율을 실시간 분석하여 선택적으로 네트워크 코딩 여부를 실시간 확인할 수 있는 방안을 제시하였다. 분석과 시물레이션 결과를 통해 다중 전송 속도와 패킷의 길이가 시스템 처리량에 큰 영향을 주게 된다는 것을 확인하였다. 특히, 전송 속도가 빠른 링크로 전송되는 패킷의 사이즈가 전송속도가 느린 패킷의 사이즈보다 작을 때는 항상 네트워크 코딩의 효과가 유효하며, 네트워크 코딩을 적용하는 패킷의 크기가 동일할 때 효율이 가장 좋다는 것을 보였다. 네트워크 코딩의 성능 확보를 위해서는 정교한 모델링과 성능 평가가 뒷받침 되어야 할 것이다.

References
1. R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung. "Network Information Flow", In IEEE Transactions on Information Theory, Vol. 46, Issue. 4, pp. 1204-1216, Jul 2000
2. Alejandro Cohen, Guillaume Thiran, Vered Bar Bracha, Muriel Médard, "Adaptive causal network coding with feedback for multipath multi-hop communications", In Proc. IEEE International Conference on Communications (ICC), Dublin, Ireland, Ireland, pp 1-7, June 2020.
3. L Wang, Y Li, B Pan, Q Wu, J Yin, L Xu, "Network Coding for Efficient Video Multicast in Device-to-Device Communications", In Sensors 2020, 20(8), 2254, 2020.
4. S. R. Li, R. W. Yeung, and N. Cai. "Linear network coding", In IEEE Transactions on Information Theory, Vol. 49, Issue. 2, pp. 371-381, Feb 2003.
5. S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft. "Xors in the air: Practical wireless network coding", In Proc. of ACM SIGCOMM’06, September 2006.
6. S. Chachulski, M. Jennings, S. Katti, and D. Katabi, “Trading Structure for Randomness in Wireless Opportunistic Routing,” in Proc. of ACM SIGCOMM, 2007.
7. Raja Karmakar, Samiran Chattopadhyay, Sandip Chakraborty, "IEEE 802.11ac Link Adaptation Under Mobility", In Proc. 2017 IEEE 42nd Conference on Local Computer Networks (LCN), Singapore, Singapore, pp. 392 - 400, Oct. 2017.
8. Raja Karmakar, Samiran Chattopadhyay, Sandip Chakraborty, "An online learning approach for auto link-Configuration in IEEE 802.11ac wireless networks", In Elsevier Computer Networks, vol 181(pre)Nov. 2020.
9. P. Chevillat ; J. Jelitto ; A.N. Barreto ; H.L. Truong, "A dynamic link adaptation algorithm for IEEE 802.11 a wireless LANs", In Proc. IEEE International Conference on Communications, 2003. ICC '03. Anchorage, AK, USA, pp. 1141-1145, May 2003.
10. G. Berger-Sabbatel, F. Rousseau, M. Heusse and A. Duda, "Performance anomaly of 802.11b", In Proc. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, USA, pp. 836 - 843, July 2003.

저자소개

강영명(Young-Myoung Kang)

2003년 : 서울대학교 대학원 (공학석사)

2012년 : 서울대학교 대학원 (공학박사)

2003년～2006년: LG전자

2012년～현 재: 삼성전자

※관심분야：컴퓨터 네트워크(Computer Network), 소셜 네트워크(Social Network), 무선랜(WLANs) 등

 
Copyrightⓒ2015 Korea Digital Contents Society. All Right Reserved.

Korea Digital Contents Society(KDCS) #914, 133, Dunsan-ro, Seo-gu, Daejeon, Republic of Korea (Zip code : 35240)
Phone : +82- 70 - 4212-0127, 042-484-3232 Email : dcs@dcs.or.kr Homepage : http://www.dcs.or.kr