[go: up one dir, main page]

KR20030059259A - 효율적인 경로 코스트 집합 도출 방법 및 장치 - Google Patents

효율적인 경로 코스트 집합 도출 방법 및 장치 Download PDF

Info

Publication number
KR20030059259A
KR20030059259A KR10-2003-7006652A KR20037006652A KR20030059259A KR 20030059259 A KR20030059259 A KR 20030059259A KR 20037006652 A KR20037006652 A KR 20037006652A KR 20030059259 A KR20030059259 A KR 20030059259A
Authority
KR
South Korea
Prior art keywords
cost
path
node
data set
costs
Prior art date
Application number
KR10-2003-7006652A
Other languages
English (en)
Other versions
KR100544008B1 (ko
Inventor
다니엘 바우어
존 데이글
일리어스 일리아디스
파올로 스코튼
Original Assignee
인터내셔널 비지네스 머신즈 코포레이션
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 인터내셔널 비지네스 머신즈 코포레이션 filed Critical 인터내셔널 비지네스 머신즈 코포레이션
Publication of KR20030059259A publication Critical patent/KR20030059259A/ko
Application granted granted Critical
Publication of KR100544008B1 publication Critical patent/KR100544008B1/ko
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
    • H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
    • H04Q11/0478—Provisions for broadband connections
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H04L45/124—Shortest path evaluation using a combination of metrics

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

본 발명은, 데이터 통신 네트워크 내에 소스 노드와 복수의 데스티네이션 노드를 포함하는 노드 그룹에 대한 효율적인 경로 코스트 집합을 도출하는 방법에 관한 것으로서, 상기 그룹 내의 노드들 사이의 경로에 대한 경로 코스트는 네트워크 내에서 규정되고, 각각의 경로 코스트는 제한적인 코스트 및 부가적인 코스트를 포함하며, 상기 방법은 우선적으로 보다 높은 대역폭의 경로를 반복적으로 식별하는 단계와, 동등한 대역폭의 경로가 둘 이상 있는 경우에 보다 낮은 전송 지연을 갖는 경로를 선택하는 단계를 포함한다.

Description

효율적인 경로 코스트 집합 도출 방법 및 장치{COSTS IN DATA NETWORKS}
본 발명은 데이터 통신 네트워크에서의 코스트에 관한 것으로, 특히 데이터 통신 네트워크의 노드들의 그룹에 대한 일군의 유효 경로 코스트를 도출하기 위한 방법, 장치 및 컴퓨터 프로그램 요소에 관한 것이다.
인터넷과 같은 대규모 네트워크 내의 서비스 품질(QoS)의 지원은 이종의 애플리케이션에 대해 아주 중요해지고 있다. QoS를 보장하기 위해, 엔드 유저를 접속하는 경로들은 주어진 요건들을 만족시켜야 한다. 따라서, 라우팅 프로토콜은 네트워크에서 다양한 링크들에 의해 지원된 트래픽 특성들을 알아야 한다.
OSPF(개방 최단 경로 : Open Shortest Path First)와 같은 공지되어 있는 라우팅 프로토콜에 대해 QoS 확장이 제안되었다. 그러한 확장들의 예는, 1999년 3월 뉴욕 IEEE INFOCOM'99의 회보 제75-83페이지, Apostolopoulos 등의 "Implementation and Performance Measurements of QoS Routing Extensions to OSPF"에 개시되어 있다. OSPF 프로토콜은 링크 상태 라우팅 프로토콜의 일례이다. 이러한 프로토콜은 대규모 네트워크에서 효과적으로 동작하지 않는다는 것은 잘 알고 있을 것이다. 따라서, 스케일러빌러티(scalability)를 위해, OSPF 네트워크는 몇 개의 라우팅 영역으로 분할된다. OSPF 프로토콜은, 1998년 4월 IETF(Internet Engineering Task Force)에서 발표한 RFC(Request for Comments) 사양인 Moy의"OSPF Version 2"에 상세히 기술되어 있다.
종래 기술 분야에서 공지되어 있는 다른 유사한 라우팅 프로토콜로는, 1996년 3월 ATM 포럼에서의 "Private Network to Network Interface Specification Version 1.0"에 개시된 PNNI(Private Network to Network Interface)가 있다. PNNI 프로토콜에 따르면, 네트워크는 여러 개의 클러스터로 분할되어 라우팅 계층을 형성한다.
전체적으로 정확한 경로 선택을 제공하기 위해, OSPF 영역 또는 PNNI 클러스터인 포함된 각 라우팅 도메인의 횡단(traversing) 특성이 고려되어야 한다. 2000년 3월 이스라엘 텔 아비브(Tel Aviv)에서의 IEEE INFOCOM'2000의 회보의 Hao 등의 "On Scalable QoS Routing, Performance Evaluation of Topology Aggregation" 및 2000년 3월 이스라엘 텔 아비브(Tel Aviv)에서의 IEEE INFOCOM'99의 회보의 128-136 페이지, Orda 등의 "QoS Routing, a Precomputation Perspective"는 모두, 네트워크의 계층적 조직을 통해 경로 계산 효율에 있어서의 큰 이득이 얻어질 수 있음을 암시한다.
도메인의 각각의 입구-출구(ingress-egress) 노드 쌍에 대한 경로 코스트를 제공하는 변환 매트릭스(transition matrix)에 의해 라우팅 도메인의 횡단 특성을 나타내는 방법이, 1999년, 5월, 일본 코치(Kochi)에서의 IEEE ATM Workshop'99의 회보의, Iliadis 등의 "Transition Matrix Generation for Complex Node Representation"에 개시되어 있다. 변환 매트릭스에서 각각의 성분(entry)은 대응하는 입구-출구 노드 쌍의 횡단 특성을 나타내는 최소 표시이다. 횡단 특성은 제한적인(restrictive) 코스트 메트릭스(metrics), 부가적인(additive) 코스트 메트릭스 또는 이들 둘에 의해 기술될 수 있다. 단지 하나의 메트릭스에 의해 기술된 변환 특성은 1차원으로 간주될 수 있다. N 개의 메트릭스로 기술된 변환 특성은 N 차원으로 간주될 수 있다. 경로의 부가적인 메트릭스는 경로 내의 모든 링크의 모든 부가적인 메트릭스의 합이다. 경로의 제한적인 메트릭스는 그 경로에서의 모든 링크들의 각각의 제한적인 메트릭스의 최소치이다. 부가적인 메트릭스의 예들은 지연 및 관리 코스트를 포함한다. 제한적인 메트릭스의 예는 대역폭을 포함한다. 횡단 특성의 최소 표시는 종래 기술에서 효율적 프론티어(efficient frontier)로 지칭되어 왔다. 효율적 프론티어를 계산하는 종래의 기법을 간단히 설명한다. 다음과 같은 두 가지 표준에 따라서 이들 기법을 분류하는 것이 가능하다. 즉,
·계산 결과 : 일부 기법들은 하나의 소스 입구-출구 노드로부터 네트워크 내의 다른 모든 입구-출구 노드까지 효율적 프론티어를 계산한다. 다른 기법들은 모든 입구-출구 노드 쌍 사이의 효율적 프론티어를 계산한다. 전자의 범주에 속하는 기법들은 모든 입구-출구 노드에 적용되어야 한다는 것을 알 수 있을 것이다.
·지연 함수 : 일부 기법들은 단지 고정된 지연 함수만을 지원한다. 다른 기법들은 고정된 지연 및 대역폭 의존 지연에 적용될 수 있다.
다음의 세 개의 공지되어 있는 알고리즘은 최소 표시를 계산하기 위해 이용될 수도 있다.
·2000년 7월 뉴올리언스주에서의 IEEE ICC'00의 회보 1353-59 페이지의 Bauer 등의 "Efficient Frontier Formulation for Additive and RestrictiveMetrics in Hierarchical Routing"에 개시된 멀티 다익스트라(Multi-Dijkstra) 알고리즘.
·1989년 MIT에서 발행한 MIT 전기 공학 및 컴퓨터 사이언스 시리즈(MIT Electrical Engineering and Computer Science Series), ISBN 제 0-62-031412-8호의 Cormen 등의 "Introduction to Algorithms"와, 1958년 Quarterly of Applied Mathematics 제 16권 제 1장 87-90페이지의 Bellman의 "On a Routing Problem"과, 1962년 프린스턴 대학 회보(Princeton University Press)의 Ford Jr. 등의 "Flows in Networks"에 개시된 벨만-포드(Bellman-Ford) 알고리즘.
·1965년 Communications of the ACM 제 5권 제 6장의 Floyd의 "Algorithm 97(Shortest Path)"에 개시된 플로이드 와샬(Floyd-Warshall) 알고리즘.
이들 세 개의 알고리즘 모두 일정한 지연에 적용할 수 있다. 그러나, 단지 벨만 포드 및 플로이드 와샬 알고리즘만이 대역폭 의존 지연을 처리할 수 있다. 또한, 멀티 다익스트라 및 벨만 포드 알고리즘만이 모든 노드에 대한 하나의 소스에 있어서의 효율적 프론티어 문제를 해결할 수 있다. 멀티 다익스트라 및 플로이드 와샬 알고리즘은 일반적으로 효율적 프론티어를 계산하는데 있어서 벨만 포드 알고리즘보다 덜 복잡하다. 따라서 이들 알고리즘들 사이의 선택은 애플리케이션에 기초한다. 예를 들면, 단지 몇 개의 입구-출구 버텍스(vertex) 및 고려될 일정한 지연만이 있으면, 멀티 다익스트라 알고리즘이 플로이드 와샬 알고리즘보다 바람직하다.
일반적으로, 라우팅 도메인의 하나의 노드로부터 다른 모든 노드들로의 효율적 프론티어를 계산하는 종래의 기술은 계산이 복잡하고 응용에 제한이 있다. 그러한 효율적 프론티어를 계산하는 보다 간단한 방법을 제공하는 것이 바람직하다. 또한, "모든 노드들에 대한 하나의 소스(One source to all nodes)" 문제를 해결하기 위한 방법을 제공하는 것이 바람직할 것이다.
본 발명에 따르면, 데이터 통신 네트워크에서 소스 노드와 복수의 데스티네이션 노드를 포함하는 노드 그룹에 대한 효율적인 경로 코스트 집합을 도출하는 방법이 제공되는데, 여기서, 상기 그룹 내의 노드들 사이의 경로들에 대한 경로 코스트는 네트워크 내에서 규정되며 각각의 경로 코스트는 제한적인 코스트 및 부가적인 코스트를 포함하며, 상기 방법은
a) 제 1 데이터 집합 내에, 상기 소스 노드로부터 임의의 상기 데스티네이션 노드로의 직접 경로에 대한 상기 경로 코스트를 기록하는 단계 -각각의 기록된 코스트는 상기 제 1 데이터 집합 내에서 상기 대응하는 경로에 의해 도달된 상기 노드와 관련됨- 와,
b) 상기 제 1 데이터 집합으로부터 최상의 경로 코스트 -상기 최상의 경로 코스트는 최상의 제한적인 코스트를 포함하도록 결정되며, 복수의 상기 경로 코스트가 동등한 제한적인 코스트를 포함하는 경우에는 경로 코스트가 상기 최상의 제한적인 코스트와 최상의 부가적인 코스트를 포함하도록 결정됨- 를 선택하는 단계와,
c) 제 2 데이터 집합 내에 단계 b)에서 선택된 상기 최상의 경로 코스트를 기록하는 단계 -상기 기록된 코스트는 상기 제 2 데이터 집합 내에서 상기 대응 경로에 의해 도달된 상기 노드와 관련됨- 와,
d) 상기 제 2 데이터 집합 내의 단계 c)에서 기록된 상기 코스트를 상기 제 1 데이터 집합으로부터 제거하는 단계와,
e) 상기 제 1 데이터 집합 내에, 단계 c)에 기록된 상기 코스트에 대응하는 상기 경로에 의해 도달된 상기 데스티네이션 노드로부터 상기 그룹 내의 임의의 다른 노드로의 직접 경로에 대한 누적 경로 코스트를 기록하는 단계 -각각의 기록된 누적 경로 코스트는 상기 제 1 데이터 집합 내에서 상기 대응 경로에 의해 도달된 상기 노드와 관련됨- 와,
f) 단계 e)에서 제 1 데이터 집합 내에 관련 코스트가 기록되어 있는 각각의 노드에 대하여, 상기 제 1 및 제 2 데이터 집합 내의 상기 노드와 관련된 상기 코스트들을 비교하고, 그 노드에 도달하기 위한 임의의 다른 그러한 코스트보다 양호하지 못한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트, 또는 그 노드에 도달하기 위한 임의의 다른 그러한 코스트와 동등한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트를 상기 제 1 데이터 집합으로부터 제거하는 단계와,
g) 단계 f) 후에 상기 제 1 데이터 집합 내에 남아 있는 코스트가 없을 때까지 단계 b) 내지 f)를 반복하는 단계를 포함하며,
이들 단계에 의해, 그 결과의 제 2 데이터 집합은 효율적인 코스트 집합을 포함한다.
이것은 효율적 프론티어를 계산하는데 있어서 훨씬 간단하고 빠른 방법을 제공한다. 또한, "모든 노드들에 대한 하나의 소스(One source to all nodes)" 문제의 해결을 편리하게 한다. 또한, 상기 방법은 일정한 지연 및 대역폭 의존 지연 모두에 적용가능한다.
각각의 제한적인 코스트는 대응 경로의 대역폭을 나타내는 값을 포함하고, 최상의 제한적인 코스트는 최대 대역폭을 나타내는 코스트이다. 각각의 부가적인 코스트는 대응 경로와 관련된 전송 지연을 나타내는 값을 포함하고, 최상의 부가적인 코스트는 최소 전송 지연을 나타내는 코스트이다. 상기 경로들 중 적어도 하나는 복수의 링크와 적어도 하나의 중간 노드를 포함한다.
본 발명은 또한, 데이터 처리 시스템의 프로세서에 로딩될 때, 상기 프로세서가 전술한 바와 같은 효율적인 경로 코스트 집합을 도출하는 방법을 수행하도록 구성된 컴퓨터 프로그램 코드 수단을 포함하는 컴퓨터 프로그램 요소로 확장된다.
다른 측면으로부터 본 발명은 고찰하면, 데이터 통신 네트워크 내에 소스 노드와 복수의 데스티네이션 노드를 포함하는 노드들의 그룹에 대한 효율적인 경로 코스트 집합을 도출하기 위한 장치에 있어서,
상기 그룹 내의 노드들 사이의 경로들에 대한 상기 경로 코스트들은 상기 네트워크 내에서 규정되고 각각의 경로 코스트는 제한적인 코스트 및 부가적인 코스트를 포함하고, 상기 장치는 경로 코스트들로 이루어진 제 1 및 제 2 데이터 집합 및 제어 로직을 저장하기 위한 메모리를 포함하고, 상기 제어 로직은
a) 상기 제 1 데이터 집합 내에, 상기 소스 노드로부터 임의의 상기 데스티네이션 노드로의 직접 경로에 대한 상기 경로 코스트를 기록하고 -각각의 기록된 코스트는 상기 제 1 데이터 집합 내에서 상기 대응하는 경로에 의해 도달된 상기 노드와 관련됨-,
b) 상기 제 1 데이터 집합으로부터 최상의 경로 코스트 -상기 최상의 경로 코스트는 최상의 제한적인 코스트를 포함하도록 결정되며, 복수의 상기 경로 코스트가 동등한 제한적인 코스트를 포함하는 경우에는 경로 코스트가 상기 최상의 제한적인 코스트와 최상의 부가적인 코스트를 포함하도록 결정됨- 를 선택하고,
c) 상기 제 2 데이터 집합 내에, 단계 b)에서 선택된 상기 최상의 경로 코스트를 기록하고 -상기 기록된 코스트는 상기 제 2 데이터 집합 내에서 상기 대응 경로에 의해 도달된 상기 노드와 관련됨-,
d) 상기 제 2 데이터 집합 내의 단계 c)에서 기록된 상기 코스트를 상기 제 1 데이터 집합으로부터 제거하고,
e) 상기 제 1 데이터 집합 내에, 단계 c)에 기록된 상기 코스트에 대응하는 상기 경로에 의해 도달된 상기 데스티네이션 노드로부터 상기 그룹 내의 임의의 다른 노드로의 직접 경로에 대한 누적 경로 코스트를 기록하고 -각각의 기록된 누적 경로 코스트는 상기 제 1 데이터 집합 내에서 상기 대응 경로에 의해 도달된 상기 노드와 관련됨-,
f) 단계 e)에서 제 1 데이터 집합 내에 관련 코스트가 기록되어 있는 각각의 노드에 대하여, 상기 제 1 및 제 2 데이터 집합 내의 상기 노드와 관련된 상기 코스트들을 비교하고, 그 노드에 도달하기 위한 임의의 다른 그러한 코스트보다 양호하지 못한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트, 또는 그 노드에 도달하기 위한 임의의 다른 그러한 코스트와 동등한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트를 상기 제 1 데이터 집합으로부터 제거하고,
g) 단계 f) 후에 상기 제 1 데이터 집합 내에 남아 있는 코스트가 없을 때까지 단계 b) 내지 f)를 반복하도록 구성되며,
이에 따라, 그 결과의 상기 제 2 데이터 집합은 효율적인 코스트 집합을 포함하는 효율적인 경로 코스트 집합 도출 장치가 제공된다.
본 발명은 데이터 통신 네트워크의 경로에 각각 접속하기 위한 복수의 포트와, 상기 경로에 결합된 전술한 바와 같은 효율적인 경로 코스트 집합을 도출하기 위한 장치를 포함하는 데이터 네트워킹 장치로 확장된다. 본 발명은 또한 복수의 경로에 의해 상호접속된 복수의 노드를 포함하되, 상기 노드들 중 적어도 하나는 전술한 바와 같은 데이터 네트워킹 장치를 포함하는 데이터 네트워크로 확장된다.
이하에서는 첨부한 도면을 예로서 참조하여 본 발명의 바람직한 실시예를 설명한다.
도면의 간단한 설명
도 1은 일정한 지연 경로에 대한 효율적인 프론티어의 일례를 도시한 그래프.
도 2a는 네 개의 입구-출구 노드를 갖는 네트워크의 일례를 간략하게 도시한 도면.
도 2b는 클러스터 네트워크에 대응하는 변환 매트릭스의 도표도.
도 3 내지 도 13은 네트워크에 대응하는 유향(directed) 그래프.
도 14는 네트워크의 노드 0으로부터 노드 1로의 효율적 프론티어를 도시한 그래프.
도 15는 네트워크의 노드 0으로부터 노드 2로의 효율적 프론티어를 도시한 그래프.
도 16은 네트워크의 노드 0으로부터 노드 3으로의 효율적 프론티어를 도시한 그래프.
도 17은 본 발명에 따른 효율적 경로 코스트 집합을 도출하기 위한 방법의 일례에 대응하는 흐름도.
도 18은 본 발명을 실시하는 데이터 네트워킹 장치의 블록도.
상세한 설명에 앞서, 관련 용어 및 표현을 정의하고 설명한다.
본원 명세서에서 사용된 "제한적인 코스트(restrictive cost)"라는 표현은 예를 들어 대역폭과 같은 링크의 차원 또는 특성의 함수로서 코스트를 설명하는데 사용된다. 제한적인 코스트 C는, 예를 들면, C=Max-대역폭 또는 C=1/대역폭으로 정의될 수 있다. 제한적인 코스트의 정의에 따르면, 경로의 가장 약한 링크가 코스트를 규정한다. 제한적인 코스트의 반대는 부가적인 코스트(additive cost)이다. 부가적인 코스트는, 예를 들면, 링크들의 지연에 달려있다.
본원 명세서에 사용된 "노드" 또는 "버텍스(vertex)"라는 용어는 라우터, 스위치, 브리지, 브라우터(brouter), 허브, 및 통신 네트워크에서 정보를 송수신하는 기타 데이터 네트워킹 장치에 있어서의 일반적인 용어이다.
네트워크는 유향 그래프로 나타낼 수 있다. 다음의 규정이 이용된다.
·네트워크의 노드는 그래프의 버텍스(vertex)로 지칭된다.
·두 네트워크 사이의 링크는 그래프의 두 버텍스 사이의 에지 또는 직접 경로로 지칭된다.
G(V, E)를 주어진 시점에서 네트워크를 나타내는 유향 그래프라고 하자. V는 버텍스의 집합이고, E는 유향 에지의 집합이다. 따라서, 모든 νi, νj∈V에 대하여, 만약 νi및 νj가 접속되어 있으면, 에지가 존재한다. 버텍스들은 다수의 병렬 에지에 의해 접속될 수도 있다. 두 개의 벡터 νi및 νj를 접속시키는 에지 집합은로 표시된다. 표시는 버텍스 νi및 νj를 접속시키는 임의의 에지를 가리킨다.
s와 t를 그래프 G(V, E)의 두 개의 버텍스라고 하자. Ps,t를, s를 t에 접속시키는 경로라고 하자. 만약 s로부터 t로의 경로가 존재하지 않는다면,이다. 길이 ∥ρ∥=n의 경로 ρ∈Ps,t는 n 개의 에지의이며 따라서 다음의 관계가 성립한다.
ν0=s
νn=t
ν= νi또는 ν=νi+1인 에지가 존재하면, 버텍스 ν는 경로 ρ의 일부이다.
경로들 및 에지들에 대한 메트릭스는 네트워크 내의 가용 자원에 대한 정보를 제공한다. 다음은 가용 대역폭에 대한 메트릭스 및 전송 지연을 규정한다. 그러나, 본원 명세서에 제시된 관측치들은 본원 명세서에서 제공된 정의에 알맞는 임의의 제한적인 메트릭 및 부가적인 메트릭에 적용 가능하다는 것을 알 수 있을 것이다.
에지에 대하여, 가용 대역폭은으로 표시된다. 경로의 가용 대역폭은 그 경로가 통과하는 에지들의 가용 대역폭의 최소치이므로, 가용 대역폭은 제한적이다. 길이 n, ρ∈Ps,t인 s로부터 t까지의 적절한 경로 ρ에 대하여, 가용 대역폭은 다음과 같다.
(1)
에지의 전송 지연이 요청된 대역폭 b의 함수라고 가정한다. 따라서, 에지 ε∈E이고 요청된 대역폭이 b일 때, 전송 지연은으로 주어진다. 만약, b＞B(ε)이면, D(ε,b)=∞이다. 경로의 전송 지연은 횡단된 에지들의 전송 지연들의 합이기 때문에, 전송 지연은 부가된다. 길이 n, ρ∈Ps,t의 s로부터 t까지의 적절한 경로 ρ에 대하여, 전송 지연은 다음과 같다.
(2)
에지 ε∈ρ에 대하여, 요청된 대역폭이 b＞B(ε)이면, D(ρ,b)=∞이다. 그렇지 않으면, D(ρ,b)는 유한하다.
아래에서는, 입구-출구 버텍스 쌍에 대한 2차원 변환 특성이 정의된다. 변환 특성의 차원은 대역폭과 지연이다. 다음은 입구 출구 버텍스 집합에 대한 확장을 검토한다. 라우팅 도메인을 나타내는 전술한 그래프 G(V,E)를 고려한다. s,t∈V 가 두 개의 입구-출구 버텍스라고 하자. 라우팅 결정을 위한 s로부터 t까지의 횡단 메트릭스(traversing metrics)는 최대 가용 대역폭인 Bmax및 요청된 대역폭 b에 대한 최대 전송 지연 함수 Deff(b)이다. 이들 둘 모두 s와 t를 접속하는 경로들(Ps,t)의 집합에 의존한다. 특히,
이고, (3)
이다. (4)
가용 대역폭 및 전송 지연의 차원으로부터,에 대해이,에 대해이 얻어진다. 따라서,은 모든 대역폭에 대해 최소 지연을 갖는 경로를 나타내므로,은 입구-출구 쌍(s, t)의 횡단 메트릭스를 기술하기에 충분하다.은 또한 가용 대역폭 및 s로부터 t까지의 전송 지연에 대한 효율적 프론티어를 나타낸다. 정의에 따르면,은 경로(Ps,t)의 집합에 의존한다. 그러나, 단지 Ps,t의 부분집합만이 효율적 프론티어에 기여한다. 이 집합은 이하에서는 s 및 t에 대한 효율적 경로 또는이라 한다.
(5)
효율적 프론티어는 일련의 세그먼트들로 간주될 수 있는데, 여기서 각각의 세그먼트는 다음의 경로의 전송 지연 함수에 대응한다.
(6)
여기서이며, i∈[1,n]인 경우, ρi는
로 주어지고, 따라서이다. (7)
식 (7)을 만족하는 다수의 경로가 존재할 수도 있다는 점에 있어서, ρi는 유일하지 않을 수도 있음에 주의하라. 또한, 일부 형태의 지연 함수에 있어서, 단일 경로가 다수의 세그먼트에 기여하는 일이 일어날 수도 있다. 예를 들면, 수학식 (6)에서 일부 i≠j에 대하여 ρi≡ρj가 가능하다.
도 1에는 일정한 지연 경로에 대하여, 효율적 프론티어의 일례가 도시되어 있다. 이들은 D(ρ,b)가 b에 독립적인 경로로서, 따라서 D(ρ)로 기록될 수 있다. 이 예에서,은 네 개의 경로로 이루어진다. 이들 경로의 전송 지연-대역폭 특성은 효율적 프론티어 상에 검은색 점으로 표시되어 있다. 이들 효율적 경로의 전송지연 및 가용 대역폭은을 완전히 정의한다. 음영 부분은 또한 백색 점으로 표시된의 일부가 아닌 비효율적 해들(non-efficient solutions)을 포함한다. 일정한 지연 경로에 있어서, 달성할 수 있는 최소 지연을 다음과 같이 정의하는 것이 가능하다.
(8)
일반적인 경우에, 요청된 대역폭에 대해을 얻는 것이 가능하지 않을 수도 있다. 이것은 경로의 지연 D(ρ)이 모두 동일할 때에만 가능하다. 예를 들면,가 하나의 경로만 포함하고 있는 경우가 그런 경우이다. 따라서, 임의의 네트워크에 있어서, 만약이면, "하나의 경로 해(solution)"가 존재한다.
이제, 그래프가 R0...,RN-1∈V라고 하는 N 개의 입구-출구 버텍스를 포함한다고 가정한다. 각각의 입구-출구 버텍스(Ri, Rj) 쌍에 대하여, 효율적 프론티어가 존재한다. 모든 효율적 프론티어 집합은 네트워크의 횡단 메트릭스를 완전히 정의한다. 임의의 입구-출구 버텍스 쌍들 간의 모든 효율적 프론티어의 대수 표현은 변환 매트릭스라고 하는 매트릭스로 주어진다. 변환 매트릭스는 다음과 같이 지정될 수도 있다.
(9)
상기 변환 매트릭스는 기본적인 라우팅 도메인의 위상(topology)의 대수 표현이다. 대역폭과 지연 메트릭스를 고려하여 횡단 특성을 완전히 유지한다는 점에 있어서 이것은 라우팅 도메인의 정확한 표현이다.
전술한 바와 같이, 본 발명에 의해 해결된 문제는 변환 매트릭스의 계산과 관련이 있다. 이 문제는 구체적으로 변환 매트릭스의 각 성분의 계산을 포함한다. 도 2a에서는, 네 개의 입구-출구 버텍스(0, 1, 2, 3)를 포함하는 예시적인 네트워크를 고려한다. 도 2b에서, 각 성분은 각각의 입구-출구 버텍스 쌍 사이의 효율적 프론티어이다.
본 발명의 바람직한 실시예에서, 다양한 버텍스에 대응하는 효율적 프론티어는 병렬로 "하향(descending)" 방식으로 반복해서 결정된다. "하향(descending)"은, 보다 큰 대역폭을 갖는 효율적 프론티어의 포인트들이 먼저 발견되고, 동등한 대역폭을 갖는 포인트들 중에서 보다 작은 지연을 갖는 포인트들이 먼저 발견된다는 것을 의미한다. 후술하는 바와 같이 y 축이 지연을, x 축이 대역폭을 나타내는 효율적 프론티어의 그래프를 고려하면, 이것은 우측(보다 높은 대역폭)으로부터 좌측(보다 낮은 대역폭)으로의 효율적 프론티어를 효과적으로 진행할 수 있다. 본 발명에 따른 효율적 프론티어를 결정하는 프로세스의 바람직한 예를 이하에서 세부에 걸쳐 간단하게 설명한다. 그러나, 일부 예비적인 정의들을 먼저 제시한다.
예비 정의(Preliminary definitions)
G(V,E)는 주어진 시점에서 네트워크를 나타내는 그래프로 한다. V는 버텍스의 집합이고, E는 유향 에지의 집합이다. 따라서, 모든 νi, νj∈E에 대하여 νi및 νj가 접속되면, 에지가 존재한다. 버텍스는 복수의 병렬 에지에 의해 접속된다. 두 개의 버텍스 νi및 νj를 접속하는 에지들의 집합은으로 표시된다. 표시은 버텍스 νi및νj를 접속하는 임의의 에지를 지칭한다. 에지에 대하여, 메트릭(코스트)은 대역폭 및 지연에 의해으로 표시되는데, 여기서및은 가용 대역폭 및 에지와 관련된 지연을 각각 나타낸다. 이들 메트릭스는 음이 아닌 정수라고 추정한다. 즉,및이다.
두 코스트 Ci=(Bi,Di) 및 Cj=(Bj,Dj)는 다음과 같이 비교된다.
·Bi=Bj및 Di=Dj인 경우에 한해, 코스트 Ci는 Cj와 동일하다(Ci=Cj). 그렇지 않으면, Ci는 Cj와 동일하지 않다(Ci≠Cj).
·Bi≥Bj, Di≤Dj및 (Ci≠Cj)인 경우에 한해, 코스트 Ci는 Cj보다 양호하거나, 또는 이와 마찬가지로, 코스트 Cj는 코스트 Ci보다 양호하지 못하다.
·Bk=min(Bi,Bj) 및 Dk=Di+Dj인 경우에 한해, 코스트 Ck는 코스트 Ci및 Cj를 연장한다(Ck=ext(Ci,Cj)).
프로세스
ν0를 효율적 프론티어가 계산되는 소스 버텍스라고 하자. ri(i=1,... N-1)를 ν0로부터 버텍스 νi에 도달하는 코스트들의 리스트라고 하자. fi(i=1,... N-1)를 νi와 관련된 효율적 프론티어라고 하자.및을 대응하는 리스트, 즉,및을 각각 포함하는 데이터 집합이라고 하자. 이들 데이터 집합은 예를 들어 표와 같이 구성될 수도 있다.
설명을 계속하기 전에, 다음의 부가적인 정의들을 제시한다.
i는 반복 카운터
νm(i)는 i번째 반복 표시를 나타내는 버텍스
는 버텍스 νj로부터의 아웃고잉 에지들의 집합
rj는 ν0로부터 버텍스 νj에 도달하는 코스트의 리스트
fj는 버텍스 νj에 대응하는 효율적 프론티어를 포함하는 리스트
다음은 일련의 규칙 1) 내지 3)의 형태의 상기 프로세스의 의사 코드 표현이다.
초기화 :
i번째 반복 단계
1) 집합내의 각각의 에지에 대하여,do
a) fm(i)리스트의 최종 항목과 코스트의 최종 성분에 의거하여 연장된 경로의 코스트 Cj=(Bj,Dj)를 계산, 즉,
b)ifCj가 리스트 fj의 임의의 성분과 같거나 양호하지 못하다면,thenCj폐기
c)else ifCj가 리스트 rj의 임의의 성분과 같거나 양호하지 못하다 면,thenCj폐기
else do
d)대역폭 및 지연(동등한 대역폭 성분들에 대해)에 따라 저장된 리스트를 유지함으로써 리스트 rj내에 Cj를 입력
e)Cj보다 양호하지 못한 리스트 rj의 임의의 성분들 폐기
done
2)if 데이터 집합이 비어있으면,thenSTOP.
3)else do
a) 리스트 rk내에 포함된데이터 집합의 최상의 성분을 선택. 상기 최상의 성분은 최대 대역폭을 가지며 및 다수의 성분이 있는 경 우에, 가장 낮은 지연을 갖는 성분으로 간주될 수 있다. 나머지 타이들(ties)은 홉 개수(hop count)와 같은 다른 표준에 따라서 또 는 임의로 파기된다.
b) 리스트 rk로부터 상기 성분을 제거하여 그 성분을 리스트 fk에 배 치.
c) 카운터 증가 : i=i+1.
d) m(i)=k(따라서 νm(i)=νk)
done
Go back to Step
실시예
다음은 도 3을 참조하여, 네 개의 노드를 갖는 네트워크의 일례의 버텍스 0으로부터 나머지 버텍스 1, 2, 3으로의 효율적 프론티어를 결정하기 위한 본 발명을 이용하는 방법의 일례를 설명한다. 본 발명은 네 개보다 많거나 또는 적은 노드를 갖는 네트워크에도 동등하게 적용 가능하다.
단계 1
도 4를 참조하면, 상기 방법은 버텍스 0으로부터 시작하여 버텍스 0으로부터의 모든 아웃고잉 에지들을 고려하고 있다. 세 개의 에지는 버텍스 1, 2, 3에 대한 접속을 각각 제공한다. 여기서 버텍스 0과 관련된 코스트는 없다. 따라서, 버텍스 1, 2, 3으로의 대응 에지의 코스트는 상기 규칙 1d)에 따라서데이터 집합 내에 삽입된다.
데이터 집합에서, 대역폭에 의한 최상의 코스트는 버텍스 3에 대한 9,5이다. 그 다음에 이 코스트는 규칙 3b에 따라서,데이터 집합으로부터 버텍스 3에 대한 효율적 프론티어로 이동한다.
상기 프로세스는 이제 9,5의 관련 코스트를 갖는 버텍스 3으로 이동한다.
단계 2
도 5를 참조하면, 버텍스 3은 버텍스 1 및 2로의 두 에지를 갖는다.데이터 집합 내에 설정된 버텍스 3의 9,5와 관련된 코스트에 의해 연장된 이들 에지의 코스트가 도 5에 도시되어 있다.데이터 집합 내의 버텍스 1 및 2 에 대한 성분들이 없기 때문에 이들 코스트는데이터 집합 내에 입력된다.
가장 넓은 대역폭 값은 버텍스 2의 8,10에 대응한다. 이 값은데이터 집합으로부터 버텍스 2의 효율적 프론티어로 이동한다.
상기 프로세스는 8,10의 관련 코스트를 갖는 버텍스 2로 이동한다.
단계 3
도 6에서, 버텍스 2는 버텍스 1 및 3으로의 두 개의 에지를 갖는다.데이터 집합 내의 버텍스 2(8,10) 집합과 관련된 코스트에 의해 연장된 이들 에지의 코스트가 도 6에 도시되어 있다. 버텍스 1에 도달하는 코스트는 r1리스트 내의 코스트(6,9)보다 양호하지 못한 (6,12)이다. 따라서, 규칙 1c)에 따라서 이것은 폐기된다. 버텍스 3에 도달하는 코스트는 f3리스트 내의 코스트 (9,5)보다 양호하지 못한 (1,11)이다. 따라서, 규칙 1b)에 따라서 이것은 폐기된다. 가장 넓은 대역폭 값은 버텍스 2(7,6)에 대응한다.
이 값은데이터 집합으로부터 버텍스 2의 효율적 프론티어로 이동한다.
상기 방법은 7,6의 관련 코스트를 갖는 버텍스 2로 진행한다.
단계 4
도 7에서, 버텍스 2는 버텍스 1 및 3으로의 두 개의 에지를 갖는다.데이터 집합 내의 버텍스 2(7,6) 집합과 관련된 코스트에 의해 연장된 이들 에지의 코스트들은 도 7에 도시되어 있다. 버텍스 1에 도달하는 코스트는 r1의 임의의 성분과 동일하지 않거나 또는 양호하지 못한 (6,8)이다. 따라서, 이것은 규칙 1d)에 따라서데이터 집합으로 입력된다. 그러나, 성분 (6,9)는 (6,8)보다 양호하지 않다. 따라서, 이것은 규칙 1e)에 따라서 폐기된다. 버텍스 3에 도달하는 코스트는 f3리스트 내의 코스트(9,5)보다 양호하지 못한 (1,7)이다. 따라서, 규칙 1b)에 따라서 이것은 폐기된다.
가장 넓은 대역폭 값은 버텍스 1의 6,8에 대응한다. 이 값은데이터 집합으로부터 버텍스 1의 효율적인 프론티어로 이동한다.
상기 방법은 이제 6,8의 관련 코스트를 갖는 버텍스 1로 진행한다.
단계 5
도 8에서, 버텍스 1은 버텍스 2 및 3에 대한 두 개의 에지를 갖는다. 버텍스 2에 도달하는 코스트는 f2리스트 내의 코스트(7,6)보다 양호하지 않은 (2,9)이다. 따라서, 규칙 1b)에 따라 이것은 폐기된다. 버텍스 3에 도달하는 코스트는 f3리스트 내의 코스트(9,5)보다 양호하지 못한 (3,11)이다. 따라서, 규칙 1b)에 따라 이것은 폐기된다.
가장 넓은 대역폭 값은 버텍스 1에 대응한다. 이 값은데이터 접합으로부터 버텍스 1의 효율적 프론티어로 이동한다.
상기 프로세스는 이제 4,1의 관련 코스트를 갖는 버텍스 1로 진행한다.
단계 6
도 9에서, 버텍스 1은 버텍스 2 및 3으로의 두 개의 에지를 갖는다. 버텍스 2에 도달하는 코스트는 f2의 임의의 성분과 동일하지 않거나 또는 양호하지 못한 (2,2)이다. 따라서, 이것은 규칙 1d)에 따라서데이터 집합에 입력된다. 버텍스 3에 도달하는 코스트는 f3의 임의의 성분과 동일하지 않거나 양호하지 않은(3,4)이다. 따라서, 이것은 규칙 1d)에 따라데이터 집합 내에 입력된다.
가장 넓은 대역폭 값은 버텍스 3의 3,4에 대응한다. 이 값은데이터 접합으로부터 효율적 프론티어로 이동한다.
상기 방법은 이제 3,4의 관련 코스트를 갖는 버텍스 3으로 진행한다.
단계 7
도 10에서, 버텍스 3은 버텍스 1 및 2로의 두 개의 에지를 갖는다. 버텍스 1에 도달하는 코스트는 f1리스트 내의 코스트(4,1)보다 양호하지 못한 (3,8)이다. 따라서, 규칙 1b)에 따라서 이것은 폐기된다. 그러나, 버텍스 2에 도달하는 코스트는 f2또는 r2의 임의의 성분과 동일하지 않거나 양호하지 않은 (3,5)이다. 따라서, 이것은 규칙 1d)에 따라데이터 집합 내에 입력된다.
가장 넓은 대역폭 값은 버텍스 2의 3,5에 대응한다. 이 값은데이터 접합으로부터 버텍스 2의 효율적 프론티어로 이동한다.
상기 방법은 이제 3,5의 관련 코스트를 갖는 버텍스 2로 진행한다.
단계 8
도 11에서, 버텍스 2는 버텍스 1 및 3으로의 두 개의 에지를 갖는다. 버텍스 1에 도달하는 코스트는 f1리스트 내의 코스트(4,1)보다 양호하지 못한 (3,7)이다. 따라서, 이것은 규칙 1b)에 따라서 이것은 폐기된다. 버텍스 3에 도달하는 코스트는 f3리스트 내의 코스트 (3,4)보다 양호하지 않은 (1,6)이다. 따라서, 규칙 1b)에 따라 이것은 폐기된다.
가장 넓은 대역폭 값은 버텍스 2의 2,2에 대응한다. 이 값은데이터 접합으로부터 버텍스 2의 효율적 프론티어로 이동한다.
상기 방법은 이제 2,2의 관련 코스트를 갖는 버텍스 2로 진행한다.
단계 9
도 12에서, 버텍스 2은 버텍스 1 및 3으로의 두 개의 에지를 갖는다. 버텍스 1에 도달하는 코스트는 f1리스트 내의 코스트(4,1)보다 양호하지 못한 (2,4)이다. 따라서, 규칙 1b)에 따라 이것은 폐기된다. 그러나, 버텍스 3에 도달하는 코스트는 f3리스트 내의 임의의 성분과 동일하지 않거나 양호하지 못한 (1,3)이다. 따라서, 이것은 규칙 1d)에 따라데이터 집합 내에 입력된다.
가장 넓은 대역폭 값은 버텍스 3의 1,3에 대응한다. 이 값은데이터 접합으로부터 버텍스 3의 효율적 프론티어로 이동한다.
상기 방법은 이제 1,3의 관련 코스트를 갖는 버텍스 3으로 진행한다.
단계 10
도 13에서, 버텍스 3은 버텍스 1 및 2로의 두 개의 에지를 갖는다. 버텍스1에 도달하는 코스트는 f1리스트 내의 코스트(4,1)보다 양호하지 못한 (1,7)이다. 따라서, 규칙 1b)에 따라 이것은 폐기된다. 버텍스 2에 도달하는 코스트는 f2리스트 내의 코스트 (2,2)보다 양호하지 못한 (1,4)이다. 따라서, 규칙 1b)에 따라 이것은 폐기된다.
데이터 집합 내에 더 이상의 성분이 없기 때문에, 상기 프로세스는 규칙 2)에 따라 종료한다.
결론
버텍스 0으로부터 버텍스 1, 2, 3으로의 효율적 프론티어는 다음과 같다.
도 14 내지 16은 버텍스 0으로부터 버텍스 1, 2, 3으로의 효율적 프론티어를 각각 도시한 그래프이다.
도 17을 참조하면, 본 발명의 바람직한 실시예에서는, 데이터 처리 시스템의 프로세서에 로딩될 때, 프로세서가 데이터 통신 네트워크 내에 소스 노드와 복수의 데스티네이션 노드를 포함하는 노드들의 그룹에 대한 효율적인 경로 코스트 집합을 도출하는 방법을 실시하도록 하는 컴퓨터 프로그램 코드를 포함하는 컴퓨터 프로그램 요소가 제공되는데, 여기서, 상기 그룹 내의 노드들 사이의 경로들에 대한 경로 코스트는 네트워크 내에서 규정되며, 각각의 경로 코스트는 가용 대역폭을 나타내는 제한적인 코스트 및 전송 지연을 나타내는 값과 같은 부가적인 코스트를 포함한다.
상기 방법은, 단계 10에서 데이터 처리 시스템의 메모리 내의 제 1 데이터 집합 내에 소스 노드로부터 임의의 데스티네이션 노드들로의 직접 경로들에 대한 경로 코스트를 기록하는 것을 포함한다. 각각의 기록된 코스트는 제 1 데이터 집합 내에서, 대응 경로에 의해 도달된 노드와 관련된다.
단계 20에서, 최상의 경로 코스트가 상기 제 1 데이터 집합으로부터 선택된다. 최상의 경로 코스트는 최상의 제한적인 코스트를 포함하거나, 또는 복수의 경로 코스트가 동등한 제한적인 코스트들을 포함할 경우에는 최상의 제한적인 코스트와 최상의 부가적인 코스트를 갖는 경로 코스트를 포함하도록 결정된다. 만약, 예를 들어, 제한적인 코스트가 대역폭을 나타내는 값이라면, 최상의 제한적인 코스트는 최대 대역폭을 나타내는 코스트이다. 마찬가지로, 부가적인 코스트가 전송 지연을 나타내는 값이라면, 최상의 부가적인 코스트는 최소 전송 지연을 나타내는 코스트이다.
단계 30에서, 단계 20에서 선택된 최상의 경로 코스트가 데이터 처리 시스템의 메모리 내의 제 2 데이터 집합 내에 기록된다. 기록된 코스트는 제 2 데이터 집합 내에서 대응 경로에 의해 도달된 노드와 관련된다.
단계 40에서, 제 2 데이터 집합 내의 단계 30에서 기록된 코스트는 제 1 데이터 집합으로부터 제거된다. 상기 제거는 삭제, 플래깅(flagging), 또는 추가적인 고려사항으로부터 코스트를 배제하기 위한 기타 동작을 포함할 수도 있다.
단계 50에서, 단계 30에서 기록된 코스트에 대응하는 경로에 의해 도달된 데스티네이션 노드로부터 그룹 내 임의의 다른 노드로의 직접 경로에 대한 누적 경로 코스트는 제 1 데이터 집합 내에 기록된다. 각각의 기록된 누적 경로 코스트는 제 1 데이터 집합 내에서 대응 경로에 의해 도달된 노드와 관련된다.
단계 60에서, 단계 50에서 관련된 코스트가 제 1 데이터 집합 내에 기록된 각각의 노드에 대하여, 제 1 및 제 2 데이터 집합 내에서 그 노드와 관련된 코스트들이 비교된다. 그 노드에 도달하기 위한 임의의 다른 그러한 코스트보다 양호하지 못한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트, 또는 그 노드에 도달하기 위한 임의의 다른 그러한 코스트와 동등한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트는 제 1 데이터 집합으로부터 제거된다.
단계 70에서, 단계 20 내지 60은 단계 60 후에 제 1 데이터 집합 내에 어떠한 코스트도 남아있지 않을 때까지 반복된다. 단계 80에서, 그 결과의 제 2 데이터 집합은 효율적 코스트 집합을 포함한다. 바꾸어 말하면, 효율적 코스트 집합은 소스 노드에 대한 효율적 프론티어를 포함한다. 데이터 처리 시스템은 라우터, 스위치, 브리지, 브라우터(brouter), 허브, 및 통신 네트워크에서 정보를 송수신하는 기타 데이터 네트워킹 장치일 수도 있다.
도 18에는, 본 발명의 다른 실시예에서, 데이터 통신 네트워크(170)로의 접속을 위한 입력/출력(I/O) 포트(110), 상기 I/O 포트(110)에 결합된 프로세서(120), 상기 프로세서에 접속된 메모리(130)를 포함하는 데이터 네트워킹 장치(100)가 제시되어 있다. 메모리는 제 1 데이터 집합(140)의 저장 장소에 할당된 공간, 제 2 데이터 집합(150)의 저장 장소에 할당된 공간, 제어 로직 프로그램 코드(160)를 포함한다. 동작시, 데이터 네트워킹 장치는 데이터 통신 네트워크 내에 소스 노드와 복수의 데스티네이션 노드를 포함하는 노드 그룹 에 대해 효율적 경로 코스트들의 집합을 도출한다. 데이터 처리 장치는 데이터 통신 네트워크의 소스 노드를 구현할 수도 있다. 그룹 내 노드들 간의 경로에 대한 경로 코스트는 네트워크에서 규정되며 각각의 경로 코스트는 제한적인 코스트와 부가적인 코스트를 포함한다. 동작시, 제어 로직(160)은
a) 상기 제 1 데이터 집합(140) 내에, 상기 소스 노드로부터 임의의 상기 데스티네이션 노드로의 직접 경로에 대한 상기 경로 코스트를 기록하고 -각각의 기록된 코스트는 상기 제 1 데이터 집합 내에서 상기 대응하는 경로에 의해 도달된 상기 노드와 관련됨-,
b) 상기 제 1 데이터 집합(140)으로부터 최상의 경로 코스트 -상기 최상의 경로 코스트는 최상의 제한적인 코스트를 포함하도록 결정되며, 복수의 상기 경로 코스트가 동등한 제한적인 코스트를 포함하는 경우에는 경로 코스트가 상기 최상의 제한적인 코스트와 최상의 부가적인 코스트를 포함하도록 결정됨- 를 선택하고,
c) 상기 제 2 데이터 집합(150) 내에, 단계 b)에서 선택된 상기 최상의 경로코스트를 기록하고 -상기 기록된 코스트는 상기 제 2 데이터 집합(150) 내에서 상기 대응 경로에 의해 도달된 상기 노드와 관련됨-,
d) 상기 제 2 데이터 집합(150) 내의 단계 c)에서 기록된 상기 코스트를 상기 제 1 데이터 집합으로부터 제거하고,
e) 상기 제 1 데이터 집합(140) 내에, 단계 c)에 기록된 상기 코스트에 대응하는 상기 경로에 의해 도달된 상기 데스티네이션 노드로부터 상기 그룹 내의 임의의 다른 노드로의 직접 경로에 대한 누적 경로 코스트를 기록하고 -각각의 기록된 누적 경로 코스트는 상기 제 1 데이터 집합 내에서 상기 대응 경로에 의해 도달된 상기 노드와 관련됨-,
f) 단계 e)에서 제 1 데이터 집합(140) 내에 관련 코스트가 기록되어 있는 각각의 노드에 대하여, 상기 제 1 데이터 집합(140)및 제 2 데이터 집합(150) 내의 상기 노드와 관련된 상기 코스트들을 비교하고, 그 노드에 도달하기 위한 임의의 다른 그러한 코스트보다 양호하지 못한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트, 또는 그 노드에 도달하기 위한 임의의 다른 그러한 코스트와 동등한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트를 상기 제 1 데이터 집합으로부터 제거하고,
g) 단계 f) 후에 상기 제 1 데이터 집합 내에 남아 있는 코스트가 없을 때까지 단계 b) 내지 f)를 반복하도록 구성된다.
그 결과의 제 2 데이터 집합은 효율적인 코스트 집합을 포함한다. 도 18을참조하여 전술한 본 발명의 실시예에서, 제어 로직(160)은 컴퓨터 프로그램 코드이지만, 본 발명의 다른 실시예에서는 상기 제어 로직이 적어도 부분적으로는 배선에 의한 논리 회로로 특별히 구현될 수도 있음에 주의하라. 또한 상기 경로들 중 적어도 하나는 복수의 링크 및 적어도 하나의 중간 노드를 포함할 수도 있음에 유의하라.
요약하면, 전술한 본 발명의 바람직한 실시예에서, 데이터 통신 네트워크 내에 소스 노드 및 복수의 데스티네이션 노드를 포함하는 노드 그룹에 대한 효율적 경로 코스트 집합이 도출되는데, 여기서, 상기 그룹 내의 노드들 사이의 경로에 대한 경로 코스트는 네트워크 내에서 규정되고, 각각의 경로 코스트는 제한적인 코스트 및 부가적인 코스트를 포함하며, 상기 효율적 경로 코스트 집합 도출 방법은 우선적으로 보다 높은 대역폭의 경로를 반복적으로 식별하는 단계와, 동등한 대역폭의 경로가 둘 이상 있는 경우에 보다 낮은 전송 지연을 갖는 경로를 선택하는 단계를 포함한다.

