Деректерді тасымалдау ортасы

Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 34 бет
Таңдаулыға:

ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ

Қ. И. Сәтбаев атындағы Қазақ ұлттық техникалық университеті

Ақпараттық технологиялар институты

Есептеу техникасы кафедрасы

Курстық жобаға арналған

ТҮСІНДІРМЕ ЖАЗБА

Тақырыбы: “Fast Ethernet жергілікті желісін жобалау”

Тексерген:

Тех. ғыл. кан., проф. Тұрым А. Ш.

Орындаған: Сейталин Н. А.

Мамандығы: 3704

Оқу тобы: ЗБИ-02-1қ

АЛМАТЫ 2006

ТАПСЫРМА

№15 тапсырма. Келесі сипаттамалары бар жергілікті желіні жобалау керек:

Сызба-құрылым (топология) - Жұлдыз;
Қатынас құру әдісі - СSМА/CD;
Желінің түйіндерінің саны - 21;
Синтез жасау әдісі - МІӘ;
Желілік шабуыл - ICMP Redirect жалған хабары;
Кадр түрі: Fast Ethernet SNAP кадры;
Желілік бейімдеуіштің функционалдық сұлбасын әзірлеу және сипаттау;
Жергілікті желіні салу, оған түсініктеме беру.

Тапсырма берілген күн: „25” қыркүйек 2006 жыл.

Тапсырма берген: т. ғ. к., профессор: Тұрым А. Ш.

Тапсырма алған студент: Сейталин Н. А.

МАЗМҰНЫ

КІРІСПЕ4

1 FAST ETHERNET ЖЕРГІЛІКТІ ЖЕЛІСІН ЖОБАЛАУ5

1. 1 Желі үлгілері5

1. 2 Желілік сызба- құрылымдар8

1. 3 Деректерді тасымалдау ортасы9

1. 4 Деректерді тасымалдау ортасына қатынас құру әдістері11

1. 5 Желінің құрылымын синтез жасау13

1. 5. 1 Жұлдыз тәрізді құрылымның математикалық үлгісі13

1. 5. 2 Cинтез жасау, медиана іздеу әдісі14

1. 6 Хаттамалар және стандарттар16

1. 6. 1 Fast Ethernet SNAP кадры16

1. 6. 2 Fast Ethernet стандарттары19

1. 7 Сигналды физикалық деңгейде кодалау20

1. 8 Желілік бейімдеуіштің функционалды сұлбасы22

1. 9 Желілік шабуылдар24

1. 10 Жабдықтар айқындамасы26

1. 11 Ақпараттық кәбілді салу-жүргізу сұлбасы26

1. 12 Желінің құрылымдық сұлбасы28

1. 13 Желінің параметрлерін есептеу33

ҚОРЫТЫНДЫ34

ӘДЕБИЕТТЕР ТІЗІМІ35

ҚОСЫМША А36

ҚОСЫМША Ә37

ҚОСЫМША Б38

ҚОСЫМША Г39

ҚОСЫМША Д40

КІРІСПЕ

Бұл курстық жобаның негізгі мақсаты әрқайсымызға берілген тапсырма бойынша компьютерлік желіні жобалау және алған білімімізді бекіту.

Алдымен, компьютерлік желі дегеніміз - арнайы коммуникациялық құрылғы мен программалық қамтама арқылы бір-бірімен ақпараттық әрекеттесу мүмкіндігі бар түйіндердің (копьютерлердің, терминалдардың, баспа құрылғылары) жинтығы. Желінің өлшемі өте кең, ол көршілес стөлдерде орналасқан екі компьютерден, дүниежүзінің шеткері жерлерінде орналасқан миллиондаған компьтерлерді байланыстырады. Өлшеміне байланысты желі бірнеше түрге бөлінеді. Соның бірі - жергілікті желі немесе LAN (Local Area Network) . Жергілікті желі деп бір-бірімен шамалы ғана қашықтықта орналасқан және деректер тасымалданатын физикалық орта арқылы біртұтас желіге біріктірілген абонеттік жүйелер (есептеу машиналары, принтерлер, т. б. ) жиынтығын айтады.

