Префрлање на црвоточини

Нема проверени преработки на оваа страница, што значи дека можеби не е проверено дали се придржува до стандардите.

Контрола на проток на црвоточина, исто така наречена префрлање на црвоточина или рутирање на црвоточина, е систем на едноставна контрола на проток во компјутерско вмрежување засновано на познати фиксни врски. Тоа е подгрупа на методи за контрола на проток наречена Контрола на проток Флит-пуфер.^[1] ^{:Chapter 13.2.1}

Префрлањето е посоодветен термин од рутирањето, бидејќи „рутирање“ ја дефинира маршрутата или патеката по која се стигнува до целта.^[2]^[3] Техниката на црвоточина не ја диктира маршрутата до одредиштето, но одлучува кога пакетот се движи напред од насочувачот.

Префрлањето на црвоточини се користи многу кај мултикомпјутерите поради ниската латентност и малите побарувања на јазлите.^[3]^:376

Рутирањето на црвоточини поддржува многу мала латентност, голема брзина, загарантирана испорака на пакети соодветни за комуникација во реално време.^[4]

Принцип на механизмот на работа

Во контролата на проток на црвоточина, секое пакување се распаѓа на мали парчиња наречени единици за контрола на проток (флитови).

Вообичаено, првите флитови, наречени заглавија, содржат информации за рутата на овој пакет (на пример, адреса за одредиште) и го поставуваат однесувањето на рутирање за сите последователни флитови поврзани со пакетот. Заглавјата се проследени со нула или повеќе флитови кои го содржат вистинскиот товар на податоци. Некои последни флитови, наречени опашки, извршуваат задачи кои ја затвораат врската помеѓу двата јазли.

При префрлање на црвоточини, секој тампон е во мирување или е распределен на еден пакет. Заглавие флитот може да се пренасочи до тампон ако овој тампон е во мирување. Ова го распределува тампонот на пакетот. Тело или приколка - флит може да се пренасочи во тампон ако овој тампон е распределен на неговиот пакет и не е полн. Последниот флит го ослободува тампонот. Ако преклопот на заглавието е блокиран во мрежата, тампонот се полни и откако ќе се наполни, не може да се испраќаат повеќе флитови: овој ефект се нарекува „повратен притисок“ и може да се движи назад до изворот.

Името „црвоточини“ го претставуваначинот на испраќање пакети преку врските: адресата е толку кратка што може да се преведе пред да пристигне самата порака. Ова му овозможува на насочувачот брзо да го постави рутирањето на вистинската порака. Бидејќи пакетот се пренесува флит по флит, тој може да зафати неколку пултови на флит по својот пат, создавајќи слика слична на црв.

Ова е прилично слично на преклопното движење,^[5] вообичаено наречено „виртуелно пробивање“, најголемата разлика е во тоа што контролата на проток со пресек ги распределува тампоните и пропусниот опсег на каналот на ниво на пакет, додека контролата на протокот на црвоточина го прави ова на нивото на флит.

Во случај на кружна зависност, овој повратен притисок може да доведе до ќор-сокак.

Во повеќето аспекти, црвоточината е многу слична на проследувањето на банкомат или MPLS, со исклучок дека ќелијата не мора да се чека на ред.

Она што е специфично во врска со контролата на проток на црвоточини е имплементација на виртуелни канали:

Виртуелниот канал ја задржува состојбата потребна за координирање на ракувањето со флитовите преку пакет. Во најмала рака, оваа состојба го идентификува излезниот канал на тековниот јазол за следниот скок на трасата и состојбата на виртуелниот канал (празен, чекајќи ресурси или активен). Виртуелниот канал може исто така да вклучува и покажувачи на прстените на пакетот што се тампонирани на тековниот јазол и бројот на расположливи тампони на следниот јазол.^[1] ^:237

Пример

Три текови на мрежата 2x2 со користење на префрлање на црвоточини

Замислете ја мрежата 2x2 на сликата десно, со 3 пакети што треба да се испратат: розова, направена од 4 флитови, 'UVWX', од C до D; сина, изработена од 4 флитови 'abcd', од А до Ф; и зелена, направена од 4 флитови „ijkl“, од E до H. Претпоставуваме дека рутирањето е пресметано, како што е нацртано, и подразбира судир на тампон, во долниот лев рутер. Пропусната моќност е од една флит на време единица.

Прво, размислете за розовиот проток: во времето 1, флитот 'U' се испраќа до првиот тампон; во времето 2, флитот 'U' поминува низ следниот тампон (под претпоставка дека пресметката на трасата не трае време), а флитот 'V' се испраќа до првиот тампон итн.