Claims (11)

  1. 데이터 통신 네트워크 내에 소스 노드와 복수의 데스티네이션 노드를 포함하는 노드들의 그룹에 대한 효율적인 경로 코스트 집합을 도출하기 위한 방법에 있어서,
    상기 그룹 내의 노드들 사이의 경로들에 대한 상기 경로 코스트들은 상기 네트워크 내에서 규정되고 각각의 경로 코스트는 제한적인 코스트 및 부가적인 코스트를 포함하고,
    a) 제 1 데이터 집합 내에, 상기 소스 노드로부터 임의의 상기 데스티네이션 노드로의 직접 경로에 대한 상기 경로 코스트를 기록하는 단계 -각각의 기록된 코스트는 상기 제 1 데이터 집합 내에서 상기 대응하는 경로에 의해 도달된 상기 노드와 관련됨- 와,
    b) 상기 제 1 데이터 집합으로부터 최상의 경로 코스트 -상기 최상의 경로 코스트는 최상의 제한적인 코스트를 포함하도록 결정되며, 복수의 상기 경로 코스트가 동등한 제한적인 코스트를 포함하는 경우에는 경로 코스트가 상기 최상의 제한적인 코스트와 최상의 부가적인 코스트를 포함하도록 결정됨- 를 선택하는 단계와,
    c) 제 2 데이터 집합 내에 단계 b)에서 선택된 상기 최상의 경로 코스트를 기록하는 단계 -상기 기록된 코스트는 상기 제 2 데이터 집합 내에서 상기 대응 경로에 의해 도달된 상기 노드와 관련됨- 와,
    d) 상기 제 2 데이터 집합 내의 단계 c)에서 기록된 상기 코스트를 상기 제 1 데이터 집합으로부터 제거하는 단계와,
    e) 상기 제 1 데이터 집합 내에, 단계 c)에 기록된 상기 코스트에 대응하는 상기 경로에 의해 도달된 상기 데스티네이션 노드로부터 상기 그룹 내의 임의의 다른 노드로의 직접 경로에 대한 누적 경로 코스트를 기록하는 단계 -각각의 기록된 누적 경로 코스트는 상기 제 1 데이터 집합 내에서 상기 대응 경로에 의해 도달된 상기 노드와 관련됨- 와,
    f) 단계 e)에서 제 1 데이터 집합 내에 관련 코스트가 기록되어 있는 각각의 노드에 대하여, 상기 제 1 및 제 2 데이터 집합 내의 상기 노드와 관련된 상기 코스트들을 비교하고, 그 노드에 도달하기 위한 임의의 다른 그러한 코스트보다 양호하지 못한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트, 또는 그 노드에 도달하기 위한 임의의 다른 그러한 코스트와 동등한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트를 상기 제 1 데이터 집합으로부터 제거하는 단계와,
    g) 단계 f) 후에 상기 제 1 데이터 집합 내에 남아 있는 코스트가 없을 때까지 단계 b) 내지 f)를 반복하는 단계를 포함하고,
    이들 단계에 의해, 그 결과의 제 2 데이터 집합은 효율적인 코스트 집합을 포함하는
    효율적인 경로 코스트 집합 도출 방법.
  2. 제 1 항에 있어서,
    각각의 상기 제한적인 코스트는 상기 대응 경로의 대역폭을 나타내는 값을 포함하고, 최상의 상기 제한적인 코스트는 최대 대역폭을 나타내는 상기 코스트인 효율적인 경로 코스트 집합 도출 방법.
  3. 제 1 항 또는 2 항에 있어서,
    각각의 상기 부가적인 코스트는 상기 대응 경로와 관련된 전송 지연을 나타내는 값을 포함하고, 최상의 상기 부가적인 코스트는 최소 전송 지연을 나타내는 상기 코스트인 효율적인 경로 코스트 집합 도출 방법.
  4. 제 1 항 내지 3 항 중 어느 한 항에 있어서,
    상기 경로들 중 적어도 하나는 복수의 링크와 적어도 하나의 중간 노드를 포함하는 효율적인 경로 코스트 집합 도출 방법.
  5. 데이터 처리 시스템의 프로세서에 로딩될 때, 상기 프로세서가 제 1 항 내지 4 항 중 어느 한 항에 청구된 효율적인 경로 코스트 집합을 도출하는 방법을 수행하도록 구성된 컴퓨터 프로그램 코드 수단을 포함하는 컴퓨터 프로그램 요소.
  6. 데이터 통신 네트워크 내에 소스 노드와 복수의 데스티네이션 노드를 포함하는 노드들의 그룹에 대한 효율적인 경로 코스트 집합을 도출하기 위한 장치에 있어서,
    상기 그룹 내의 노드들 사이의 경로들에 대한 상기 경로 코스트들은 상기 네트워크 내에서 규정되고 각각의 경로 코스트는 제한적인 코스트 및 부가적인 코스트를 포함하고, 상기 장치는 경로 코스트들로 이루어진 제 1 및 제 2 데이터 집합 및 제어 로직을 저장하기 위한 메모리를 포함하고, 상기 제어 로직은
    a) 상기 제 1 데이터 집합 내에, 상기 소스 노드로부터 임의의 상기 데스티네이션 노드로의 직접 경로에 대한 상기 경로 코스트를 기록하고 -각각의 기록된 코스트는 상기 제 1 데이터 집합 내에서 상기 대응하는 경로에 의해 도달된 상기 노드와 관련됨-,
    b) 상기 제 1 데이터 집합으로부터 최상의 경로 코스트 -상기 최상의 경로 코스트는 최상의 제한적인 코스트를 포함하도록 결정되며, 복수의 상기 경로 코스트가 동등한 제한적인 코스트를 포함하는 경우에는 경로 코스트가 상기 최상의 제한적인 코스트와 최상의 부가적인 코스트를 포함하도록 결정됨- 를 선택하고,
    c) 상기 제 2 데이터 집합 내에, 단계 b)에서 선택된 상기 최상의 경로 코스트를 기록하고 -상기 기록된 코스트는 상기 제 2 데이터 집합 내에서 상기 대응 경로에 의해 도달된 상기 노드와 관련됨-,
    d) 상기 제 2 데이터 집합 내의 단계 c)에서 기록된 상기 코스트를 상기 제 1 데이터 집합으로부터 제거하고,
    e) 상기 제 1 데이터 집합 내에, 단계 c)에 기록된 상기 코스트에 대응하는 상기 경로에 의해 도달된 상기 데스티네이션 노드로부터 상기 그룹 내의 임의의 다른 노드로의 직접 경로에 대한 누적 경로 코스트를 기록하고 -각각의 기록된 누적 경로 코스트는 상기 제 1 데이터 집합 내에서 상기 대응 경로에 의해 도달된 상기 노드와 관련됨-,
    f) 단계 e)에서 제 1 데이터 집합 내에 관련 코스트가 기록되어 있는 각각의 노드에 대하여, 상기 제 1 및 제 2 데이터 집합 내의 상기 노드와 관련된 상기 코스트들을 비교하고, 그 노드에 도달하기 위한 임의의 다른 그러한 코스트보다 양호하지 못한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트, 또는 그 노드에 도달하기 위한 임의의 다른 그러한 코스트와 동등한 제한적인 코스트 및 양호하지 못한 부가적인 코스트를 갖는 상기 노드에 도달하기 위한 임의의 그러한 코스트를 상기 제 1 데이터 집합으로부터 제거하고,
    g) 단계 f) 후에 상기 제 1 데이터 집합 내에 남아 있는 코스트가 없을 때까지 단계 b) 내지 f)를 반복하도록 구성되며,
    이에 따라, 그 결과의 상기 제 2 데이터 집합은 효율적인 코스트 집합을 포함하는
    효율적인 경로 코스트 집합 도출 장치.
  7. 제 6 항에 있어서,
    각각의 상기 제한적인 코스트는 상기 대응 경로의 대역폭을 나타내는 값을 포함하고, 최상의 상기 제한적인 코스트는 최대 대역폭을 나타내는 상기 코스트인 효율적인 경로 코스트 집합 도출 장치.
  8. 제 6 항 또는 7 항에 있어서,
    각각의 상기 부가적인 코스트는 상기 대응 경로와 관련된 전송 지연을 나타내는 값을 포함하고, 최상의 상기 부가적인 코스트는 최소 전송 지연을 나타내는 상기 코스트인 효율적인 경로 코스트 집합 도출 장치.
  9. 제 6 항 내지 8 항 중 어느 한 항에 있어서,
    상기 경로들 중 적어도 하나는 복수의 링크와 적어도 하나의 중간 노드를 포함하는 효율적인 경로 코스트 집합 도출 장치.
  10. 데이터 통신 네트워크의 경로에 각각 접속하기 위한 복수의 포트와, 상기 경로에 결합된 제 6 항 내지 9 항 중 어느 한 항에 청구된 효율적인 경로 코스트 집합을 도출하기 위한 장치를 포함하는 데이터 네트워킹 장치.
  11. 복수의 경로에 의해 상호접속된 복수의 노드를 포함하되, 상기 노드들 중 적어도 하나는 제 10 항에 청구된 데이터 네트워킹 장치를 포함하는 데이터 네트워크.