Жергілікті желілердің алғашқылары - 1970 жылдары IBM фирмасы ұсынған Token Ring технологиясы және 1980 жылы DEC, Intel және Xerox фирмаларының ұсынған Ethernet технологиясы. Қазір, көптеген жаңа жоғары жылдамдықты коммуникациялық технологиялар пайда болды. Internet желісінің күрт өсуінен және ақпаратты жылдам жеткізудің қажеттілігінен жоғары жылдамдықты АТМ, ISDN, Fast Ethernet және Gigabit Ethernet технологиялары кең тарала бастады. Пайдаланушыларға жоғары жылдамдықты кең жолақты технологияларды артықшылықтарын тиімді пайдалана алатын жаңа хаттамалар стандарттары жасалынған.

1 FAST ETHERNET ЖЕРГІЛІКТІ ЖЕЛІСІН ЖОБАЛАУ

1. 1 Желі үлгілері

Адамдар өзара қарым-қатынас жасау үшін ортақ тіл қолданады. Егер олар тікелей сөйлесе алмаса, онда хабар жіберу үшін сәйкес қосымша амал пайдаланады. Хабарды таратушыдан қабылдаушыға жіберу кезінде де осыған ұқсас механизм пайдаланылады.

Ақпаратты байланыс желісі арқылы тасымалдау үшін деректерді бірдей кодалайтын және өзара байласуы бар машиналар керек. Ақпараттар тасымалданатын байланыс желісіндегі деректерді бірегей түрге келтіру үшін Халықаралық стандарттар Ұйымы (ағыл. ISO - International Standarts Organization) құрылған.

Ашық жүйелер әрекеттестігі (АЖӘ), TCP/IP, IBM фирмасының SNA (System Network Architecture), Digital компаниясының DNA (Digital Network Architecture), Novell фирмасының NovellNetWare, АТМ (Asynchronous Transfer Mode) және т. б. желілік үлгілер бар.

1984 жылы Халықаралық стандарттар Ұйымы негізгі желі үлгісі - ашық жүйелер әрекеттестігін (ағыл. OSI - Open Systems Interconnection) жасап шығарады. Бұл үлгі деректерді тасымалдауда халықаралық стандарт болып табылады.

OSI үлгісі жеті бөлек деңгейлерге бөлінген:

1) Физикалық - ақпаратты жіберудің биттік хаттамасы; 2) Арналық кадрды пішіндеу, ортаға қатынас құруды басқару; 3) Желілік - бейімдеуіш, деректер ағынын басқару; 4) Көліктік - алшатылған үрдістердің өзара әрекеттестігін қамтамасыз ету; 5) Сеанстық - алшатылған үрдіс арасындағы диалогты қолдау; 6) Көрсетімдік - жіберілетін деректердің интерпретациясы; 7) Қолданбалық - деректерді қолданбалы басқару.

Осы аталған деңгейлер атқаратын қызметтеріне қарай үш топқа бөлінеді. Алғашқы үшеуі (физикалық, арналық, желілік) деректерді тасымалдау мен бағдарғылауға жатады. Төртінші (көліктік) деңгей алғашқы үшеуі мен жоғарғы деңгейлер арасындағы байланысты қамтамасыз етеді. Соңғы үш (сеанстық, көрсетімділік, қолданбалы) деңгей пайдаланушылар қолданбаларына қызмет көрсетеді.

Бұл үлгінің негізгі мақсаты әр деңгейге, тасымалдау ортасына да белгілі бір міндетті жүктеу. Осыған байланысты деректерді жіберудің жалпы есебі бөлек жеңіл есептерге бөлінеді. Әрбір деңгей өзінің жоғарғы деңгейге көрсететін қызметімен және хаттамасымен анықталады. Төменгі деңгей жоғарғы деңгейге қызмет етеді. Сервис әрбір деңгейдің қандай қызмет атқаратынын анықтайды, бірақ оның қалайша жүзеге асырылатынын көрсетпейді. Бір деңгейдің жоғары немесе төмен орналасқан деңгейлермен байланысына қажетті келісімдер хаттама деп аталады.