Сините и зелените текови треба да се презентираат чекор по чекор:

Време 1: И сините и зелените текови ги испраќаат своите први флитови, 'i' и 'a'.
Време 2: Флитот „i“ може да продолжи во следниот тампон. Но, тампон е посветен на пакет од првиот до последниот flit, и така, флитот „а“ не може да се проследи. Ова е почеток на ефект на повратен притисок . Флiтот 'j' може да го замени флитот 'i'. Флитот 'b' може да се испрати.
Време 3: Зелениот пакет продолжува. Синиот флит 'c' не може да се пренасочи (тампон е окупиран со флитовите 'b' и 'a'): овој ефект на повратен притисок го достигнува изворот на пакетот.
Време 4: Како во времето 3
Време 5: Зелениот пакет повеќе не го користи тампонот поставен лево-долу. Синиот пакет е деблокиран и може да се проследи (под претпоставка дека информацијата за „деблокирање“ може да се проследи во нулто време)
Време 6-10: Синиот пакет поминува низ мрежата.

Предности

Контролата на проток на црвоточини прави поефикасно користење на тампоните отколку пресеците. Онаму каде за пресек се потребни многу пакети вредни тампон-простори, на методот на црвоточини му требаат многу малку тампони (споредбено).
Целиот пакет не треба да се тампонира за да премине на следниот јазол, намалувајќи ја латентноста на мрежата во споредба со преклопувањето од зачувај и препрати.
Пропусниот опсег и распределбата на каналот се одвојуваат

Употреба

Техниките на црвоточини се користат првенствено во мултиобработувачски системи, особено хиперкуби. Во компјутерски хиперкуб, секој обработувач е прикачен на неколку соседи во фиксна шема, со што се намалува бројот на скокови од еден на друг обработувач. На секој обработувач е даден број (обично само од 8-битни до 16-битни ), што е негова мрежна адреса, а пакетите до обработувачите се испраќаат со овој број во заглавието. Кога пакетот ќе пристигне на среден рутер за пренасочување, насочувачот го испитува заглавието (многу брзо), поставува коло до следниот рутер и потоа се повлекува од разговорот. Ова значително ја намалува латентноста (доцнењето) во споредба со преклопувањето од зачувај и препрати што го чека целиот пакет пред да го препратите. Во поново време, контролата на проток на црвоточни го најде патот до апликациите во мрежните чипови системи (NOC). Овде, многу јадра на обработувачот, или на пониско ниво, дури и функционални единици можат да се поврзат во мрежа на еден пакет IC . Бидејќи одложувањата на жиците и многу други не-размерливи ограничувања на поврзаните елементи за обработка стануваат доминантен фактор за дизајнот, инженерите бараат да се поедностават организираните мрежи за интерконекција, во кои методите за контрола на проток играат важна улога.

Технологиите IEEE 1355 и SpaceWire користат црвоточина.

Виртуелни канали

Екстензија на контрола на црвоточина е виртуелен канал за контрола на проток, каде што неколку виртуелни канали може да се мултиплексираат преку еден физички канал. Секој еднонасочен виртуелен канал се реализира од независно управуван пар (флит) тампони. Различни пакети тогаш можат да го споделуваат физичкиот канал врз основа на флит по флит. Првично беа воведени виртуелни канали за да се избегне проблемот со ќор-сокак, но тие можат да се користат и за да се намали блокирањето на црвоточините, подобрување на латентноста и пропусната моќ на мрежата. Блокирање на црвоточина се случува кога пакет се здобива со канал, со што се спречуваат другите пакети да го користат каналот и принудувајќи ги да заглават. Да претпоставиме дека пакет P0 го стекнал каналот помеѓу два насочувачи. Во отсуство на виртуелни канали, пакетот P1 што пристигнува подоцна ќе биде блокиран сè додека не заврши трансмисијата на P0. Доколку се имплементираат виртуелни канали, можни се следниве подобрувања:

По пристигнувањето на P1, физичкиот канал може да се мултиплексира помеѓу нив на основа на флит по флит, така што двата пакета продолжуваат со половина брзина (во зависност од арбитражната шема).
Ако P0 е пакет со целосна должина, додека P1 е само мал контролен пакет со големина на неколку лета, тогаш оваа шема овозможува P1 да помине низ двата насочувачи, додека P0 се забавува за кратко време, што одговара на преносот на неколку пакети. Ова ја намалува латентноста за P1.
Да претпоставиме дека P0 е привремено блокиран низводно од тековниот рутер. Пропусната моќ се зголемува со дозволување на P1 да продолжи со полна брзина на физичкиот канал. Без виртуелни канали, P0 ќе го окупира каналот, без всушност да го користи достапниот ширина на опсег (бидејќи тој е блокиран).^[6]