KR1020037006652A 2000-11-21 2001-11-12 효율적인 경로 코스트 집합 도출 방법 및 장치 Expired - Fee Related KR100544008B1 (ko)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
EP00811104.9 2000-11-21
EP00811104 2000-11-21
PCT/IB2001/002078 WO2002043324A2 (en) 2000-11-21 2001-11-12 Routing costs in data networks

Publications (2)

Publication Number Publication Date
KR20030059259A true KR20030059259A (ko) 2003-07-07
KR100544008B1 KR100544008B1 (ko) 2006-01-20

Family

ID=8175042

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020037006652A Expired - Fee Related KR100544008B1 (ko) 2000-11-21 2001-11-12 효율적인 경로 코스트 집합 도출 방법 및 장치

Country Status (9)

Country Link
US (1) US7355980B2 (ko)
EP (1) EP1336274B1 (ko)
JP (1) JP3762748B2 (ko)
KR (1) KR100544008B1 (ko)
CN (1) CN1220353C (ko)
AU (1) AU2002212596A1 (ko)
BR (1) BR0115551A (ko)
TW (1) TW561747B (ko)
WO (1) WO2002043324A2 (ko)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100810016B1 (ko) * 2003-07-25 2008-10-27 인터내셔널 비지네스 머신즈 코포레이션 전자 장치 접속 리소스 관리
WO2009023689A3 (en) * 2007-08-15 2009-05-22 Adc Telecommunications Inc Delay management for distributed communications networks
KR100905650B1 (ko) * 2007-08-01 2009-06-30 에스케이 텔레콤주식회사 신호 루트의 라우팅 코스트 오류 검출 방법과 이를 위한네트워크 관리 시스템
US8743718B2 (en) 2011-06-21 2014-06-03 Adc Telecommunications, Inc. End-to-end delay management for distributed communications networks
US9450689B2 (en) 2013-10-07 2016-09-20 Commscope Technologies Llc Systems and methods for delay management in distributed antenna system with direct digital interface to base station