Базалық үлгінің дербес деңгейлері деректерді жіберушіде төмен бағытталған (7-деңгейден 1-деңгейге) және деректерді қабылдаушыда жоғары бағытталған (1-деңгейден 7-деңгейге) . Соңғы деңгейге жетпегенше пайдаланушының деректері төмен орналасқан деңгейге арнайы тақырыппен қоса жіберіліп тұрады.

Физикалық деңгейде (Physical layer) Желілік байланыс арнасы арқылы деректер тасымалдайды және осы міндетті атқаратын аппараттық құралдардан тұрады. Хабар құрайтын символдар электрлік сигналдарға түрлендіріледі және олардың есептеу машиналар арасында тасымалданылуы қамтамасыз етіледі. Бұл деңгейде есептеу машиналарының аттары, хабардың мазмұны және оның тасымалданатын бағдарғысы жайында ештеңе белгісіз болады. Басқа деңгейлерде осы жұмыстар істелініп қойылғандықтан физикалық деңгейде тек электрлік сигналдарды кәбілге жіберу жұмыстары ғана жүргізіледі.

Физикалық деңгей ақпарат дестелерін жоғары жатқан деңгейлерден алып, оларды 0 немесе 1-лік бинарлық ағынды электрлік немесе оптикалық сигналдарға айналдырады. Бұл сигналдар тасымалдау ортасы арқылы қабылдау түйініне барады. Тасымалдау ортасының механикалық және электрлік/оптикалық қасиеттері физикалық деңгейде анықталады және мыналардан құралады:

1) кәбілдер типі;

2) 0 және 1 мәндерін кодалау сұлбасы.

Физикалық деңгейдің көп тараған түрлеріне мыналар жатады:

EIA-RS-232-C, CCITT V. 24/V. 28 - тураланбаған тізбекті

интерфейстің механикалық/электрлік сипаттамалары;

EIA-RS-422/449, CCITT V. 10 - тураланған тізбекті интерфейстің механикалық/электрлік және оптикалық сипаттамалары;
IEEE 802. 3u - Fast Ethernet; +IEEE 802. 5 - Token ring.

Арналық деңгей (Data Link layer) . Физикалық деңгейге керек биттер тасымалданады. Арналық деңгейдің (Data Link ) бір міндеті тасымалдау ортасына қатынас құруды тексеру болып табылады. Қателерді түзету және іздеп табу тетігін жүзеге асыру арналық деңгейдің басқа бір міндеті. Бұл үшін арналық деңгейде биттер кадрлар (frames) деп аталатын жиынға топтастырылады.

Арналық деңгей деректер дестесінің құрамына кіретін символдарды тізбектелген түрде тасымалдауға арналған. Бұл деңгейде желінің түйіндерінің физикалық деңгейді пайдалану ережелері анықталады. Физикалық деңгейден алынған деректерді желілік деңгейге түсінікті (деректер кадрі деп аталатын) түрге аударады. Және керісінше, желілік деңгейден қабылданған кадрларды физикалық деңгейге керек биттер (ақпарлар) ағынына түрлендіреді. Арналық деңгей екі желілік деңгей арасында тасымалданатын деректердің тұтастығын қадағалап отырады.

Арналық деңгей керек кадрларын жасау, жіберу және қабылдау қызметін атқарады. Бұл деңгей желілік деңгейдің сұранымдарын орындап, дестелерді қабылдау және жіберу үшін физикалық деңгейдің қызметін қолданады. IEEE 802. х ерекшелігі арналы деңгейді екі деңгейшеге бөледі: логикалық арнаны басқару (LLC) және ортаға қатынас жасауды басқару (MAC) . LLC желілік деңгейге қызмет көрсетеді, ал МАС деңгейшесі физикалық ортаға қатынас құруды реттейді.

Екінші деңгейдегі ең көп қолданатын хаттамалар:

# HDLC - тізбектеп жалғау үшін;

# IEEE 802. 2 LLC (I және II тип) 802. x ортасына МАС қамтамасыз

етеді;

# Ethernet # Token ring # FDDI # X. 25 # Frame relay

1. 2 Желілік сызба - құрылымдар