Користењето виртуелни канали за намалување на блокирањето на црвоточините има многу сличности со користењето на редици за виртуелни излези за да се намали блокирањето на врвните линии

Рутирање

Може да се користи мешавина од изворно рутирање и логично рутирање во истиот пакет со вклучена црвоточина. Вредноста на првиот бајт од пакетот Myrinet или SpaceWire е адресата на пакетот. Секој прекинувач SpaceWire ја користи адресата за да одлучи како да го рутира пакетот.^[7]

Рутирање на изворот

Со рутирање на изворот, испраќачот на пакет избира како да се рутира пакетот преку прекинувачот.

Ако првиот бајт од влезниот пакет SpaceWire е во опсег од 1 до 31, тоа ја означува соодветната порта од 1 до 31 на прекинувачот Spacewire. Прекинувачот SpaceWire потоа го отфрла тој карактер за рутирање и го испраќа остатокот од пакетот од таа порта. Ова го изложува следниот бајт од оригиналниот пакет на следниот прекинувач SpaceWire. Испраќачот на пакет може да избере да користи рутирање на изворот за експлицитно да ја одреди целосната патека низ мрежата до крајното одредиште на овој начин.^[7]

Логично рутирање

Со логично рутирање, прекинувачот Spacewire сам одлучува како да го рутира пакетот.

Ако адресата (првиот бајт) на дојдовниот пакет SpaceWire е во опсег од 32 до 255, прекинувачот SpaceWire ја користи таа вредност како индекс во табела за внатрешно рутирање што покажува која порта (и) да го испрати пакетот и дали да се избрише или задржете го првиот бајт.^[7]

Адресата 0 се користи за директно комуницирање со прекинувачот и може да се користи за поставување на записите на табелата за рутирање за тој прекинувач.^[7]

Поврзано

Наводи

↑ ^1,0 ^1,1 William James Dally; Brian Towles (2004). „13.2.1“. Principles and Practices of Interconnection Networks. Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-200751-4.
↑ John L. Hennessy and David A. Patterson (2006). „Appendix E.5“. Computer Architecture: A Quantitative Approach (Fourth. изд.). Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-370490-0.
↑ ^3,0 ^3,1 Mohapatra, Prasant (1998), „Wormhole Routing Techniques for Directly Connected Multicomputer Systems“ (PDF), ACM Computing Surveys, 30 (3): 374–410, doi:10.1145/292469.292472, Архивирано од изворникот (PDF) на 2017-08-11, Посетено на 2020-11-14
↑ Sharad Sundaresan; Riccardo Bettati. "Distributed Connection Management for Real-Time Communication over Wormhole-Routed Networks". 1997.
↑ Stefan Haas. "The IEEE 1355 Standard: Developments, Performance and Application in High Energy Physics". 1998. p. 59.
↑ Pavel Tvrdik. "Why wormhole routing is an important switching technique"
↑ ^7,0 ^7,1 ^7,2 ^7,3 Dr Barry M Cook; Paul Walker. "Ethernet over SpaceWire - software issues". 2007. p. 2.

[Dally_and_Towles-1] 1,0 ^1,1 William James Dally; Brian Towles (2004). „13.2.1“. Principles and Practices of Interconnection Networks. Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-200751-4.

[2] John L. Hennessy and David A. Patterson (2006). „Appendix E.5“. Computer Architecture: A Quantitative Approach (Fourth. изд.). Morgan Kaufmann Publishers, Inc. ISBN 978-0-12-370490-0.

[Mohapatra-3] 3,0 ^3,1 Mohapatra, Prasant (1998), „Wormhole Routing Techniques for Directly Connected Multicomputer Systems“ (PDF), ACM Computing Surveys, 30 (3): 374–410, doi:10.1145/292469.292472, Архивирано од изворникот (PDF) на 2017-08-11, Посетено на 2020-11-14

[4] Sharad Sundaresan; Riccardo Bettati. "Distributed Connection Management for Real-Time Communication over Wormhole-Routed Networks". 1997.

[5] Stefan Haas. "The IEEE 1355 Standard: Developments, Performance and Application in High Energy Physics". 1998. p. 59.

[6] Pavel Tvrdik. "Why wormhole routing is an important switching technique"

[Cook-Walker-7] 7,0 ^7,1 ^7,2 ^7,3 Dr Barry M Cook; Paul Walker. "Ethernet over SpaceWire - software issues". 2007. p. 2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]