Families Citing this family (76)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FI20011392L (fi) * 2001-06-28 2002-12-29 Nokia Corp Mekanismi multicast-jakelua varten tietoliikennejärjestelmässä
US7145878B2 (en) * 2001-07-27 2006-12-05 Corrigent Systems Ltd. Avoiding overlapping segments in transparent LAN services on ring-based networks
US7283478B2 (en) * 2001-11-28 2007-10-16 Corrigent Systems Ltd. Traffic engineering in bi-directional ring networks
US7499404B2 (en) * 2002-08-30 2009-03-03 Nortel Networks Limited Distributed quality of service routing
US7792991B2 (en) * 2002-12-17 2010-09-07 Cisco Technology, Inc. Method and apparatus for advertising a link cost in a data communications network
US7707307B2 (en) * 2003-01-09 2010-04-27 Cisco Technology, Inc. Method and apparatus for constructing a backup route in a data communications network
US7869350B1 (en) 2003-01-15 2011-01-11 Cisco Technology, Inc. Method and apparatus for determining a data communication network repair strategy
US7336605B2 (en) 2003-05-13 2008-02-26 Corrigent Systems, Inc. Bandwidth allocation for link aggregation
US7330440B1 (en) 2003-05-20 2008-02-12 Cisco Technology, Inc. Method and apparatus for constructing a transition route in a data communications network
US7864708B1 (en) 2003-07-15 2011-01-04 Cisco Technology, Inc. Method and apparatus for forwarding a tunneled packet in a data communications network
US7466661B1 (en) 2003-09-22 2008-12-16 Cisco Technology, Inc. Method and apparatus for establishing adjacency for a restarting router during convergence
US7554921B2 (en) * 2003-10-14 2009-06-30 Cisco Technology, Inc. Method and apparatus for generating routing information in a data communication network
US7580360B2 (en) * 2003-10-14 2009-08-25 Cisco Technology, Inc. Method and apparatus for generating routing information in a data communications network
US7710882B1 (en) 2004-03-03 2010-05-04 Cisco Technology, Inc. Method and apparatus for computing routing information for a data communications network
GB0407144D0 (en) * 2004-03-30 2004-05-05 British Telecomm Networks
US7848240B2 (en) * 2004-06-01 2010-12-07 Cisco Technology, Inc. Method and apparatus for forwarding data in a data communications network
US7418000B2 (en) * 2004-06-03 2008-08-26 Corrigent Systems Ltd. Automated weight calculation for packet networks
US8843978B2 (en) 2004-06-29 2014-09-23 Time Warner Cable Enterprises Llc Method and apparatus for network bandwidth allocation
US7577106B1 (en) 2004-07-12 2009-08-18 Cisco Technology, Inc. Method and apparatus for managing a transition for a class of data between first and second topologies in a data communications network
US7330431B2 (en) * 2004-09-03 2008-02-12 Corrigent Systems Ltd. Multipoint to multipoint communication over ring topologies
US7630298B2 (en) * 2004-10-27 2009-12-08 Cisco Technology, Inc. Method and apparatus for forwarding data in a data communications network
US7496644B2 (en) * 2004-11-05 2009-02-24 Cisco Technology, Inc. Method and apparatus for managing a network component change
US7974223B2 (en) * 2004-11-19 2011-07-05 Corrigent Systems Ltd. Virtual private LAN service over ring networks
US7567565B2 (en) 2005-02-01 2009-07-28 Time Warner Cable Inc. Method and apparatus for network bandwidth conservation
US7656886B2 (en) * 2005-02-07 2010-02-02 Chin-Tau Lea Non-blocking internet backbone network
US9306831B2 (en) * 2005-02-14 2016-04-05 Cisco Technology, Inc. Technique for efficient load balancing of TE-LSPs
US7933197B2 (en) * 2005-02-22 2011-04-26 Cisco Technology, Inc. Method and apparatus for constructing a repair path around a non-available component in a data communications network
US7848224B2 (en) * 2005-07-05 2010-12-07 Cisco Technology, Inc. Method and apparatus for constructing a repair path for multicast data
US7835312B2 (en) * 2005-07-20 2010-11-16 Cisco Technology, Inc. Method and apparatus for updating label-switched paths
US7693043B2 (en) * 2005-07-22 2010-04-06 Cisco Technology, Inc. Method and apparatus for advertising repair capability
NZ541666A (en) * 2005-08-05 2008-09-26 Elizabeth Cramer Methods of modulating apoptosis and platelet production using an isolated oligonucleotide, its compliment, a vector with the expression sequence or an isolated polypeptide all relating to cytochrome C
US7978611B2 (en) * 2005-09-06 2011-07-12 At&T Intellectual Property I, L.P. Systems and methods to determine network routes based on transmission medium length
US7898957B2 (en) * 2005-10-03 2011-03-01 The Hong Kong University Of Science And Technology Non-blocking destination-based routing networks
US7983150B2 (en) * 2006-01-18 2011-07-19 Corrigent Systems Ltd. VPLS failure protection in ring networks
US8111618B2 (en) * 2006-01-27 2012-02-07 Alcatel Lucent End-to-end service quality using source-routed probes
US8170065B2 (en) 2006-02-27 2012-05-01 Time Warner Cable Inc. Methods and apparatus for selecting digital access technology for programming and data delivery
US8458753B2 (en) 2006-02-27 2013-06-04 Time Warner Cable Enterprises Llc Methods and apparatus for device capabilities discovery and utilization within a content-based network
US7808931B2 (en) * 2006-03-02 2010-10-05 Corrigent Systems Ltd. High capacity ring communication network
US7593400B2 (en) * 2006-05-19 2009-09-22 Corrigent Systems Ltd. MAC address learning in a distributed bridge
US9386327B2 (en) 2006-05-24 2016-07-05 Time Warner Cable Enterprises Llc Secondary content insertion apparatus and methods
US8280982B2 (en) 2006-05-24 2012-10-02 Time Warner Cable Inc. Personal content server apparatus and methods
US8024762B2 (en) 2006-06-13 2011-09-20 Time Warner Cable Inc. Methods and apparatus for providing virtual content over a network
US7660303B2 (en) 2006-08-22 2010-02-09 Corrigent Systems Ltd. Point-to-multipoint functionality in a bridged network
US7701845B2 (en) 2006-09-25 2010-04-20 Cisco Technology, Inc. Forwarding data in a data communications network
US8014291B2 (en) * 2006-11-28 2011-09-06 Cisco Technology, Inc. Relaxed constrained shortest path first (R-CSPF)
US8181206B2 (en) 2007-02-28 2012-05-15 Time Warner Cable Inc. Personal content server apparatus and methods
US20080235746A1 (en) 2007-03-20 2008-09-25 Michael James Peters Methods and apparatus for content delivery and replacement in a network
US7940776B2 (en) * 2007-06-13 2011-05-10 Cisco Technology, Inc. Fast re-routing in distance vector routing protocol networks
US9071859B2 (en) 2007-09-26 2015-06-30 Time Warner Cable Enterprises Llc Methods and apparatus for user-based targeted content delivery
US8561116B2 (en) 2007-09-26 2013-10-15 Charles A. Hasek Methods and apparatus for content caching in a video network
US8099757B2 (en) 2007-10-15 2012-01-17 Time Warner Cable Inc. Methods and apparatus for revenue-optimized delivery of content in a network
US9503691B2 (en) 2008-02-19 2016-11-22 Time Warner Cable Enterprises Llc Methods and apparatus for enhanced advertising and promotional delivery in a network
US8813143B2 (en) 2008-02-26 2014-08-19 Time Warner Enterprises LLC Methods and apparatus for business-based network resource allocation
US8270316B1 (en) * 2009-01-30 2012-09-18 The Regents Of The University Of California On-chip radio frequency (RF) interconnects for network-on-chip designs
US9866609B2 (en) 2009-06-08 2018-01-09 Time Warner Cable Enterprises Llc Methods and apparatus for premises content distribution
US9178634B2 (en) 2009-07-15 2015-11-03 Time Warner Cable Enterprises Llc Methods and apparatus for evaluating an audience in a content-based network
US8813124B2 (en) 2009-07-15 2014-08-19 Time Warner Cable Enterprises Llc Methods and apparatus for targeted secondary content insertion
US8701138B2 (en) 2010-04-23 2014-04-15 Time Warner Cable Enterprises Llc Zone control methods and apparatus
CN102347886A (zh) * 2010-07-30 2012-02-08 鸿富锦精密工业（深圳）有限公司 客户端及其选择最佳通讯路径的方法
US8542578B1 (en) 2010-08-04 2013-09-24 Cisco Technology, Inc. System and method for providing a link-state path to a node in a network environment
US8856846B2 (en) * 2010-11-29 2014-10-07 At&T Intellectual Property I, L.P. Content placement
CN102055675B (zh) * 2011-01-21 2012-12-19 清华大学 一种基于负载均衡的多径路由分配方法
US20120250535A1 (en) * 2011-03-31 2012-10-04 Microsoft Corporation Hub label based routing in shortest path determination
US9078040B2 (en) 2012-04-12 2015-07-07 Time Warner Cable Enterprises Llc Apparatus and methods for enabling media options in a content delivery network
US9854280B2 (en) 2012-07-10 2017-12-26 Time Warner Cable Enterprises Llc Apparatus and methods for selective enforcement of secondary content viewing
US8862155B2 (en) 2012-08-30 2014-10-14 Time Warner Cable Enterprises Llc Apparatus and methods for enabling location-based services within a premises
US9131283B2 (en) 2012-12-14 2015-09-08 Time Warner Cable Enterprises Llc Apparatus and methods for multimedia coordination
US20140282786A1 (en) 2013-03-12 2014-09-18 Time Warner Cable Enterprises Llc Methods and apparatus for providing and uploading content to personalized network storage
US9832500B2 (en) 2014-07-05 2017-11-28 TiltedGlobe LLC System for enabling a virtual theater
US10028025B2 (en) 2014-09-29 2018-07-17 Time Warner Cable Enterprises Llc Apparatus and methods for enabling presence-based and use-based services
US10586023B2 (en) 2016-04-21 2020-03-10 Time Warner Cable Enterprises Llc Methods and apparatus for secondary content management and fraud prevention
US10687115B2 (en) 2016-06-01 2020-06-16 Time Warner Cable Enterprises Llc Cloud-based digital content recorder apparatus and methods
US11212593B2 (en) 2016-09-27 2021-12-28 Time Warner Cable Enterprises Llc Apparatus and methods for automated secondary content management in a digital network
US10911794B2 (en) 2016-11-09 2021-02-02 Charter Communications Operating, Llc Apparatus and methods for selective secondary content insertion in a digital network
US11109290B2 (en) 2017-08-04 2021-08-31 Charter Communications Operating, Llc Switching connections over frequency bands of a wireless network
US10939142B2 (en) 2018-02-27 2021-03-02 Charter Communications Operating, Llc Apparatus and methods for content storage, distribution and security within a content distribution network

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6088436A (en) * 1994-10-11 2000-07-11 Anip, Inc. Automated callback system
US5754543A (en) 1996-07-03 1998-05-19 Alcatel Data Networks, Inc. Connectivity matrix-based multi-cost routing
DE69840844D1 (de) 1998-08-10 2009-07-02 Ibm Abstraktion einer "PNNI" Topologie
US6330229B1 (en) * 1998-11-09 2001-12-11 3Com Corporation Spanning tree with rapid forwarding database updates
US6195553B1 (en) * 1999-04-20 2001-02-27 Analytical Graphics, Inc. Method and apparatus for determining optimal paths among objects of a communications network
US6414951B1 (en) * 1999-10-08 2002-07-02 Interdigital Technology Corporation Method for detecting short codes in CDMA systems