Желінің сызба-құрылымы (topology) деп желінің геометриялық нысанын немесе есептеу машиналарының бір-біріне қарағандағы орналасуын айтады. Желінің сызба-құрылымы желілік тасымалдау ортасының және қосылған құрылғылардың физикалық орналасуын сипаттайды.

Желілік сызба-құрылымның бірнеше түрі бар: құрсым (магистраль, Bus), сақина (Ring), жұлдыз (Star), бұтақ (Tree) және ұяшықты (гибридті) .

“Жұлдыз” сызба-құрылымы

Есептеу желісінің қалған түйіндерінің әрқайсысымен деректер тасымалданатын жеке желі арқылы байланысқан, орталық түйін бар сызба-құрылым мультиплексор, көп портты қайталауыш немесе шоғырлауыш деп атайды. ”Жұлдыз“ сызба-құрылымды желіде басқару толық мұнда ешқандай қақтығыс болуы мүмкін емес. ”Жұлдыздың“ белсенді және бейбелсенді түрі бар. Бірінші түрінде ақпарат айырбастаудың барлығы тек орталық компютер арқылы жүреді. Әдетте, осы орталық компютер ретінде ең қуатты есептеу машинасы тағайындалады және оған айырбастауды басқару міндеті жүктеледі.

Бейбелсенді ”Жұлдыз“ жұлдызға тек сырттай ғана ұқсайды және қазіргі уақытта анағұрлым көп таралған. Ол Ethernet желісінде қолданылады. Осындай желінің орталығында компьютер емес, көп портты қайталауыш немесе шоғырлауыш (Хаб) орналасады. Шоғырлауыш өзінің кез келген портына келіп түскен сигналдарды қалған барлық порттарына жібереді. Осының нәтижесінде түйіндердің біреуінен шыққан сигналдар қалғандарының барлығына жететін болады. Бұзылған түйінді есептеу желісінің құрамынан шығарып тастау мүмкіншілігі осы құрылымның ыңғайлы жағы болып табылады. Бірақ егер орталық түйін бұзылса, онда барлық есептеу желісі жұмыс істеу қабілетін жоғалтады.

«Жұлдыз» сызба-құрылымы барлық қосылу нүктелері бір орынға жиналған (2-сурет) . Бұл желі жұмысын жеңіл бақылауға, кейбір абоненттерді орталықтан жай ғана ажырату арқылы желідегі ақауларды түзетуге, сондай-ақ, желінің маңызды бөліктеріне бөтен адамдардың қол жеткізуіне шек қоюға мүмкіндік береді. Басқа сызба-құрылымдарға қарағанда (әсіресе егер орталық түйін сызба-құрылымның геометриялық орталығында орналаспаған жағдайда) кәбіл шығыны анағұрлым көп болатыны «жұлдыз» сызба-құрылымының кемшілігі болып табылады.

«Жұлдыз» тәрізді сызба-құрылымы бар есептеу желісіне мысал ретінде Fast Ethernet (100Ваsе-TX деп аталатын) жергілікті есептеу желісін келтіруге болады.

2-сурет «Жұлдыз» сызба-құрылымы

1. 3 Деректерді тасымалдау ортасы

Деректерді тасымалдау ортасы деп компьютерлер арасында ақпарат айырбастау жүргізілетін байланыс арналарын атайды. Әрбір компьютерлік желіде деректер тасымалдау ортасы деректерді электрлік немесе электромагниттік сигнал түрінде тасымалдайды. Тасымалдау үшін әртүрлі физикалық орталар қолданылады. Жалпы жағдайда деректер тасымалдау ортасы шектелген (сымды немесе кәбілдік) және шектелмеген (сымсыз) болып екіге бөлінеді.

Деректер тасымалдаудың шектелген ортасының ең көп таралған түрі кәбілдер болып табылады. Желілерде кәбілдердің мынадай негізгі түрлері қолданылады: талшық-оптикалық, коаксиал және есулі қоссым. Есулі қоссымда және коаксиалда сигналдар тасымалдау үшін металл өткізгіш, ал талшық-оптикалық кәбілде - шыныдан немесе пластмассадан жасалған жарықөткізгіш қолданылады.

