Желілік тор құрылғыларындағы OrderOne маршрулдау протоколы: мыңдаған түйіндерді қолдайды, тиімді жолмен хабар алмасуды қамтамасыз етеді. Төмен шығындар!
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Торлы желілерді анықтау және маршруттау протоколы
Mesh network discovery and routing protocol
OrderOne MANET маршруттау протоколы – бұл цифрлық радио арқылы торлы желіде байланыс жасайтын компьютерлердің бір-бірін табуы және тиімді жолмен хабар алмасуы үшін жасалған алгоритм. Ол сымсыз торлы желілермен жұмыс істеу үшін әзірленген және ұсынылған. OON-ның жасаушылары оның мыңдаған түйінді қабылдай алатынын, ал көптеген басқа протоколдар жүзден аз түйінді ғана қолдай алатынын айтады. OON маршруттау үшін қажетті хабарламалардың жалпы көлемін азайту мақсатында иерархиялық алгоритмдерді пайдаланады. Маршруттау жүктемесі кез келген желіде түйінен түйінге берілетін жолақтың 1%-дан 5%-ына дейін шектеледі және желінің мөлшері артқан сайын өспейді. Негізгі идея – желінің өздігінен ағаш тәрізді құрылымға ұйымдасуы. Түйіндер ағаш түбірінде бастапқы маршрутты белгілеу үшін жиналады. Содан кейін маршрут бұрыштарды қысқарту арқылы түбірден алыстайды, бұл құмырсқалардың іздеріне ұқсас. Қысқартуға болатын бұрыштар қалмағанда, жақын дағдылы маршрут пайда болады. Бұл маршрут үнемі жаңартылып отырады. Әрбір процесс минималды жергілікті байланыс арқылы және өте кішкентай маршрутизатор кестелерімен орындалуы мүмкін. OORP шамамен 200 КБ жадты қажет етеді. 500 түйіндік, 200 байт/секунд жылдамдықпен хабар жіберетін модельдік желі шамамен 20 секунд ішінде өздігінен ұйымдасты. 2004 жылдан бастап OORP патенттелген немесе басқа да маңызды зияткерлік меншік құқықтарымен қорғалған. Төмендегі сілтемеге қараңыз.
The OrderOne MANET Routing Protocol is an algorithm for computers communicating by digital radio in a mesh network to find each other, and send messages to each other along a reasonably efficient path. It was designed for, and promoted as working with wireless mesh networks. OON's designers say it can handle thousands of nodes, where most other protocols handle less than a hundred. OON uses hierarchical algorithms to minimize the total amount of transmissions needed for routing. Routing overhead is limited to between 1% and 5% of node to node bandwidth in any network and does not grow as the network size grows. The basic idea is that a network organizes itself into a tree. Nodes meet at the root of the tree to establish an initial route. The route then moves away from the root by cutting corners, as ant trails do. When there are no more corners to cut, a nearly optimum route exists. This route is continuously maintained. Each process can be performed with localized minimal communication, and very small router tables. OORP requires about 200K of memory. A simulated network with 500 nodes transmitting at 200 bytes/second organized itself in about 20 seconds. As of 2004, OORP was patented or had other significant intellectual property restrictions. See the link below.
Қорытындылар
Әрбір компьютер, немесе желінің "түйіні" бірегей атауға, кем дегенде бір желілік байланысқа және көршілер тізімін сақтау мүмкіндігіне ие компьютерге ие.
Each computer, or "node" of the network has a unique name, at least one network link, and a computer with some capacity to hold a list of neighbors.
Ағаштарды ұйымдастыру
Желі түйіндері әр түйін ата-ана таңдап, иерархия құрайды. Ата-ана – бұл көрші түйін, ол көптеген басқа түйіндерге ең жақсы келесі қадам болып табылады. Бұл әдіс желінің топологиялық орталығына жақын, сыйымдылығы жоғары және тұрақтырақ болатын түйіндердің айналасында иерархия жасайды. Кішкентай түйіннің жад шектеулері оның кішкентай маршрутталмалық кестесінде көрінеді, бұл оны басым орталық түйін болудан автоматты түрде сақтайды. Жоғары деңгейде бір немесе екі түйін өзінен жақсырақ байланысқан түйіндерді таба алмайды және осылай бүкіл желіге ата-ана болады. Иерархия құру алгоритміне күрделі маршруттау алгоритмі немесе көп көлемдегі байланыс қажет емес.
The network nodes form a hierarchy by having each node select a parent. The parent is a neighbor node that is the next best step to the most other nodes. This method creates a hierarchy around nodes that are more likely to be present, and which have more capacity, and which are closer to the topological center of the network. The memory limitations of a small node are reflected in its small routing table, which automatically prevents it from being a preferred central node. At the top, one or two nodes are unable to find nodes better connected than themselves, and therefore become parents of the entire network. The hierarchy formation algorithm does not need a complex routing algorithm or large amounts of communication.
Жолдау
Барлық түйіндер ағаш түбіріне дейін өздеріне қарай маршрут жібереді. Сондықтан, қосылыс қажет болған түйін ағаш түбіріне сұраныс жіберіп, әрқашан маршрут таба алады. Коммерциялық протокол Dijkstra алгоритмін пайдаланып, маршрутты үздіксіз оңтайландырып, жаңартып отырады. Желі қозғалғанда немесе өзгергенде, маршрут үнемі түзетіліп отырады.
All nodes push a route to themselves to the root of the tree. A node wanting a connection can therefore push a request to the root of the tree, and always find a route. The commercial protocol uses Dijkstra's algorithm to continuously optimize and maintain the route. As the network moves and changes, the path is continually adjusted.
Артықшылықтар
Желідегі кейбір түйіндердің желідегі барлық түйіндерді білуге жеткілікті жадысы болған жағдайда, желінің мөлшеріне ешқандай нақты шектеу жоқ. Басқару жолағының ені желінің мөлшеріне қарамастан 5%-дан кем деп белгіленгендіктен, желінің мөлшері өскен сайын қажетті басқару жолағының ені арта қоймауы керек. Жүйе аз жадысы бар түйіндерді де пайдалана алады. Желіде түйіннің желіде жоқ екенін анықтаудың сенімді және аз шығынды жолы бар. Бұл, әсіресе, желілік тораптарда маңызды және құнды қасиет. Көптеген маршруттау протоколдары проактивті байланыс күйі туралы ақпаратты азайту арқылы немесе қосылу талаптарына жауап ретінде маршруттауды реактивті түрде жүзеге асыру арқылы кеңейеді. OORP проактивті және реактивті әдістерді біріктіреді. Дұрыс конфигурацияланған OORP желісі 100 000 түйінге дейін кеңейтілуі мүмкін және маршруттау жолағының ені 5%-қа дейін шектелгеніне қарамастан, көбінесе жақсы өнімділікке қол жеткізе алады.
Assuming that some nodes in the network have enough memory to know of all nodes in the network, there is no practical limitation to network size. Since the control bandwidth is defined to be less than 5% regardless of network size, the amount of control bandwidth required is not supposed to increase as network size grows. The system can use nodes with small amounts of memory. The network has a reliable, low overhead way to establish that a node is not in the network. This is a difficult, valuable property in ad hoc mesh networks. Most routing protocols scale either by reducing proactive link state routing information or reactively driving routing by connection requests. OORP mixes the proactive and reactive methods. Properly configured, an OORP net can scale to 100,000's of nodes and can often achieve reasonable performance even though it limits routing bandwidth to 5%.
Сын-пікірлер
Орталық түйіндер қосымша жүктемеге ие, себебі олар желідегі барлық түйіндер туралы ақпаратты сақтау үшін жеткілікті жадқа ие болуы керек. Түйіндер саны артқан сайын желі масштабталудан тоқтауы мүмкін. Егер желідегі барлық түйіндер төмен сыйымдылықтағы түйіндер болса, желі өзгерістерге шыдамай қалуы мүмкін. Бұл желінің максималды масштабын шектеуі мүмкін. Дегенмен, нақты әлемдегі желілердің көпшілігінде шеткі түйіндерден алшақтаған сайын өткізу қабілеті артады. Бұл сын-қатерлердің ешқандай практикалық әсері болмауы да мүмкін. Мысалы, 9,6 Кбит/с өткізу қабілеті бар радионы қарастырайық. Егер протокол 5 секунд сайын 180 байттан тұратын бір пакет жіберуге конфигурацияланса, ол желінің жалпы өткізу қабілетінің 3% -ын пайдаланады. OON үшін жасалған қоғамдық ұсыныстарда қауіпсіздік немесе аутентификация қарастырылмаған. Қауіпсіздік пен аутентификацияны протоколды интеграциялаушы ұйым қамтамасыз етуі мүмкін. Типик қауіпсіздік шараларына шифрлау, пакеттерге қол қою және қайта ойнату шабуылдарын болдырмау үшін санауларды арттыру кіреді.
Central nodes have an extra burden because they need to have enough memory to store information about all nodes in the network. At some number of nodes, the network will therefore cease to scale. If all the nodes in the network are low capacity nodes the network may be overwhelmed with change. This may limit the maximum scale. However, In virtually all real world networks, the farther away from the edge nodes the more the bandwidth grows. These critiques may have no practical effect. For example, consider a low bandwidth 9.6 Kbit/second radio. If the protocol was configured to send one packet of 180 bytes every 5 seconds, it would consume 3% of overall network bandwidth. Public proposals for OON do not include security or authentication. Security and authentication may provided by the Integrator of the protocol. Typical security measures include encryption or signing or the protocol packets and incrementing counters to prevent replay attacks.