Cited By (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100810016B1 (ko) * 2003-07-25 2008-10-27 인터내셔널 비지네스 머신즈 코포레이션 전자 장치 접속 리소스 관리
KR100905650B1 (ko) * 2007-08-01 2009-06-30 에스케이 텔레콤주식회사 신호 루트의 라우팅 코스트 오류 검출 방법과 이를 위한네트워크 관리 시스템
WO2009023689A3 (en) * 2007-08-15 2009-05-22 Adc Telecommunications Inc Delay management for distributed communications networks
US7948897B2 (en) 2007-08-15 2011-05-24 Adc Telecommunications, Inc. Delay management for distributed communications networks
US8509215B2 (en) 2007-08-15 2013-08-13 Adc Telecommunications, Inc. Delay management for distributed communications networks
US8743718B2 (en) 2011-06-21 2014-06-03 Adc Telecommunications, Inc. End-to-end delay management for distributed communications networks
USRE47545E1 (en) 2011-06-21 2019-07-30 Commscope Technologies Llc End-to-end delay management for distributed communications networks
USRE49070E1 (en) 2011-06-21 2022-05-10 Commscope Technologies Llc End-to-end delay management for distributed communications networks
US9450689B2 (en) 2013-10-07 2016-09-20 Commscope Technologies Llc Systems and methods for delay management in distributed antenna system with direct digital interface to base station
US9991978B2 (en) 2013-10-07 2018-06-05 Commscope Technologies Llc Systems and methods for delay management in distributed antenna system with direct digital interface to base station
US10567095B2 (en) 2013-10-07 2020-02-18 Commscope Technologies Llc Systems and methods for delay management in distributed antenna system with direct digital interface to base station

Also Published As

Publication number Publication date
CN1476696A (zh) 2004-02-18
WO2002043324A3 (en) 2002-09-06
AU2002212596A1 (en) 2002-06-03
US7355980B2 (en) 2008-04-08
JP3762748B2 (ja) 2006-04-05
WO2002043324A2 (en) 2002-05-30
BR0115551A (pt) 2003-08-19
KR100544008B1 (ko) 2006-01-20
US20040071089A1 (en) 2004-04-15
EP1336274A2 (en) 2003-08-20
CN1220353C (zh) 2005-09-21
TW561747B (en) 2003-11-11
JP2004515120A (ja) 2004-05-20
EP1336274B1 (en) 2012-03-21

Similar Documents

Publication Publication Date Title
KR100544008B1 (ko) 효율적인 경로 코스트 집합 도출 방법 및 장치
JP3115769B2 (ja) メトリック値をネットワークの各リンクに割り当てる方法
Yuan et al. Heuristic algorithms for multi-constrained quality of service routing
Orda Routing with end-to-end QoS guarantees in broadband networks
Orda et al. Precomputation schemes for QoS routing
Gelenbe Sensible decisions based on QoS
Kuipers et al. MAMCRA: a constrained-based multicast routing algorithm
US7397761B2 (en) Routing restorable service-level-guaranteed connections using maximum 2-route flows
Nace et al. Max–min fairness in multi-commodity flows
Georgiadis et al. Lexicographically optimal balanced networks
Carlos Sancho et al. A flexible routing scheme for networks of workstations
Curado et al. A survey of QoS routing algorithms
LeBlanc et al. Packet routing in telecommunication networks with path and flow restrictions
Yang et al. Bandwidth–delay constrained routing algorithms
Yang et al. Quality of service routing algorithms for bandwidth-delay constrained applications
Aboelela et al. Fuzzy multiobjective routing model in B-ISDN
Sobrinho et al. Routing in equilibrium
Thorup et al. Avoiding ties in shortest path first routing
Fortz Applications of meta‐heuristics to traffic engineering in IP networks
Siachalou et al. Algorithms for precomputing constrained widest paths and multicast trees
Kodialam et al. Online multicast routing with bandwidth guarantees: a new approach using multicast network flow
Ansah et al. DBvLEA: A demand-based approach to virtual link mapping for multi-service industrial applications
Aboelela et al. Fuzzy generalized network approach for solving an optimization model for routing in B‐ISDN
Bauer et al. Efficient frontier formulation for additive and restrictive metrics in hierarchical routing
Xiao et al. Approximation and heuristic algorithms for delay constrained path selection under inaccurate state information

Legal Events

Date Code Title Description
PA0105 International application

Patent event date: 20030516

Patent event code: PA01051R01D

Comment text: International Patent Application

PG1501 Laying open of application
A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20030807

Comment text: Request for Examination of Application

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20051005

Patent event code: PE09021S01D

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20051220

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20060110

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20060109

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
PR1001 Payment of annual fee

Payment date: 20090106

Start annual number: 4

End annual number: 4

PR1001 Payment of annual fee

Payment date: 20091203

Start annual number: 5

End annual number: 5

FPAY Annual fee payment

Payment date: 20101210

Year of fee payment: 6

PR1001 Payment of annual fee

Payment date: 20101210

Start annual number: 6

End annual number: 6

LAPS Lapse due to unpaid annual fee
PC1903 Unpaid annual fee