3-сурет Есулі қоссым

Есулі қоссым - бірге ширатылып екі айырылған өткізгіш. Бұл жұп сыртынан қоршаумен, қосымша айырғыш затпен немесе басқа есулі сыммен қоршалуы мүмкін (3-сурет) . Есулі қоссымның бірнеше түрі болғанымен экрандалмаған (UTP - Unshielded Twisted Pair) және экрандалған (STP - Shielded Twisted Pair) деп аталатын екі түрі бар. Қазіргі өндіріліп жатқан есулі қоссымдардың көбі қоршаусыз болғандықтан олар электромагниттік бөгеуілдер әсеріне шалдыққыш болып келеді. Бірақ есулі қоссымдарды ауыстыру немесе салу жеңіл. Сондықтан мен өз курстық жобамда есулі қос сымды пайдалануды шештім.

Экрандалмаған UTP есулі қоссымдар өткізу қабілетіне қарай бірнеше санатқа бөлінеді. Мәселен: UTP1-телефондық қатынаста қолданылады және деректер тасымалдауға жарамайды; UTP2 - 4 Мбит/с дейінгі жылдамдықпен деректер тасымалдау үшін қолданылады; UTP3 - 10 Мбит/с дейінгі жылдамдықпен деректер тасымалдау үшін қолданылады (мыс., 10Base-T желісінде) ; UTP4 - 16 Мбит/с дейінгі жылдамдықпен деректер тасымалдау үшін қолданылады (мыс., Token Ring желісінде) ; UTP5-100 Мбит/с және одан астам жылдамдықпен деректер тасымалдау үшін қолданылады (мыс., 100Base-TX желісінде) . Экрандалмаған қоссым желінің қауіпсіздігін және сенімділігін арттыруға мүмкіндік береді.

Экрандалмаған қоссым экрандалған түріне қарағанда арзан. Бірақ жоғары жылдамдықты желілерде экрандалмаған қоссымды қолданған кезде бірнеше жайтты ескеру керек болады. Солардың бірі-деректердің қауіпсіздігін қамтамасыз ету мәселесі. Экрандалмаған қоссым қолданылатын желілерде (мәселен, 10Base-T, 100Base-T) осындай кәбіл таратушы антенна рөлін атқара алады. Сондықтан, экрандалмаған қоссымға тікелей жалғанбай-ақ, тек одан біршама қашықтықта қабылдауыш антенна орналастыру арқылы желіден керекті ақпаратты алуға болады. Бұл жағдайда, тыңдаушыға, тек қосымша, радиосигналдарды қабылдағыш, оларды өңдейтін электроника және компьютер қажет. Кейбір мекемелерде қорғауды талап ететін ақпаратты экрандалмаған кәбілмен тасымалдау үшін оларды шартбелгілеу (шифрлау) технологиясы қолданылады. Бұл вариант экрандалған қоссымды пайдаланудан қымбатқа түседі.

1. 4 Деректерді тасымалдау ортасына қатынас құру әдістері

Желіге қатынас құру деп басқа түйіндермен ақпарат алмасу үшін жұмыс бекетінің деректер тасымалдау ортасымен өзара әрекеттестігін айтады. Деректер тасымалдау ортасына қатынас құруды басқару - жұмыс бекеттерінің деректер тасымалдау ортасына қатынас құру тәртібін тағайындау.

Қатынас құру әдісі - келесі кезекте қайсы жұмыс бекеті (немесе компьютер) деректер тасымалдау үшін есептеу желісің пайдалана алатынын анықтайтын тәсіл (ережелер жинағы) . Көп тараған қатынас құру әдістеріне кездейсоқ және детерминалдық әдістер жатады.

Кездейсоқ қатынас құру әдісі

Кездейсоқ қатынас құру әдістерінің тиімділігі деректер тасымалдап бастар алдында осы ортаның жай-күйі туралы мәліметтің бар-жоқтығына байланысты. Кездейсоқ қатынас құру әдістері екі топқа бөлінеді:

CSMA/CD - тасуышты бақылау және қақтығысты іздеп-таба отырып, көптік қатынас құру әдісі

Басқа түйіндер не істеп жатқанын анықтау және одан кейін ғана шешім қабылдау мүмкіндігі жүзеге асырылатын әдіс - CSMA/CD (Carrier Sense Multiple Access with Collision Detection) . Тасымалдауға арналған ақпараты бар түйін деректер тасымалдауды бастаудың алдында арнаның жай-күйін тексереді, бұл операцияны тасуышты бақылау деп атайды да, ол бейімдеуіште орнатылған қарапайым сұлбаның көмегімен жүзеге асырылады. Егер арна бос болса, онда бейімдеуіш дестелерді тасымалдай бастайды; керісінше, болмаса - кездейсоқ уақытты күтеді де, тасымалдау үдерісін қайтадан ұйымдастыруға кіріседі. Тасуышты бақылау операциясын қолдану қақтығыс болу ықтималдығын кемітеді.

Бұл әдіс кезінде бірнеше жұмыс бекеті (көптік қатынас құру) тасымалдау ортасына қатынас құру үшін олар осы ортада тасымалдау үзілісі болғанша оны бақылайды (тасуышты тексеру) . Одан кейін деректер тасымалдана бастайды және онымен қатарласа тасымалдау әрекеттері тексеріледі (қақтығысты табу) . Әрбір жұмыс бекеті (өзінше) желі бос деп санап, хабар тасымалдауға тырысады. Егер қақтығыс бола қалса, онда белгілі бір уақыт өткен соң хабар тасымалдауға қайтадан әрекет жасайды. Бұл қатынас құру әдісі ең көп тараған әдістер қатарына жатады және Fast Ethernet сияқты есептеу желілерінде қолданылады.

Қайталау уақыты: t _қ =L⋅t _қау

t _қау - қос айналым уақыты. Екі бекет арасындағы сигналдардың барып-қайтып келетін уақыты - 5, 12 мкс

L=[0, 2 ^N -1] - мына аралықта жатқан сандар тізбегі.

N - қатынас құруды қайталау нөмірі =16-ға дейін рұқсат берілген

L=[0, 1]

00 - қақтығыс болады;

11 - қақтығыс болады;

01 - қақтығыс болмайды;

10 - қақтығыс болмайды.

1. 5 Желінің құрылымын синтез жасау

1. 5. 1 Жұлдыз тәрізді құрылымның математикалық үлгісі

Жұлдыз тәрізді сызба-құрылымды жергілікті желіде әрбір абоненттік жүйе (АЖ) орталық коммутациялау бекетіне (КБ) қатынас құра алады. Бұл бекет АЖ-нің сұранысын анықтағаннан кейін екі АЖ-ні бір-бірімен байластырады. Жұлдыз тәріздес құрылымды синтездеу келесі түрдегі функционалды минимизациялауға әкеледі:

→min (5. 1)

Бұл кезде төмендегі шектеулер орындалуы тиісті [3] .

1 Әрбір Equation. 3 түйінде АЖ-нің тек бір түрі орналасуы мүмкін:

Equation. 3 (j∈M ⁰ ) (5. 2)

2 Әрбір пайдаланушы тек қана бір АЖ-не бекітіледі:

Equation. 3 (i ≠j, j∈M ⁰ ) (5. 3)

3 АЖ-нің өнімділігі бір уақыт өлшемінде келіп түсетін сұраныстардың барлық түрін өңдеуді қамтамасыз етуге жеткілікті болуы керек

Equation. 3 (j∈M ⁰ ) (5. 4)

және

, (j≠k, ⊂ ) (5. 5)

(5. 6)

(5. 7)

Мұнда ⊂ - КБ орнатылуы мүмкін түйіндердің іш жиынтығы; V _l - КБ-нің l түрінің өткізу қабілеті; L - КБ орнату нұсқасының жиынтығы; C _jk - бір уақыт өлшемінде j-ші АЖ-ден k-ші КБ арқылы ақпарат тасымалдаудың келтірілген шығындары. (5. 5) шектеу КБ орналастыруға мүмкін болатын түйіндердің берілген жиынтығында барлық АЖ-мен байланысқан тек бір ғана КБ ұйымдастыру болатынын білдіреді. (5. 7) шектеуде КБ және байланыс арнасының өткізу қабілетіне қойылатын талаптар ескеріледі. Бұл кезде байланыс арнасының өткізу қабілеті КБ-нің барынша көп жүктемеленуін толық қамсыздандырады деп есептелінеді.

1. 5. 2 Cинтез жасау, медиана іздеу әдісі

Жұлдыз тәрізді желілерде әрбір абоненттік жүйе (АЖ) деректер тасымалдаудың жекеше ортасы арқылы коммутациялау бекетімен (КБ) қосылады. Әрбір уақыт ішінде КБ тек бір АЖ сұранысына ғана қызмет көрсетеді. Сондықтан бұндай ЖЕТ шапшаңдылығы ең алдымен КБ-нің өткізу қабілеттілігімен анықталады.

Мұндай есепті шешудің бір амалы - медианасын іздеу әдісі. Медианасы деп өзінің орналасқан жерінен бастап қалған барлық төбелеріне дейінгі ең қысқа арақашықтықтардың қосындысы ең аз болатын графтың төбесін атайды. Әрбір төбе үшін беріліс сандары деп аталатын екі санды анықтайық:

мұнда төбесінен төбесіне дейінгі ең қысқа аралық, нақты жағдайда . және сандары сәйкесінше төбесінің сыртқы және ішкі беріліс сандары деп аталады. төбесі G графының сыртқы медианасы деп аталады, егер мына келесі өрнек орындалса:

(5. 1)

Ал ( ) төбесі G-графының ішкі медианасы деп аталады, егер мына келесі өрнек орындалса:

(5. 2)

Егер G графы шығындар матрицасы симметриялы болса, яғни бір сол байланыс арналары арқылы деректер жіберу және қабылдау жүзеге асырылатын болса (мысалы, ЖЕТ-ғы сияқты), онда . Сонымен, КБ-ны орналастыру түйіні ретінде сыртқы-ішкі медианасы болып табылатын төбесін алуға болады.

КБ орнату вариантын оны құру кезіндегі шығын аз болатындай және мына шарт орындалатындай етіп тандау керек:

(5. 3)

мұнда w _j(r) - j-ші түйінде орналасқан КБ-ның r-ші вариантының өткізу қабілеті.

1-ші адым. КБ орнату варианттарын құрудағы барлық шығындарды
өсуі бойынша реттеу: С ₁ < С ₂ < . . . < C _r < . . . < С _n

2-ші адым. КБ-ды құруға кететін шығындардың өсуі ретінде оларды орнату варианттарын шарты орындалғанша қарап шығу.

3-ші адым. Егер (5. 3) шарты орындалса, онда j-ші КБ-ға w _j(r) өнімділікті r-ші техникалық құралдар тағайындалады. Егер шарты орындалмаса, ондау j=j+1 амалын орындаған соң 1-ші адымға өту.

4-ші адым. Егер j m болса, онда 5-ші адымға өту. Әйтпесе j=j+1 амалын орындағаннан кейін 1-ші адымға көшу.

5-ші адым. Сыртқы немесе ішкі беріліс сандарын есептеу.

6-шы адым. (5. 1) және (5. 2) өрнектері арқылы графтың сыртқы-ішкі медианасын анықтау. Алгоритмнің соңы.

Егер шығындар матрицасының симметриялы екенін ескерсек, сондай-ақ барлық j үшін деп қабылдасақ, онда

Онда КБ орналастыру түйінін іздеу элементтерінің ең аз қосындысы бар бағанды (немесе қатарды) табуға әкеледі. Жоба бойынша медиананы іздеу әдісі ҚОСЫМША Д көрсетілген.

Синтез жасау әдісі: медиананы іздеу әдісі болып табылады. Осы әдістің негізгі мақсаты: желінің оңтайлы құрылымын табу мәселесін шешу. Сол арқылы біз шоғырлауыштың орналасу орнын анықтаймыз.

1. 6 Хаттамалар және стандарттар

... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.